new grad google， facebook电话面试面经 - 未名空间MITBBS历史存档

new grad google， facebook电话面试面经# JobHunting - 待字闺中

t*m2015-04-08 07:04

1 楼

本人fresh master，
找人内推了Facebook， amazon
自己网投了google
其中facebook和google 拿到了 phone interview
多谢版上的兄弟refer
********************面经分割线****************************
facebook只有一轮电话面试
面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
之后拿到onsite
google安排了两轮电话面试
第一轮是个三姐，LC上的insert interval类似的题，之后各种讨论follow up
第二轮是个美国人，问题是给你一个sorted的长度为N的数组，求所有数组内出现次数
超过N/4次的数字
我写出了O（N） time O（1）Space，之后面试官问我有没有更好的解法了，我说我想
不出来了
接着问了一道followup，现在给你一个time complextity O（1）的function，叫做
findCandidates（A）， return的结果是一个长度为3的数组，popular numbers是这个
数组的一个子集，问如果用这个function，能否改进time complexity。
这道题我写的时候出了个index out of range 的bug，被面试官指出，马上改过来。
最后讨论了如何test我写的这个function
一天后拿到onsite。
********************求referral分割线****************************
顺道问一句GF家的new grad onsite 如何准备，顺道求其他公司的referral，本人
leetcode两遍，lintcode两遍，之前有实习经历

y*e2015-04-08 07:04

2 楼

如果颜色超过三种怎么办
怎么办啊lz，是不是用个hashmap code一下每个颜色？

c*e2015-04-08 07:04

3 楼

counting sort?

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

: 如果颜色超过三种怎么办
: 怎么办啊lz，是不是用个hashmap code一下每个颜色？

p*o2015-04-08 07:04

4 楼

如果完全不准extra space，就只能把其中两种颜色当一种先过一遍，然后再排这两个。

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

: counting sort?

c*e2015-04-08 07:04

5 楼

所谓findCandidates（A）就是给你所有可能出现超过n/4的数？
你从sorted array里每隔1/5段，找一个数，总共4个数，是不是就相当于一个
findCandidates（A）函数？
所以本质上findCandidates（A) 并不是一个followup，而是一个提示，告诉你第一问
有sub o(n)的解？

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

: 本人fresh master，
: 找人内推了Facebook， amazon
: 自己网投了google
: 其中facebook和google 拿到了 phone interview
: 多谢版上的兄弟refer
: ********************面经分割线****************************
: facebook只有一轮电话面试
: 面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
: 之后拿到onsite
: google安排了两轮电话面试

j*32015-04-08 07:04

6 楼

mark!

T*u2015-04-08 07:04

7 楼

二轮一题可以log（n）吧

T*u2015-04-08 07:04

8 楼

从n/2开始，binary search求长度，然后break成两个at most n/2长度的数组，如果继
续从中间开始。如果长度小于n/4，停止。

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

: 二轮一题可以log（n）吧

t*m2015-04-08 07:04

9 楼

我想了一想，是这样的
不过按你说的办法，取三个数就行了

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

: 所谓findCandidates（A）就是给你所有可能出现超过n/4的数？
: 你从sorted array里每隔1/5段，找一个数，总共4个数，是不是就相当于一个
: findCandidates（A）函数？
: 所以本质上findCandidates（A) 并不是一个followup，而是一个提示，告诉你第一问
: 有sub o(n)的解？

t*m2015-04-08 07:04

10 楼

我想了一想，google第二轮的问题我没有给出最优解
确实可以O（log（n））解决
假设给定array的长度为N，那么我们就取index为N/4， N/2，3N/4的三个数为
candidates
之后以每个candidate为target对array做binary search，确定这个candidate是不是
popular
所以time complexity是O（log（N））

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

: 本人fresh master，
: 找人内推了Facebook， amazon
: 自己网投了google
: 其中facebook和google 拿到了 phone interview
: 多谢版上的兄弟refer
: ********************面经分割线****************************
: facebook只有一轮电话面试
: 面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
: 之后拿到onsite
: google安排了两轮电话面试

c*e2015-04-08 07:04

11 楼

对如果要求超过n/4（不含）的话，只要三个数

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

: 我想了一想，是这样的
: 不过按你说的办法，取三个数就行了

l*92015-04-08 07:04

12 楼

thanks

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

: 从n/2开始，binary search求长度，然后break成两个at most n/2长度的数组，如果继
: 续从中间开始。如果长度小于n/4，停止。

z*e2015-04-08 07:04

13 楼

re

个。

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

: 如果完全不准extra space，就只能把其中两种颜色当一种先过一遍，然后再排这两个。

z*e2015-04-08 07:04

14 楼

赞原创!

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

: 所谓findCandidates（A）就是给你所有可能出现超过n/4的数？
: 你从sorted array里每隔1/5段，找一个数，总共4个数，是不是就相当于一个
: findCandidates（A）函数？
: 所以本质上findCandidates（A) 并不是一个followup，而是一个提示，告诉你第一问
: 有sub o(n)的解？

c*n2015-04-08 07:04

15 楼

ft 刷了4遍啊你们还让不让人活了

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

: 本人fresh master，
: 找人内推了Facebook， amazon
: 自己网投了google
: 其中facebook和google 拿到了 phone interview
: 多谢版上的兄弟refer
: ********************面经分割线****************************
: facebook只有一轮电话面试
: 面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
: 之后拿到onsite
: google安排了两轮电话面试

c*n2015-04-08 07:04

16 楼

yeah

个。

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

: 如果完全不准extra space，就只能把其中两种颜色当一种先过一遍，然后再排这两个。

c*n2015-04-08 07:04

17 楼

worst case 当然要 o（n）。跳着试可以减少best case time

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

: 所谓findCandidates（A）就是给你所有可能出现超过n/4的数？
: 你从sorted array里每隔1/5段，找一个数，总共4个数，是不是就相当于一个
: findCandidates（A）函数？
: 所以本质上findCandidates（A) 并不是一个followup，而是一个提示，告诉你第一问
: 有sub o(n)的解？

c*n2015-04-08 07:04

18 楼

你最后 1/4N 那个 follow up 题里面提到 popular numbers 是指count 超过 1/4 的
numbers 么？

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

: 本人fresh master，
: 找人内推了Facebook， amazon
: 自己网投了google
: 其中facebook和google 拿到了 phone interview
: 多谢版上的兄弟refer
: ********************面经分割线****************************
: facebook只有一轮电话面试
: 面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
: 之后拿到onsite
: google安排了两轮电话面试

t*m2015-04-08 07:04

19 楼

worst case 其实也可以是O（log（n））。。。
看我上面的回复

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

: worst case 当然要 o（n）。跳着试可以减少best case time

t*m2015-04-08 07:04

20 楼

是的，不好意思语文是体育老师教的
已经改正！

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

: 你最后 1/4N 那个 follow up 题里面提到 popular numbers 是指count 超过 1/4 的
: numbers 么？

c*n2015-04-08 07:04

21 楼

?
if the list is just 1. to N. don't u have to inspect each element ?

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

: worst case 其实也可以是O（log（n））。。。
: 看我上面的回复

t*m2015-04-08 07:04

22 楼

array是sorted的，这个确实不容易想到，看我之前的回帖：
我想了一想，google第二轮的问题我没有给出最优解
确实可以O（log（n））解决
假设给定array的长度为N，那么我们就取index为N/4， N/2，3N/4的三个数为
candidates
之后以每个candidate为target对array做binary search，确定这个candidate是不是
popular
所以time complexity是O（log（N））

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

: ?
: if the list is just 1. to N. don't u have to inspect each element ?

r*t2015-04-08 07:04

23 楼

LZ facebook是最近电面的吗？我上个月找人内推，结果recruiter说人已经招满了，只
有whatsapp的职位了。。。

t*m2015-04-08 07:04

24 楼

半个月以前面的
你是new grad？

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

: LZ facebook是最近电面的吗？我上个月找人内推，结果recruiter说人已经招满了，只
: 有whatsapp的职位了。。。

n*n2015-04-08 07:04

25 楼

popular number candidate就是位置1/4，1/2，3/4的数啊。然后equal range

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

: 本人fresh master，
: 找人内推了Facebook， amazon
: 自己网投了google
: 其中facebook和google 拿到了 phone interview
: 多谢版上的兄弟refer
: ********************面经分割线****************************
: facebook只有一轮电话面试
: 面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
: 之后拿到onsite
: google安排了两轮电话面试