google on campus 面试多久出结果+面经 - 未名空间MITBBS历史存档

google on campus 面试多久出结果+面经# JobHunting - 待字闺中

n*n2010-11-03 07:11

1 楼

请问版上各位google on campus面试多久能出结果？整个过程走下来，直到最后知道
hiring decision需要多长时间？一个月够吗
我昨天刚面了2轮，各45分钟。下面是题目
1. count the number of 1s in binary representation 我用的4位4位hash的方法
但是没有考虑负数情况，在面试官提示下，意识到对负数向右shift,发生的是sign
extension, 所以这题要先对输入进行检查。
2. remove duplicates from linked list, suppose you can use stl list. 我用的
hash_set, 这题很顺利。
3. 很长很长的string/file, 要我找出中间重复次数最多的character, character set
可能是任何char set, unicode... 我说mapreduce, 后来面试官说如果是一台机器，8
个core, 1个process,怎么办。我说似乎mapreduce需要在distributed system环境下(
但其实我不肯定，如果一台机器多进程/多线程)是不是就也可以mapreduce）.面试官又
给了提示，我才说multi-process,后改成multi-threading, 后来他问我那几个thread
怎么写协调，我说可以公用data segment in the process space, 但是要注意锁的问
题。最后他问我说mapreduce和multi-thread的tradeoff，我说communication
overhead, 似乎他对我的答案满意。
我和面试官说honestly第一题我见过了（我不知道这是不是画蛇添足了！！！！！）
哎总之虽然觉得自己答得还可以但是很担心！！
第二个人先问了一些暑期实习的项目问题
1. 设计一个counte class, 写一个函数算某机器最后一分钟处理任务的个数。我说用
circular array, 他说right way to go, 但是在细节上澄清了一会。不知道是不是我
的表达不够好。
2. vector of vector of ints, 请implement bool hasnext()和int next() 我说要用
一个变量track在nested vector中的位置，他提示用2个，然后我开始code, hasnext
code完了然后也解释给他，似乎没有问题。next() 由于时间不够，但我把逻辑解释完
了，把关键的那4，5行code出来。
希望能有好结果！同bless版上各位！

d*t2010-11-03 07:11

2 楼

赞分享~ bless~
第1题为什么要用HASH呢？如果二进制表示N，一遍扫下来也就是O(logN)吧。
第二人的第1题，我觉得用queue也行。用array初始化成多大才能确保不越界？

j*u2010-11-03 07:11

3 楼

楼上，建议看看hacker's delight，非常好的一本书。
第一个人的第3题比较有意思，但是他问的是charactor不是word，unicode通常也只有
16bit，memory里开一个hash或者array最大也就是2^16 * 4 byte = 256kb, not big
deal
这种情况下因为瓶颈在于读文件而不是计算，multi thread或者process都不会提高速度
如果是word就有意思的多，假设memory里放不下，multi thread或者process都可以，
thread之间sync简单一些，就是M个producer，N个consumer的问题，如果是C#我会用
ManualResetEvent + Interlock来写。

n*n2010-11-03 07:11

4 楼

@jerryju: sorry i can't type chinese in the lab
Thanks for your insightful suggestion. Actually for question 3, I suggested
hash at the very beginning saying that ascii only takes 8 bit at most. But
the interviewer seemed to look for other solutions, and told me "imagine you
can have random char from a char set of unknown size"... that's why i
switched to other solutions...

n*n2010-11-03 07:11

5 楼

@doritslt: for question 1 from second person, notice it is a circular array,
so no out-of-bound. Old values will get replaced by new values.

d*t2010-11-03 07:11

6 楼

第一题你说的hash是指mask吗？
不好意思，还是没明白。circular array怎么处理最后一分钟处理的任务个数比array
size还大的情况？

s*e2010-11-03 07:11

7 楼

For the question "count the number of 1s in binary representation"
Do they expect something like:
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return(x & 0x0000003f);
?
Is it not good to give an answer like:
count=0;
while(x)
{
if(x & 1) count++;
x = x >>1;
}
return count;
?
And for negative numbers, shall we first force the most significant bit to 0, and add 1 to the final answer?
Thanks!

s*t2010-11-03 07:11

8 楼

谢谢分享，祝好运！
有几个问题：
一面第2个，普通set就应该就行了吧，是不是就是挨个把item往set里塞。用hash_set
在这个题上有什么优势吗？

set
，8

【在 n******n 的大作中提到】

: 请问版上各位google on campus面试多久能出结果？整个过程走下来，直到最后知道
: hiring decision需要多长时间？一个月够吗
: 我昨天刚面了2轮，各45分钟。下面是题目
: 1. count the number of 1s in binary representation 我用的4位4位hash的方法
: 但是没有考虑负数情况，在面试官提示下，意识到对负数向右shift,发生的是sign
: extension, 所以这题要先对输入进行检查。
: 2. remove duplicates from linked list, suppose you can use stl list. 我用的
: hash_set, 这题很顺利。
: 3. 很长很长的string/file, 要我找出中间重复次数最多的character, character set
: 可能是任何char set, unicode... 我说mapreduce, 后来面试官说如果是一台机器，8

A*H2010-11-03 07:11

9 楼

how about this, easy and simple, very efficient for small number of 1 bit
int countBit(int x) {
unsigned int r=0;
while(x) {
x &= x-1;
r++;
}
return r;
}

【在 s*******e 的大作中提到】

: For the question "count the number of 1s in binary representation"
: Do they expect something like:
: x -= ((x >> 1) & 0x55555555);
: x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
: x = (((x >> 4) + x) & 0x0f0f0f0f);
: x += (x >> 8);
: x += (x >> 16);
: return(x & 0x0000003f);
: ?
: Is it not good to give an answer like:

g*s2010-11-03 07:11

10 楼

什么是4位4位hash？

set
，8

【在 n******n 的大作中提到】

: 请问版上各位google on campus面试多久能出结果？整个过程走下来，直到最后知道
: hiring decision需要多长时间？一个月够吗
: 我昨天刚面了2轮，各45分钟。下面是题目
: 1. count the number of 1s in binary representation 我用的4位4位hash的方法
: 但是没有考虑负数情况，在面试官提示下，意识到对负数向右shift,发生的是sign
: extension, 所以这题要先对输入进行检查。
: 2. remove duplicates from linked list, suppose you can use stl list. 我用的
: hash_set, 这题很顺利。
: 3. 很长很长的string/file, 要我找出中间重复次数最多的character, character set
: 可能是任何char set, unicode... 我说mapreduce, 后来面试官说如果是一台机器，8

r*g2010-11-03 07:11

11 楼

估计是把hex里面从0到15(4bit)的1的个数纪录下来，把1的数目存到hash table里去，
比如
0-〉0个'1'
1-〉1个'1'
2-〉1个'1'
3-〉2个'1'
。。。
15-〉4个'1'
然后再一下取4个bit，查询hash table就可以了，貌似比1个bit那种快一些。很久以前
看过，不
太确定了。。

【在 g*********s 的大作中提到】

: 什么是4位4位hash？
:
: set
: ，8

K*g2010-11-03 07:11

12 楼

不懂为什么是M个producer,N个consumer?哪里来的N个consumer?
其实就是M个producer share一个N item的array.

速度

【在 j*****u 的大作中提到】

: 楼上，建议看看hacker's delight，非常好的一本书。
: 第一个人的第3题比较有意思，但是他问的是charactor不是word，unicode通常也只有
: 16bit，memory里开一个hash或者array最大也就是2^16 * 4 byte = 256kb, not big
: deal
: 这种情况下因为瓶颈在于读文件而不是计算，multi thread或者process都不会提高速度
: 如果是word就有意思的多，假设memory里放不下，multi thread或者process都可以，
: thread之间sync简单一些，就是M个producer，N个consumer的问题，如果是C#我会用
: ManualResetEvent + Interlock来写。

j*u2010-11-03 07:11

13 楼

去看看map reduce你就明白了
M个mapper，N个reducer的instance

【在 K******g 的大作中提到】

: 不懂为什么是M个producer,N个consumer?哪里来的N个consumer?
: 其实就是M个producer share一个N item的array.
:
: 速度

n*n2010-11-03 07:11

14 楼

对的我是这么做的
我这个不是最好的做法。。。

【在 r********g 的大作中提到】

: 估计是把hex里面从0到15(4bit)的1的个数纪录下来，把1的数目存到hash table里去，
: 比如
: 0-〉0个'1'
: 1-〉1个'1'
: 2-〉1个'1'
: 3-〉2个'1'
: 。。。
: 15-〉4个'1'
: 然后再一下取4个bit，查询hash table就可以了，貌似比1个bit那种快一些。很久以前
: 看过，不

n*n2010-11-03 07:11

15 楼

这个解法中，x如果是负数，同样会有问题。
因为负数向右做的是arithmetic shift, sign extension导致前面全部变成1，这样
while(x) 这个loop never finishes
这就是我那天犯的错误。。。

【在 A*H 的大作中提到】

: how about this, easy and simple, very efficient for small number of 1 bit
: int countBit(int x) {
: unsigned int r=0;
: while(x) {
: x &= x-1;
: r++;
: }
: return r;
: }

n*n2010-11-03 07:11

16 楼

对的就是挨个网里塞，但是hash_set c++中insert/lookup amortized下来都是o(1),普
通set是红黑树实现，o(lgn),所以普通set慢一点。

set

【在 s*******t 的大作中提到】

: 谢谢分享，祝好运！
: 有几个问题：
: 一面第2个，普通set就应该就行了吧，是不是就是挨个把item往set里塞。用hash_set
: 在这个题上有什么优势吗？
:
: set
: ，8

e*62010-11-03 07:11

17 楼

array
同问有关circular array，我也被问到过同样问题，至今不知道怎么做。。。

【在 d*****t 的大作中提到】

: 第一题你说的hash是指mask吗？
: 不好意思，还是没明白。circular array怎么处理最后一分钟处理的任务个数比array
: size还大的情况？

g*s2010-11-03 07:11

18 楼

这两个问题我统统没看懂……
1. 设计一个counte class, 写一个函数算某机器最后一分钟处理任务的个数。我说用
circular array, 他说right way to go, 但是在细节上澄清了一会。不知道是不是我
的表达不够好。
2. vector of vector of ints, 请implement bool hasnext()和int next() 我说要
用
一个变量track在nested vector中的位置，他提示用2个，然后我开始code, hasnext
code完了然后也解释给他，似乎没有问题。next() 由于时间不够，但我把逻辑解释完
了，把关键的那4，5行code出来。

我用的
set
，8

【在 n******n 的大作中提到】

: 请问版上各位google on campus面试多久能出结果？整个过程走下来，直到最后知道
: hiring decision需要多长时间？一个月够吗
: 我昨天刚面了2轮，各45分钟。下面是题目
: 1. count the number of 1s in binary representation 我用的4位4位hash的方法
: 但是没有考虑负数情况，在面试官提示下，意识到对负数向右shift,发生的是sign
: extension, 所以这题要先对输入进行检查。
: 2. remove duplicates from linked list, suppose you can use stl list. 我用的
: hash_set, 这题很顺利。
: 3. 很长很长的string/file, 要我找出中间重复次数最多的character, character set
: 可能是任何char set, unicode... 我说mapreduce, 后来面试官说如果是一台机器，8

b*h2010-11-03 07:11

19 楼

我刚才试了一下 1<<31，似乎没问题啊。x-1之后变成最大的int，即7FFF FFFF。跟x
&之后就变成0了。loop一次就停止了。
你是不是看成移位操作的那个解法了。他这个不用移位的。

【在 n******n 的大作中提到】

: 这个解法中，x如果是负数，同样会有问题。
: 因为负数向右做的是arithmetic shift, sign extension导致前面全部变成1，这样
: while(x) 这个loop never finishes
: 这就是我那天犯的错误。。。

q*82010-11-03 07:11

20 楼

关于这个问题，可以给个链接什么的吗？缺少这个的背景，看来好像是一个解决大数
据问题的通常方法？
谢谢

【在 j*****u 的大作中提到】

: 去看看map reduce你就明白了
: M个mapper，N个reducer的instance

q*82010-11-03 07:11

21 楼

关于这个问题，可以给个链接什么的吗？缺少这个的背景，看来好像是一个解决大数
据问题的通常方法？
谢谢

【在 j*****u 的大作中提到】

: 去看看map reduce你就明白了
: M个mapper，N个reducer的instance

j*u2010-11-03 07:11

22 楼

wiki http://en.wikipedia.org/wiki/Mapreduce
或者google 04年的原文：http://en.wikipedia.org/wiki/Mapreduce

【在 q******8 的大作中提到】

: 关于这个问题，可以给个链接什么的吗？缺少这个的背景，看来好像是一个解决大数
: 据问题的通常方法？
: 谢谢

b*y2010-11-03 07:11

23 楼

第一题可以先用一个unsigned的数cast一下吗。然后再按照你的hash的方法应该就可以
了。

set
，8

【在 n******n 的大作中提到】

: 请问版上各位google on campus面试多久能出结果？整个过程走下来，直到最后知道
: hiring decision需要多长时间？一个月够吗
: 我昨天刚面了2轮，各45分钟。下面是题目
: 1. count the number of 1s in binary representation 我用的4位4位hash的方法
: 但是没有考虑负数情况，在面试官提示下，意识到对负数向右shift,发生的是sign
: extension, 所以这题要先对输入进行检查。
: 2. remove duplicates from linked list, suppose you can use stl list. 我用的
: hash_set, 这题很顺利。
: 3. 很长很长的string/file, 要我找出中间重复次数最多的character, character set
: 可能是任何char set, unicode... 我说mapreduce, 后来面试官说如果是一台机器，8