b******y
发帖数: 660 | 1 比较郁闷最近的几个公司的onsite都不能一天完成，两轮onsite真是累人。
由于NDA的缘故，不方便报得太具体。要具体讨论请pm。
报一下今天SF某著名网络公司的onsite。
面了５个人，最重要几个leader从３点开始开会，估计还得再去一趟（如果他们觉得我
前面面的还行的话）。不过有幸面到的第五个是创始人之一 ！
几乎每个面试都问到我做过的十分match他们的一个小project，其实就是一个final
project，幸好还算interesting。下面聊聊问到的技术问题。
１）测试一个stack（给出接口）；实现这个stack
２）找两个已排序数组的交集
一步步优化，最后要做到比mlogn更好。
３）优化我project当中的一个n＾２的算法
４）很多机器，每个机器都有一个log（一系列的访问记录，每行是一个网站名）。要
求这些机器当中的访问最多的前K个网站。 |
l*****a
发帖数: 14598 | 2 for question2)
since it is already sorted,definitely use O(m+n)
【在 b******y 的大作中提到】
: 比较郁闷最近的几个公司的onsite都不能一天完成，两轮onsite真是累人。
: 由于NDA的缘故，不方便报得太具体。要具体讨论请pm。
: 报一下今天SF某著名网络公司的onsite。
: 面了５个人，最重要几个leader从３点开始开会，估计还得再去一趟（如果他们觉得我
: 前面面的还行的话）。不过有幸面到的第五个是创始人之一 ！
: 几乎每个面试都问到我做过的十分match他们的一个小project，其实就是一个final
: project，幸好还算interesting。下面聊聊问到的技术问题。
: １）测试一个stack（给出接口）；实现这个stack
: ２）找两个已排序数组的交集
: 一步步优化，最后要做到比mlogn更好。
|
b******y
发帖数: 660 | 3 question 2)
There are different cases to discuss.
when n is huge and m is small, mlogn is better then m+n; in the same case,
there is way to do better than mlogn |
l*****a
发帖数: 14598 | 4 u r right
i didnot think much
case,
【在 b******y 的大作中提到】
: question 2)
: There are different cases to discuss.
: when n is huge and m is small, mlogn is better then m+n; in the same case,
: there is way to do better than mlogn
|
c****o
发帖数: 41 | 5
case,
my 2 cents：当在里面二分找m的元素时，记下m里每一个元素m[x]在n的位置，然后找m
里下一个元
素m[x+1]的位置时，二分上界可以用m[x]在n里的位置，这样能比从n的两头开始二分快
一些。
更好的办法还没想到。。。
【在 b******y 的大作中提到】
: question 2)
: There are different cases to discuss.
: when n is huge and m is small, mlogn is better then m+n; in the same case,
: there is way to do better than mlogn
|
g*****x
发帖数: 799 | 6 第四题
step1: 先每个机器算网站的浏览次数的list
step2: 把Ni(第i台机器log中出现所有不同网站的个数)发到central server上
step3: 找出list最短的一半的机器，把它们的list传到list较长的那一半机器上合并
list（可用第二题中的算法，囧）。。。并行处理
step4: 然后算好的再把合并完的list再循环按step2, step3处理，直到最后完全合并
成一个list，得到最大的K个
不知道还有什么比较好的方法 |
G****o
发帖数: 155 | 7 k-merge sort, and max-heap ?
【在 g*****x 的大作中提到】
: 第四题
: step1: 先每个机器算网站的浏览次数的list
: step2: 把Ni(第i台机器log中出现所有不同网站的个数)发到central server上
: step3: 找出list最短的一半的机器，把它们的list传到list较长的那一半机器上合并
: list（可用第二题中的算法，囧）。。。并行处理
: step4: 然后算好的再把合并完的list再循环按step2, step3处理，直到最后完全合并
: 成一个list，得到最大的K个
: 不知道还有什么比较好的方法
|
i******i
发帖数: 502 | 8 问下lz，为什么要2次onsite啊？
2次onsite是同一组人还是不同的人来面啊。
还有如果第一次是技术问题，那第2次还会是技术的么？ |
b******y
发帖数: 660 | |
b******y
发帖数: 660 | 10
找m
This is what they expect :-)
【在 c****o 的大作中提到】
:
: case,
: my 2 cents：当在里面二分找m的元素时，记下m里每一个元素m[x]在n的位置，然后找m
: 里下一个元
: 素m[x+1]的位置时，二分上界可以用m[x]在n里的位置，这样能比从n的两头开始二分快
: 一些。
: 更好的办法还没想到。。。
|
