s***c
发帖数: 50 | 1 刚从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! |
g*******e
发帖数: 61 | |
f*******t
发帖数: 7549 | |
k****n
发帖数: 369 | 4 太感谢了！
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什么答案阿
【在 s***c 的大作中提到】
: 刚从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)
|
v***n
发帖数: 5085 | |
x****1
发帖数: 118 | 6 bless!
我也是感觉别人的面经都比我的难，可能是看别人面经的时候不如面试的时候精力集中
吧 |
w****r
发帖数: 245 | 7 看着都不难
第一个，不用找最小的，直接比就是了
ob)
【在 s***c 的大作中提到】
: 刚从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)
|
g*****i
发帖数: 2162 | 8 bless?楼主什么背景? fresh graduate吗?
第一题我觉得不需要完整的suffix tree,因为题目只要找longest prefix,所以就把每
个string的插入一次就可以了,还可以记录当前的longest prefix的长度来加速. 另外
linear suffix tree construction好像很复杂吧.
第二题如果文件在memory放不下怎么办呢?
第四题每个server的os image都一样吗?如果一样的话应该是类似找一个快速扩散的方法
第七题这种多线程题没经验的总觉得很麻烦啊,楼主说的unblock型是什么意思?
【在 k****n 的大作中提到】
: 太感谢了！
:
: 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分布的点，丢弃圆外面的点
|
k****n
发帖数: 369 | 9 对，我土鳖了，直接比就好了，keep当前的最长prefix
方法
【在 g*****i 的大作中提到】
: bless?楼主什么背景? fresh graduate吗?
: 第一题我觉得不需要完整的suffix tree,因为题目只要找longest prefix,所以就把每
: 个string的插入一次就可以了,还可以记录当前的longest prefix的长度来加速. 另外
: linear suffix tree construction好像很复杂吧.
: 第二题如果文件在memory放不下怎么办呢?
: 第四题每个server的os image都一样吗?如果一样的话应该是类似找一个快速扩散的方法
: 第七题这种多线程题没经验的总觉得很麻烦啊,楼主说的unblock型是什么意思?
|
w****r
发帖数: 245 | 10 第一个直接找
第二个不一定要放整个文件，MD5是不错的选择
第四个感觉就是让node自己定期去哪里下新image，然后自动重装，加速的话个人认为
是指整个系统被block的时间，比如可以在有些node更新中的情况下，其他node继续用
旧版本工作，用扩散的方法太容易出错。。实际中应该很少用
第七个要问很多问题，比如这个定期得间隔是多少，扫描一个sensor要多久，如果坏了
需要最慢多久探测到，判断错误的话有没有什么后果。这在实际应用中可能都有
requirement的，根据这些条件再设计具体
方法
方法
【在 g*****i 的大作中提到】
: bless?楼主什么背景? fresh graduate吗?
: 第一题我觉得不需要完整的suffix tree,因为题目只要找longest prefix,所以就把每
: 个string的插入一次就可以了,还可以记录当前的longest prefix的长度来加速. 另外
: linear suffix tree construction好像很复杂吧.
: 第二题如果文件在memory放不下怎么办呢?
: 第四题每个server的os image都一样吗?如果一样的话应该是类似找一个快速扩散的方法
: 第七题这种多线程题没经验的总觉得很麻烦啊,楼主说的unblock型是什么意思?
|
|
|
s***c
发帖数: 50 | 11
第二个问题我也用了类似的回答。把文件按size分类。然后对同样大小的文件，用某种
编码计算signature。signature相同的就是内容相同。同时用hash表来加速signature
的匹配查询。可是那个面试官说任何编码都会有conflict，也就是不同内容生成相同的
编码。其实MD5的编码可以做到重复率低于硬盘故障率。
【在 w****r 的大作中提到】
: 第一个直接找
: 第二个不一定要放整个文件，MD5是不错的选择
: 第四个感觉就是让node自己定期去哪里下新image，然后自动重装，加速的话个人认为
: 是指整个系统被block的时间，比如可以在有些node更新中的情况下，其他node继续用
: 旧版本工作，用扩散的方法太容易出错。。实际中应该很少用
: 第七个要问很多问题，比如这个定期得间隔是多少，扫描一个sensor要多久，如果坏了
: 需要最慢多久探测到，判断错误的话有没有什么后果。这在实际应用中可能都有
: requirement的，根据这些条件再设计具体
: 方法
:
|
a********1
发帖数: 750 | 12 一个bst, 寻找第I小的值。 不用说了吧。
怎么做？要用order-statics给每个Node加上有多少left child的信息吗？还是in-
order 硬算 |
P**l
发帖数: 3722 | |
w****r
发帖数: 245 | 14 signature相同就读出来比较不行吗？
signature
【在 s***c 的大作中提到】
:
: 第二个问题我也用了类似的回答。把文件按size分类。然后对同样大小的文件，用某种
: 编码计算signature。signature相同的就是内容相同。同时用hash表来加速signature
: 的匹配查询。可是那个面试官说任何编码都会有conflict，也就是不同内容生成相同的
: 编码。其实MD5的编码可以做到重复率低于硬盘故障率。
|
y******n
发帖数: 47 | 15 感觉功力还是不行, 看着不难, 写起来还是花了好一阵功夫. 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);
}
【在 a********1 的大作中提到】
: 一个bst, 寻找第I小的值。 不用说了吧。
: 怎么做？要用order-statics给每个Node加上有多少left child的信息吗？还是in-
: order 硬算
|
g****n
发帖数: 194 | 16 Google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html
ob)
【在 s***c 的大作中提到】
: 刚从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)
|
y******n
发帖数: 47 | 17
> 6. 编程题： 一个int array, 求每连续K个值的和。就是一个K大小的窗口沿着数组滑
> 动，求该窗口内数的和。
每移动一次窗口,减去旧窗口第一个数,然后加上新窗口最后一个数? 是不是还有什么条
件?
【在 s***c 的大作中提到】
:
: 第二个问题我也用了类似的回答。把文件按size分类。然后对同样大小的文件，用某种
: 编码计算signature。signature相同的就是内容相同。同时用hash表来加速signature
: 的匹配查询。可是那个面试官说任何编码都会有conflict，也就是不同内容生成相同的
: 编码。其实MD5的编码可以做到重复率低于硬盘故障率。
|
r*******g
发帖数: 1335 | 18 第一个题，为何不是依次比较。
比如第一个和第二个的common prefix长度为10，第三个string就只需要和这个common
prefix比较，然后不断比较下去。
prefix就是长度的意思，比如abcxxxx,abdyyyy,结果就是ab？
第六题说的不是很清楚，有什么限制条件没有
Thanks. |
d***n
发帖数: 65 | 19 先祝楼主好运~
最后一题sampling rejection应该可以吧。随机取在以圆直径为边长的正方形内的某一
点，如果这点在圆内输出，不在的话reject。 |
y******n
发帖数: 47 | 20 谢谢共享, 祝LZ好运!
【在 s***c 的大作中提到】
:
: 第二个问题我也用了类似的回答。把文件按size分类。然后对同样大小的文件，用某种
: 编码计算signature。signature相同的就是内容相同。同时用hash表来加速signature
: 的匹配查询。可是那个面试官说任何编码都会有conflict，也就是不同内容生成相同的
: 编码。其实MD5的编码可以做到重复率低于硬盘故障率。
|
|
|
P**********c
发帖数: 3417 | 21 这个方法不错。
【在 d***n 的大作中提到】
: 先祝楼主好运~
: 最后一题sampling rejection应该可以吧。随机取在以圆直径为边长的正方形内的某一
: 点，如果这点在圆内输出，不在的话reject。
|
g**e
发帖数: 6127 | 22 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)
【在 s***c 的大作中提到】
: 刚从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)
|
s*****y
发帖数: 897 | 23 你好久不做题了。
【在 g**e 的大作中提到】
: 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)
|
s***c
发帖数: 50 | 24
组滑
我就是这么做的。感觉面试官还满意。
【在 y******n 的大作中提到】
: 谢谢共享, 祝LZ好运!
|
s***c
发帖数: 50 | 25
common
第六题是说，一个int array，对每连续K个元素求和。好像没说什么限制条件。可能要
判断一下K>array size的情况吧。
【在 r*******g 的大作中提到】
: 第一个题，为何不是依次比较。
: 比如第一个和第二个的common prefix长度为10，第三个string就只需要和这个common
: prefix比较，然后不断比较下去。
: prefix就是长度的意思，比如abcxxxx,abdyyyy,结果就是ab？
: 第六题说的不是很清楚，有什么限制条件没有
: Thanks.
|
s***c
发帖数: 50 | 26
这个方法简单又有效。我当时弱智了就是想不到。。。
【在 d***n 的大作中提到】
: 先祝楼主好运~
: 最后一题sampling rejection应该可以吧。随机取在以圆直径为边长的正方形内的某一
: 点，如果这点在圆内输出，不在的话reject。
|
s*****y
发帖数: 897 | 27 那么用什么方法他才满意啊？
【在 s***c 的大作中提到】
:
: 这个方法简单又有效。我当时弱智了就是想不到。。。
|
m****t
发帖数: 555 | 28 这么简单的题，不知道要考查什么？
【在 s***c 的大作中提到】
:
: 这个方法简单又有效。我当时弱智了就是想不到。。。
|
g**e
发帖数: 6127 | 29 10点半下班回家还顺便做个题，我容易么…… 眼泪哗哗的啊
【在 s*****y 的大作中提到】
: 你好久不做题了。
|
p**********t
发帖数: 126 | |
|
|
A***M
发帖数: 18 | 31 近来google面试好像没什么难题。不过另一方面， 不知道google更侧重于什么了。 以
前至少知道难题做出来了feedback不会差。 |
s***c
发帖数: 50 | 32
common
第一题我的方法是： 先找出最短的字符串，然后，对于该字符串的每个字符，依次与
其他字符串的对应位置比较。如果相等，继续下一个字符串。一旦看到一个不等，马上
退出。当前已经完成的最短字符串部分，就是longest common prefix。
第6题，就是给一个int array，每连续K个元素为一组，求该组元素的和。
【在 r*******g 的大作中提到】
: 第一个题，为何不是依次比较。
: 比如第一个和第二个的common prefix长度为10，第三个string就只需要和这个common
: prefix比较，然后不断比较下去。
: prefix就是长度的意思，比如abcxxxx,abdyyyy,结果就是ab？
: 第六题说的不是很清楚，有什么限制条件没有
: Thanks.
|
h**6
发帖数: 4160 | 33 最后一题。
19楼demon的结果和22楼gate的结果是不同的，只是两人都没有错，一个是直角坐标系
的uniform分布，一个是极坐标系的uniform分布。
这是一个著名的悖论：
http://en.wikipedia.org/wiki/Bertrand_paradox_(probability) |
g**e
发帖数: 6127 | 34 赞，学习了
【在 h**6 的大作中提到】
: 最后一题。
: 19楼demon的结果和22楼gate的结果是不同的，只是两人都没有错，一个是直角坐标系
: 的uniform分布，一个是极坐标系的uniform分布。
: 这是一个著名的悖论：
: http://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
|
y******n
发帖数: 47 | 35
应该是 x = r*cos(theta); y = r*sin(theta) ?
【在 g**e 的大作中提到】
: 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)
|
m**q
发帖数: 189 | 36 就是说是否均匀分布是依赖于坐标系的， 直角坐标系的
uniform分布拿到极坐标系就不是uniform了，反之亦然？
【在 h**6 的大作中提到】
: 最后一题。
: 19楼demon的结果和22楼gate的结果是不同的，只是两人都没有错，一个是直角坐标系
: 的uniform分布，一个是极坐标系的uniform分布。
: 这是一个著名的悖论：
: http://en.wikipedia.org/wiki/Bertrand_paradox_(probability)
|
