t****m
发帖数: 140 | 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*****e
发帖数: 712 | 2 如果颜色超过三种怎么办
怎么办啊lz，是不是用个hashmap code一下每个颜色？ |
c*******e
发帖数: 621 | 3 counting sort?
【在 y*****e 的大作中提到】
: 如果颜色超过三种怎么办
: 怎么办啊lz，是不是用个hashmap code一下每个颜色？
|
p******o
发帖数: 125 | 4 如果完全不准extra space，就只能把其中两种颜色当一种先过一遍，然后再排这两个。
【在 c*******e 的大作中提到】
: counting sort?
|
c*******e
发帖数: 621 | 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**********3
发帖数: 3211 | |
T*****u
发帖数: 7103 | |
T*****u
发帖数: 7103 | 8 从n/2开始，binary search求长度，然后break成两个at most n/2长度的数组，如果继
续从中间开始。如果长度小于n/4，停止。
【在 T*****u 的大作中提到】
: 二轮一题可以log（n）吧
|
t****m
发帖数: 140 | 9 我想了一想，是这样的
不过按你说的办法，取三个数就行了
【在 c*******e 的大作中提到】
: 所谓findCandidates（A）就是给你所有可能出现超过n/4的数？
: 你从sorted array里每隔1/5段，找一个数，总共4个数，是不是就相当于一个
: findCandidates（A）函数？
: 所以本质上findCandidates（A) 并不是一个followup，而是一个提示，告诉你第一问
: 有sub o(n)的解？
|
t****m
发帖数: 140 | 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*******e
发帖数: 621 | 11 对 如果要求超过n/4（不含）的话，只要三个数
【在 t****m 的大作中提到】
: 我想了一想，是这样的
: 不过按你说的办法，取三个数就行了
|
l**********9
发帖数: 537 | 12 thanks
【在 T*****u 的大作中提到】
: 从n/2开始，binary search求长度，然后break成两个at most n/2长度的数组，如果继
: 续从中间开始。如果长度小于n/4，停止。
|
z***e
发帖数: 209 | 13 re
个。
【在 p******o 的大作中提到】
: 如果完全不准extra space，就只能把其中两种颜色当一种先过一遍，然后再排这两个。
|
z***e
发帖数: 209 | 14 赞原创!
【在 c*******e 的大作中提到】
: 所谓findCandidates（A）就是给你所有可能出现超过n/4的数？
: 你从sorted array里每隔1/5段，找一个数，总共4个数，是不是就相当于一个
: findCandidates（A）函数？
: 所以本质上findCandidates（A) 并不是一个followup，而是一个提示，告诉你第一问
: 有sub o(n)的解？
|
c******n
发帖数: 4965 | 15 ft 刷了4遍啊 你们还让不让人活了
【在 t****m 的大作中提到】
: 本人fresh master，
: 找人内推了Facebook， amazon
: 自己网投了google
: 其中facebook和google 拿到了 phone interview
: 多谢版上的兄弟refer
: ********************面经分割线****************************
: facebook只有一轮电话面试
: 面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
: 之后拿到onsite
: google安排了两轮电话面试
|
c******n
发帖数: 4965 | 16 yeah
个。
【在 p******o 的大作中提到】
: 如果完全不准extra space，就只能把其中两种颜色当一种先过一遍，然后再排这两个。
|
c******n
发帖数: 4965 | 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******n
发帖数: 4965 | 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****m
发帖数: 140 | 19 worst case 其实也可以是O（log（n））。。。
看我上面的回复
【在 c******n 的大作中提到】
: worst case 当然要 o（n）。 跳着试可以减少best case time
|
t****m
发帖数: 140 | 20 是的，不好意思语文是体育老师教的
已经改正！
【在 c******n 的大作中提到】
: 你最后 1/4N 那个 follow up 题里面 提到 popular numbers 是指count 超过 1/4 的
: numbers 么？
|
|
|
c******n
发帖数: 4965 | 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****m
发帖数: 140 | 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*****t
发帖数: 8 | 23 LZ facebook是最近电面的吗？我上个月找人内推，结果recruiter说人已经招满了，只
有whatsapp的职位了。。。 |
t****m
发帖数: 140 | 24 半个月以前面的
你是new grad？
【在 r*****t 的大作中提到】
: LZ facebook是最近电面的吗？我上个月找人内推，结果recruiter说人已经招满了，只
: 有whatsapp的职位了。。。
|
n******n
发帖数: 12088 | 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安排了两轮电话面试
|
