S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
sharc (sharc) 于 (Mon Aug 22 15:15:14 2011, 美东) 提到:
刚从G家onsite归来。新鲜面经奉上。
总共5轮，4轮technical interview, 一个thesis discussion。在technical里，有编
程题，有open design。我记得的问题有：
1. 编程题：一堆字符串。找longest common prefix。
我的方法就是找最短的字符串，对它的每个字符，逐个与其他字符串对应位置比较。（
求更好方法）
2. open question: 一堆文件，size差别极大( from KB to many GB). 找出所有内
容相同的文件。
3. 编程题： 有一个observer 类，监视另一个类foo 的成员变量的值，每当那个值被
修改，就要调用 该observer.updated() 方法。需要实现 foo.registerObserver(ob)
, foo.unregisterObserver( ob ), foo.changeValue( newvalue ). 要考虑thread
safe.
就是在register时把所有observer 链接到一个list里。在changeValue()里，逐个唤醒
observer。 要用lock保护对于这个链表的访问。
4. open question: 一个大型cluster 包括thousands of nodes. 需要定期
upgrade 每个server跑的 OS image (也就是重装). 如何设计一个方案加速该过程。
5. 编程题： 一个bst, 寻找第I小的值。 不用说了吧。
6. 编程题： 一个int array, 求每连续K个值的和。就是一个K大小的窗口沿着数组滑
动，求该窗口内数的和。
7. Open question: 一个sensor network有很多sensors, 一个server 定期query 每
个sensor的值。sensor may fail。如何让server 避免被block。
我的想法是把query()做成unblock 型的，一个sender thread 定期向每个sensor发送
请求，然后用一个接收thread来接收答复。在sender 发送请求时，如果上一轮的答复
还没有来，就认为该sensor坏了。
8. 一个圆，产生uniform分布的点。
这时已经很累了。只想到随机产生半径和角度。但是概率和每个半径所对应的面积相关
。我觉得 p( r
=== 感想：
这些题目大都没有版上的面经难，不知道为什么。
还有，每个面试官都会把白板上的内容拍照，输入电脑，作为feedback的依据。所以白
板编程一定要特别仔细，把它当成是要编译的程序来写。我写第一个编程题时没有意识
到，犯了点错误。大家一定注意。
祝大家都有满意的offer!
☆─────────────────────────────────────☆
glorywine (glorywine) 于 (Mon Aug 22 15:21:42 2011, 美东) 提到:
bless
☆─────────────────────────────────────☆
fantasist (fan) 于 (Mon Aug 22 15:35:26 2011, 美东) 提到:
前排bless
感谢分享！
☆─────────────────────────────────────☆
kevinn (Kevinn) 于 (Mon Aug 22 15:37:07 2011, 美东) 提到:
太感谢了！
suffix tree，不过真的要白板编么？能不能写下阿
key is to reduce disk access
if it is possible to keep it in memory, then first bucket files with sizes,
then inside the bucket use (MD5 => file) hash map.
ob)
thread
have no idea，求布道
生成正方形uniform分布的点，丢弃圆外面的点
笛卡尔坐标系就麻烦多了，距圆心距离不同概率不同
Open question好多，我最讨厌这种，谁知道面试官prefer什么答案阿
☆─────────────────────────────────────☆
vsfan (小饭) 于 (Mon Aug 22 15:46:58 2011, 美东) 提到:
congs, baozi plz
☆─────────────────────────────────────☆
xyf501 (Ivan) 于 (Mon Aug 22 15:59:09 2011, 美东) 提到:
bless!
我也是感觉别人的面经都比我的难，可能是看别人面经的时候不如面试的时候精力集中
吧
☆─────────────────────────────────────☆
wiscer (BXB) 于 (Mon Aug 22 16:08:30 2011, 美东) 提到:
看着都不难
第一个，不用找最小的，直接比就是了
ob)
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Mon Aug 22 16:31:39 2011, 美东) 提到:
bless?楼主什么背景? fresh graduate吗?
第一题我觉得不需要完整的suffix tree,因为题目只要找longest prefix,所以就把每
个string的插入一次就可以了,还可以记录当前的longest prefix的长度来加速. 另外
linear suffix tree construction好像很复杂吧.
第二题如果文件在memory放不下怎么办呢?
第四题每个server的os image都一样吗?如果一样的话应该是类似找一个快速扩散的方法
第七题这种多线程题没经验的总觉得很麻烦啊,楼主说的unblock型是什么意思?
☆─────────────────────────────────────☆
kevinn (Kevinn) 于 (Mon Aug 22 16:32:44 2011, 美东) 提到:
对，我土鳖了，直接比就好了，keep当前的最长prefix
方法
☆─────────────────────────────────────☆
wiscer (BXB) 于 (Mon Aug 22 16:41:04 2011, 美东) 提到:
第一个直接找
第二个不一定要放整个文件，MD5是不错的选择
第四个感觉就是让node自己定期去哪里下新image，然后自动重装，加速的话个人认为
是指整个系统被block的时间，比如可以在有些node更新中的情况下，其他node继续用
旧版本工作，用扩散的方法太容易出错。。实际中应该很少用
第七个要问很多问题，比如这个定期得间隔是多少，扫描一个sensor要多久，如果坏了
需要最慢多久探测到，判断错误的话有没有什么后果。这在实际应用中可能都有
requirement的，根据这些条件再设计具体
方法
方法
☆─────────────────────────────────────☆
sharc (sharc) 于 (Mon Aug 22 17:23:36 2011, 美东) 提到:
第二个问题我也用了类似的回答。把文件按size分类。然后对同样大小的文件，用某种
编码计算signature。signature相同的就是内容相同。同时用hash表来加速signature
的匹配查询。可是那个面试官说任何编码都会有conflict，也就是不同内容生成相同的
编码。其实MD5的编码可以做到重复率低于硬盘故障率。
☆─────────────────────────────────────☆
anonymous1 (无名氏) 于 (Mon Aug 22 17:28:45 2011, 美东) 提到:
一个bst, 寻找第I小的值。 不用说了吧。
怎么做？要用order-statics给每个Node加上有多少left child的信息吗？还是in-
order 硬算
☆─────────────────────────────────────☆
Perl (怀念在裤子大的日子) 于 (Mon Aug 22 17:34:21 2011, 美东) 提到:
zan
☆─────────────────────────────────────☆
wiscer (BXB) 于 (Mon Aug 22 17:37:17 2011, 美东) 提到:
signature相同就读出来比较不行吗？
signature
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 22 17:54:43 2011, 美东) 提到:
感觉功力还是不行, 看着不难, 写起来还是花了好一阵功夫. lastNode用来处理i大于
树节点总数的情况, 也就是返回right most node.
int findith(Node *r, int i) {
assert(r != NULL);
assert(i > 0);
int k = i; Node *lastNode;
Node * ret = helper(r, k, lastNode);
return (ret != NULL) ? ret->value : lastNode->value;
}
Node *helper(Node *n, int& k, Node *& lastNode) {
if (n == NULL)
return NULL;
Node *ret = helper(n->left, k, lastNode);
if (ret != NULL)
return ret;
k--;
if (k == 0)
return n;
lastNode = n;
return helper(n->right, k, lastNode);
}
☆─────────────────────────────────────☆
gabman (gabman) 于 (Mon Aug 22 18:07:26 2011, 美东) 提到:
Google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html
ob)
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 22 18:22:32 2011, 美东) 提到:
> 6. 编程题： 一个int array, 求每连续K个值的和。就是一个K大小的窗口沿着数组滑
> 动，求该窗口内数的和。
每移动一次窗口,减去旧窗口第一个数,然后加上新窗口最后一个数? 是不是还有什么条
件?
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Mon Aug 22 19:01:41 2011, 美东) 提到:
第一个题，为何不是依次比较。
比如第一个和第二个的common prefix长度为10，第三个string就只需要和这个common
prefix比较，然后不断比较下去。
prefix就是长度的意思，比如abcxxxx,abdyyyy,结果就是ab？
第六题说的不是很清楚，有什么限制条件没有
Thanks.
☆─────────────────────────────────────☆
demon (brute-force) 于 (Mon Aug 22 21:56:22 2011, 美东) 提到:
先祝楼主好运~
最后一题sampling rejection应该可以吧。随机取在以圆直径为边长的正方形内的某一
点，如果这点在圆内输出，不在的话reject。
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 22 22:20:24 2011, 美东) 提到:
谢谢共享, 祝LZ好运!
☆─────────────────────────────────────☆
PixelClassic (如梦) 于 (Mon Aug 22 23:32:06 2011, 美东) 提到:
这个方法不错。
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Tue Aug 23 02:13:56 2011, 美东) 提到:
8. let rand() generates uniform distributed value between [0,1)
r = sqrt( rand() );
theta = rand() * 2 * pi;
x = r*sin(theta);
y = r*cos(theta);
return (x,y);
ob)
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Tue Aug 23 02:34:05 2011, 美东) 提到:
你好久不做题了。
☆─────────────────────────────────────☆
sharc (sharc) 于 (Tue Aug 23 11:01:39 2011, 美东) 提到:
组滑
我就是这么做的。感觉面试官还满意。
☆─────────────────────────────────────☆
sharc (sharc) 于 (Tue Aug 23 11:05:30 2011, 美东) 提到:
common
第六题是说，一个int array，对每连续K个元素求和。好像没说什么限制条件。可能要
判断一下K>array size的情况吧。
☆─────────────────────────────────────☆
sharc (sharc) 于 (Tue Aug 23 11:29:42 2011, 美东) 提到:
这个方法简单又有效。我当时弱智了就是想不到。。。
☆─────────────────────────────────────☆
speeddy (Wade) 于 (Tue Aug 23 11:55:11 2011, 美东) 提到:
那么用什么方法他才满意啊？
☆─────────────────────────────────────☆
meghat (meghat) 于 (Tue Aug 23 12:00:22 2011, 美东) 提到:
这么简单的题，不知道要考查什么？
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Tue Aug 23 12:17:56 2011, 美东) 提到:
10点半下班回家还顺便做个题，我容易么…… 眼泪哗哗的啊
☆─────────────────────────────────────☆
pursuitbeaut (寻美) 于 (Tue Aug 23 12:40:15 2011, 美东) 提到:
☆─────────────────────────────────────☆
AFGHM (面试中.......) 于 (Tue Aug 23 13:23:31 2011, 美东) 提到:
近来google面试好像没什么难题。不过另一方面， 不知道google更侧重于什么了。 以
前至少知道难题做出来了feedback不会差。
☆─────────────────────────────────────☆
sharc (sharc) 于 (Tue Aug 23 18:07:30 2011, 美东) 提到:
common
第一题我的方法是： 先找出最短的字符串，然后，对于该字符串的每个字符，依次与
其他字符串的对应位置比较。如果相等，继续下一个字符串。一旦看到一个不等，马上
退出。当前已经完成的最短字符串部分，就是longest common prefix。
第6题，就是给一个int array，每连续K个元素为一组，求该组元素的和。
☆─────────────────────────────────────☆
han6 (周瑜) 于 (Tue Aug 23 18:24:59 2011, 美东) 提到:
最后一题。
19楼demon的结果和22楼gate的结果是不同的，只是两人都没有错，一个是直角坐标系
的uniform分布，一个是极坐标系的uniform分布。
这是一个著名的悖论：
http://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
☆─────────────────────────────────────☆
gate (离开之后，再见以前) 于 (Tue Aug 23 19:38:48 2011, 美东) 提到:
赞，学习了
☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Tue Aug 23 23:27:41 2011, 美东) 提到:
应该是 x = r*cos(theta); y = r*sin(theta) ?
☆─────────────────────────────────────☆
maxq (zf) 于 (Wed Aug 24 00:14:15 2011, 美东) 提到:
就是说是否均匀分布是依赖于坐标系的， 直角坐标系的
uniform分布拿到极坐标系就不是uniform了，反之亦然？
☆─────────────────────────────────────☆
kirit (Jack) 于 (Tue Jan 17 01:22:19 2012, 美东) 提到:
What if the strings are sorted with both the length and lexi order and the
longer ones are at the front? For example,
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzza
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzb
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzc
zx
Can we optimize the approach?
1. 编程题：一堆字符串。找longest common prefix。
我的方法就是找最短的字符串，对它的每个字符，逐个与其他字符串对应位置比较。（
求更好方法）
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jan 17 01:39:36 2012, 美东) 提到:
Put the shortest in the front and just compare the character one by one.
Since the 4th string's 2nd character is not z, it will exit the loop after
the first iteration going over all strings.
I don't believe there's a better approach than brute force.
Unless you need to query the function at least few times in a row, and each
time the input may change dynamically, then a trie might be a better option.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 03:30:35 2012, 美东) 提到:
不满意是因为你这个算法空间复杂度是O(N)吧？本来空间复杂度可以O(1)的。
☆─────────────────────────────────────☆
kirit (Jack) 于 (Tue Jan 17 04:54:16 2012, 美东) 提到:
To get the shortest string, we would have to go through all the strings once
. The following code go from another direction, like radix sort.
Pros & cons?
string common_prefix (vector& vs) {
string ret;
int i = 0;
while (1)
{
if (i >= vs[0].size()) break;
char c = vs[0][i];
for (int j = 1; j < vs.size(); ++j)
{
if (vs[j].size() <= i) break;
if (vs[j][i] != c) break;
}
++i;
ret.push_back(c);
}
return ret;
}
each
option.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 12:43:56 2012, 美东) 提到:
结果可以保存到原array呀。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 12:49:17 2012, 美东) 提到:
估计考官没准就是考这个。
☆─────────────────────────────────────☆
Delon (Delon) 于 (Tue Jan 17 14:04:52 2012, 美东) 提到:
LZ好人.赞!
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jan 17 14:05:25 2012, 美东) 提到:
I have made some test cases in Online Judge, you can test your solution for
"Longest Common Prefix" by running it here: http://www.leetcode.com/onlinejudge
The break statement in your inner for loop doesn't break out the outer while
loop. You should put a return statement there, ie:
if (vs[j].size() <= i || (vs[j][i] != c)
return ret;
Also, why is there a while(1) loop? This doesn't communicate clearly what
the while loop intend to do. It is best to avoid such situation if possible.
It could be much clearer by specifying:
while (i < vs[0].size()) {
...
}
once
☆─────────────────────────────────────☆
lanb (Bin) 于 (Tue Jan 17 14:27:11 2012, 美东) 提到:
signature一样的话，可以直接读每个文件的first N bytes。因为如果真的发现了md5
或者其他的hashing的coflict的情况，文件的内容相差会非常巨大，根本不用读完所有
的文件。最重要的，我个人觉得，文件大小一样，MD5也一样的可能性应该基本不纯在
了。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 14:52:46 2012, 美东) 提到:
md5
我觉得也是，大不了再用另一种hash方法hash一次吧？
☆─────────────────────────────────────☆
kirit (Jack) 于 (Tue Jan 17 16:17:00 2012, 美东) 提到:
Nice points. Updated code below.
Tried your online test, 24 ms for the large setand 4 ms for the small set.
#include
#include
#include
using namespace std;
string common_prefix (vector& vs) {
string ret;
int i = 0;
if (vs.size() <1) return "";
while (i
{
char c = vs[0][i];
for (int j = 1; j < vs.size(); ++j)
if ((vs[j].size() <= i) || (vs[j][i] != c)) return ret;
++i;
ret.push_back(c);
}
return ret;
}
int main () {
vector vs;
cout << common_prefix(vs);
}
for
while
possible.
☆─────────────────────────────────────☆
Hbase (Hbase) 于 (Tue Jan 17 22:33:50 2012, 美东) 提到:
留个记号
这面经真有料。。
ob)
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Wed Jan 18 10:46:45 2012, 美东) 提到:
这样的干帖，不得不顶！谢谢楼主
☆─────────────────────────────────────☆
etlds (E.T.) 于 (Wed Jan 18 11:18:55 2012, 美东) 提到:
贡献第一题的C# code
int ptr = 0;
bool bOK = true;
while (bOK)
{
char currchar = words[0][ptr];
for (int i = 1; i < words.Length; i++)
{
try
{
bOK = bOK && (words[i][ptr] == currchar);
}
catch(IndexOutOfRangeException)
{
bOK = false;
}
}
if (bOK)
ptr++;
}
return words[0].Substring(0, ptr); |
|
