Redian新闻
>
失败的Google Intern电面面经,并问找实习的心态
avatar
失败的Google Intern电面面经,并问找实习的心态# JobHunting - 待字闺中
b*p
1
1. 将一个数字的二进制形式以字符串的形式返回
2. 找两个已经排好序了的数组中的中位数(LeetCode原题)
3. 找一个字符串中最长的只含有N种不同的字符的子字符串
4. 设计题:设计一个随机数产生器,有一个以列表形式保存的已经排序blacklist,输
出的数字如果出现在其中就要剔除。(是CareerCup原题)
-----------------------------
目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能,所以本来的心
态也就是想试试看自己实习如何,没觉得有一定能通过的把握。面试前一个半月内才做
了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
本来想通过找实习来给自己有个合适的定位,如果运气好,就找点自信。
现在看来自信得从别的地方找了。看起来得再多投几家,至少把LeetCode刷完。
请问这样的心态是否正确,谢谢各位
avatar
g*e
2
现在intern题目都这么难
avatar
h*o
3
move on~
第一题就是要转换二进制码?

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

avatar
b*p
4

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

【在 h*********o 的大作中提到】
: move on~
: 第一题就是要转换二进制码?

avatar
g*4
5
请问LZ这是电面还是onsite?

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

avatar
m*l
6
第二题如果要求binary search - O(log (m+n))的话就太BT了。。
avatar
x*8
7
第二题就是变种binary search啊,我google onsite的时候被问到了,每次去掉小的头
,大的尾,排除(m+n)/2
avatar
b*p
8

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

【在 g**4 的大作中提到】
: 请问LZ这是电面还是onsite?
avatar
b*p
9

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

【在 m********l 的大作中提到】
: 第二题如果要求binary search - O(log (m+n))的话就太BT了。。
avatar
w*t
10
第四题:可以用rand()函数吗?如果在blacklist里面就继续生成下一个数?
有复杂度要求吗?

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

avatar
b*p
11

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

【在 w*****t 的大作中提到】
: 第四题:可以用rand()函数吗?如果在blacklist里面就继续生成下一个数?
: 有复杂度要求吗?

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

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

avatar
A*c
13
刚做完leetcode上的那道,感觉电面考median of two sorted arrays,够狠的。
要我比lz跪的还快:)

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

avatar
b*p
14

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

【在 M*********U 的大作中提到】
: 第一题的数字仅仅是整数吗?是否包括浮点数?
: 第三题里这个随机数产生器产生的随机数有范围吗?这个blacklist是保存在数组里还
: 是链表里?还是要你自己设计数据结构?

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

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

avatar
f*3
16
狗家的设计题就是用来黑的,不管你提出什么方案,就说不行,容易的很

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

avatar
A*c
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。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位,如果运气好,就找点自信。

avatar
P*r
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]

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

【在 P*******r 的大作中提到】
: 这道题目好像以前板上讨论过。
: blacklist 是 linkedList 可以一个一个 traverse 还算简单点。
: 如果是Array, 要求binary search 就变态了。

avatar
t*d
20
楼主,你不是面试谷歌失败,你是鄙视谷歌失败。Phd都是这样的心态,觉得自己无比
牛逼,所以一旦面试悲剧,就觉得接受不了。
avatar
w*h
21
问一下楼主,是需要在google doc上把代码写下来还是直接报思路就OK了?
avatar
r*j
22
第四题可不可以把blacklist先divide了,比如分成5000个groups,第一个group包含1-
10000范围内的blacklist里面的值,第二个group包含10001-20000范围内的blacklist
里面的值,第三个。。。
然后你每次生成一个random值,先算它是在哪个group里面,然后再去那个group里面看
有没有match。
avatar
A*c
23
给的list,怎么随机访问这些group呢?

1-
blacklist

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

avatar
b*p
24

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

【在 t******d 的大作中提到】
: 楼主,你不是面试谷歌失败,你是鄙视谷歌失败。Phd都是这样的心态,觉得自己无比
: 牛逼,所以一旦面试悲剧,就觉得接受不了。

avatar
g*4
25
intern电面都这水平了啊,狗狗真心难进啊

【在 b******p 的大作中提到】
:
: good point .......
: 反正我现在做好失败的准备了…
: 如果能有幸再多尝试几家,多收点拒信,锻炼心态也好…
: 就怕想尝试都没门啊。

avatar
b*p
26

要在Google Doc上写代码

【在 w*****h 的大作中提到】
: 问一下楼主,是需要在google doc上把代码写下来还是直接报思路就OK了?
avatar
c*p
27
mark
avatar
r*j
28
把divide之后的每个sublist一个index,每个index对应一个sublist的起点。应该可以
吧。

【在 A*********c 的大作中提到】
: 给的list,怎么随机访问这些group呢?
:
: 1-
: blacklist

avatar
b*c
29
就是第k大数,容易被median误导,其实没用

【在 A*********c 的大作中提到】
: 刚做完leetcode上的那道,感觉电面考median of two sorted arrays,够狠的。
: 要我比lz跪的还快:)

avatar
x*0
30
m
avatar
s*r
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。和板上刷了很多遍的大神们相比差太远了。
: 本来想通过找实习来给自己有个合适的定位,如果运气好,就找点自信。

avatar
A*c
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)推导出来。不知道有没有更简便的做法?

avatar
s*r
33

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

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

avatar
A*c
34
木事儿。

【在 s******r 的大作中提到】
:
: 对的,我自己想复杂了。谢谢。

avatar
t*5
35
好解法!

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

avatar
w*a
36
感谢分享面经,move on吧。
2. 找两个已经排好序了的数组中的中位数
凭良心说,这题如果之前没准备过还是有难度的。
此外,从头像来看,楼主是做graphics的?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。