失败的Google Intern电面面经，并问找实习的心态 - 未名空间MITBBS历史存档

失败的Google Intern电面面经，并问找实习的心态# JobHunting - 待字闺中

b*p2013-12-17 08:12

1 楼

1. 将一个数字的二进制形式以字符串的形式返回
2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
3. 找一个字符串中最长的只含有N种不同的字符的子字符串
4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
出的数字如果出现在其中就要剔除。（是CareerCup原题）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
现在看来自信得从别的地方找了。看起来得再多投几家，至少把LeetCode刷完。
请问这样的心态是否正确，谢谢各位

g*e2013-12-17 08:12

2 楼

现在intern题目都这么难

h*o2013-12-17 08:12

3 楼

move on~
第一题就是要转换二进制码？

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

b*p2013-12-17 08:12

4 楼

对。就是类似python里面的
str(bin(N))
这样子的

【在 h*********o 的大作中提到】

: move on~
: 第一题就是要转换二进制码？

g*42013-12-17 08:12

5 楼

请问LZ这是电面还是onsite？

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

m*l2013-12-17 08:12

6 楼

第二题如果要求binary search - O(log (m+n))的话就太BT了。。

x*82013-12-17 08:12

7 楼

第二题就是变种binary search啊，我google onsite的时候被问到了，每次去掉小的头
，大的尾，排除（m+n)/2

b*p2013-12-17 08:12

8 楼

这是电面，是一共两场，每场45分钟，开始时间相差一小时的

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

: 请问LZ这是电面还是onsite？

b*p2013-12-17 08:12

9 楼

这题我在leetcode里面做过
我现在觉得我应该是挂在了最后一题
最后一题我之前没做到过，面试官也没让我写程序。
我只解释了我怎么想的，解释到后来他一直说我的做法没有满足他的要求。
估计是因此被拒掉了
再加上第三题写的可能还有bug…

【在 m********l 的大作中提到】

: 第二题如果要求binary search - O(log (m+n))的话就太BT了。。

w*t2013-12-17 08:12

10 楼

第四题：可以用rand()函数吗？如果在blacklist里面就继续生成下一个数？
有复杂度要求吗？

【在 b******p 的大作中提到】

:
: 这题我在leetcode里面做过
: 我现在觉得我应该是挂在了最后一题
: 最后一题我之前没做到过，面试官也没让我写程序。
: 我只解释了我怎么想的，解释到后来他一直说我的做法没有满足他的要求。
: 估计是因此被拒掉了
: 再加上第三题写的可能还有bug…

b*p2013-12-17 08:12

11 楼

这题我完全没做出来
面试官没让我写code，我就和他说了，建一个hash table，或是建一个bloom filter之类
他说这些不行，又补充说：
blacklist是一个链表，所以二分查找的代价和数组的二分查找不一样
他说要“incremental”的解法
也就是将整个blacklist读入，再建hash table的方法通通不行
他说，譬如blacklist里面有几百万个数怎么办？几百万个数就是~400MB，超过了CPU的
缓存的大小。如果建hash table，性能会损失非常大。所以，我说的方法全都错误，不
是他想要的。估计是因此被拒了。
后来才知道这个是CareerCup 12.3这道题目。
没做过，真该面壁思过去…

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

: 第四题：可以用rand()函数吗？如果在blacklist里面就继续生成下一个数？
: 有复杂度要求吗？

M*U2013-12-17 08:12

12 楼

第一题的数字仅仅是整数吗？是否包括浮点数？
第三题里这个随机数产生器产生的随机数有范围吗？这个blacklist是保存在数组里还
是链表里？还是要你自己设计数据结构？

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

A*c2013-12-17 08:12

13 楼

刚做完leetcode上的那道，感觉电面考median of two sorted arrays，够狠的。
要我比lz跪的还快：）

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

b*p2013-12-17 08:12

14 楼

第一题是整数
第三题是在链表里，排好序的

【在 M*********U 的大作中提到】

: 第一题的数字仅仅是整数吗？是否包括浮点数？
: 第三题里这个随机数产生器产生的随机数有范围吗？这个blacklist是保存在数组里还
: 是链表里？还是要你自己设计数据结构？

A*c2013-12-17 08:12

15 楼

看了你的面经以后我赶快做了CC的12.3, 做完以后觉得和你这个不是一道题啊。
解法应该是不一样的啊。

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

f*32013-12-17 08:12

16 楼

狗家的设计题就是用来黑的，不管你提出什么方案，就说不行，容易的很

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

A*c2013-12-17 08:12

17 楼

没忍住想了一下第四题，上网搜了一下相关信息，学了一个算法。
造福一下大家，写这儿吧。
问题定义应该是这样的，要求生成[1, n], 给个blacklist是禁止的数字, list是排序
好的。
生成算法如下:
1 生成随机数 r in range [1, n-len(blacklist)]
2: 带着这个数字linear scan blacklist，如果生成的的数字大于等于list的当前元素
，则把生成的结果加1。
算法很简单，但是没找到信息证明正确性。我琢磨了一下是正确的，并且是uniform。
举例如下：假设要求生成[1, 10]
例子1. list 是1->2。所生成随机数1－8，然后显然要增加两次，所以最后随机数生成
器的range本质上就是3～10. uniform。
例子2. list 是9->10. 生成的随机数1～8. 显然不跳。最后的的range就是1～8，
uniform
例子3 list是1->3 生成1～8. 如果生成的是1 (这个概率本身是1/8)，碰到1跳一下，
到2，没问题，如果生成的是 >=2的数字，则需要跳两下，本质上是取的(4~10) （这个
概率是7/8) 所以你算一下最终概率还是uniform 在 2还有4~10之间分布。
希望对大伙有点用。
这个算法真神童。

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

P*r2013-12-17 08:12

18 楼

这道题目好像以前板上讨论过。
blacklist 是 linkedList 可以一个一个 traverse 还算简单点。
如果是Array, 要求binary search 就变态了。

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

: 没忍住想了一下第四题，上网搜了一下相关信息，学了一个算法。
: 造福一下大家，写这儿吧。
: 问题定义应该是这样的，要求生成[1, n], 给个blacklist是禁止的数字, list是排序
: 好的。
: 生成算法如下:
: 1 生成随机数 r in range [1, n-len(blacklist)]
: 2: 带着这个数字linear scan blacklist，如果生成的的数字大于等于list的当前元素
: ，则把生成的结果加1。
: 算法很简单，但是没找到信息证明正确性。我琢磨了一下是正确的，并且是uniform。
: 举例如下：假设要求生成[1, 10]

A*c2013-12-17 08:12

19 楼

有意思，想想。胡说一下啊。
先做一次binary search，找到lower bound。看前面有几个元素，然后把生成数加几。
然后没完，更新binary search的lower bound继续search，重复，直到binary search
返回的结果是－1为止。如何？
binary search外面套一层。

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

: 这道题目好像以前板上讨论过。
: blacklist 是 linkedList 可以一个一个 traverse 还算简单点。
: 如果是Array, 要求binary search 就变态了。

t*d2013-12-17 08:12

20 楼

楼主，你不是面试谷歌失败，你是鄙视谷歌失败。Phd都是这样的心态，觉得自己无比
牛逼，所以一旦面试悲剧，就觉得接受不了。

w*h2013-12-17 08:12

21 楼

问一下楼主，是需要在google doc上把代码写下来还是直接报思路就OK了？

r*j2013-12-17 08:12

22 楼

第四题可不可以把blacklist先divide了，比如分成5000个groups，第一个group包含1-
10000范围内的blacklist里面的值，第二个group包含10001-20000范围内的blacklist
里面的值，第三个。。。
然后你每次生成一个random值，先算它是在哪个group里面，然后再去那个group里面看
有没有match。

A*c2013-12-17 08:12

23 楼

给的list，怎么随机访问这些group呢？

1-
blacklist

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

: 第四题可不可以把blacklist先divide了，比如分成5000个groups，第一个group包含1-
: 10000范围内的blacklist里面的值，第二个group包含10001-20000范围内的blacklist
: 里面的值，第三个。。。
: 然后你每次生成一个random值，先算它是在哪个group里面，然后再去那个group里面看
: 有没有match。

b*p2013-12-17 08:12

24 楼

good point .......
反正我现在做好失败的准备了…
如果能有幸再多尝试几家，多收点拒信，锻炼心态也好…
就怕想尝试都没门啊。

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

: 楼主，你不是面试谷歌失败，你是鄙视谷歌失败。Phd都是这样的心态，觉得自己无比
: 牛逼，所以一旦面试悲剧，就觉得接受不了。

g*42013-12-17 08:12

25 楼

intern电面都这水平了啊，狗狗真心难进啊

【在 b******p 的大作中提到】

:
: good point .......
: 反正我现在做好失败的准备了…
: 如果能有幸再多尝试几家，多收点拒信，锻炼心态也好…
: 就怕想尝试都没门啊。

b*p2013-12-17 08:12

26 楼

要在Google Doc上写代码

【在 w*****h 的大作中提到】

: 问一下楼主，是需要在google doc上把代码写下来还是直接报思路就OK了？

c*p2013-12-17 08:12

27 楼

mark

r*j2013-12-17 08:12

28 楼

把divide之后的每个sublist一个index，每个index对应一个sublist的起点。应该可以
吧。

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

: 给的list，怎么随机访问这些group呢？
:
: 1-
: blacklist

b*c2013-12-17 08:12

29 楼

就是第k大数，容易被median误导，其实没用

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

: 刚做完leetcode上的那道，感觉电面考median of two sorted arrays，够狠的。
: 要我比lz跪的还快：）

x*02013-12-17 08:12

30 楼

m

s*r2013-12-17 08:12

31 楼

想向大家请教一下，第三道题目的意思是什么，什么解法比较好。
对于题意，我的理解是，给一个参数N，找出字符串里面只包含N个不同字符的个数。譬
如N=1，那么在字符串"AAAAAA"里面，包含一个不同字符的最长串是6。不知道我理解的
是不是正确？
如果理解正确的话，有什么比较好的解法？我现在能够想到的是O(N^2)。就是用张二维
表，记录所有区间(i,j)之间不同字符串的个数，(i,j+1)的值可以从（i+1，j), (i, j
) 和(i+1, j+1)推导出来。不知道有没有更简便的做法？

【在 b******p 的大作中提到】

: 1. 将一个数字的二进制形式以字符串的形式返回
: 2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
: 3. 找一个字符串中最长的只含有N种不同的字符的子字符串
: 4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
: 出的数字如果出现在其中就要剔除。（是CareerCup原题）
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: 目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
: 态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
: 了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。

A*c2013-12-17 08:12

32 楼

用slide window应该可以得到一个O(n)的算法。
记录当前的window 开始。当前指针位置是窗口的结束点。
每当碰到一个新的字符把N变成了N+1以后，更新当前最大长度，然后把窗口前移，一个
一个去掉字符，直到N这个constraint被满足为止，然后继续滑动窗口的结束位置。
循环上述过程直到字符串末尾。

j

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

:
: 想向大家请教一下，第三道题目的意思是什么，什么解法比较好。
: 对于题意，我的理解是，给一个参数N，找出字符串里面只包含N个不同字符的个数。譬
: 如N=1，那么在字符串"AAAAAA"里面，包含一个不同字符的最长串是6。不知道我理解的
: 是不是正确？
: 如果理解正确的话，有什么比较好的解法？我现在能够想到的是O(N^2)。就是用张二维
: 表，记录所有区间(i,j)之间不同字符串的个数，(i,j+1)的值可以从（i+1，j), (i, j
: ) 和(i+1, j+1)推导出来。不知道有没有更简便的做法？

s*r2013-12-17 08:12

33 楼

对的，我自己想复杂了。谢谢。

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

: 用slide window应该可以得到一个O(n)的算法。
: 记录当前的window 开始。当前指针位置是窗口的结束点。
: 每当碰到一个新的字符把N变成了N+1以后，更新当前最大长度，然后把窗口前移，一个
: 一个去掉字符，直到N这个constraint被满足为止，然后继续滑动窗口的结束位置。
: 循环上述过程直到字符串末尾。
:
: j

A*c2013-12-17 08:12

34 楼

木事儿。

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

:
: 对的，我自己想复杂了。谢谢。

t*52013-12-17 08:12

35 楼

好解法！

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

: 没忍住想了一下第四题，上网搜了一下相关信息，学了一个算法。
: 造福一下大家，写这儿吧。
: 问题定义应该是这样的，要求生成[1, n], 给个blacklist是禁止的数字, list是排序
: 好的。
: 生成算法如下:
: 1 生成随机数 r in range [1, n-len(blacklist)]
: 2: 带着这个数字linear scan blacklist，如果生成的的数字大于等于list的当前元素
: ，则把生成的结果加1。
: 算法很简单，但是没找到信息证明正确性。我琢磨了一下是正确的，并且是uniform。
: 举例如下：假设要求生成[1, 10]

w*a2013-12-17 08:12

36 楼

感谢分享面经，move on吧。
2. 找两个已经排好序了的数组中的中位数
凭良心说，这题如果之前没准备过还是有难度的。
此外，从头像来看，楼主是做graphics的？