f*******7
发帖数: 943 | 1 之前已经面了三轮电话面试，题目也贴出来了。
本来说的是onsite，结果最后改成了4 轮Skype Interview
一
[1, 2, 3] => false
[1, 2, 3, 2] => true
[1, 2, 3, 2, 3] => false
[1, 2, 3, 4, 4, 4, 5, 5, 5] => false
Given an integer array, determine whether there exists an element such that
the number of occurrences of the element strictly exceeds the number of
occurrences of any other element.
中间还问了很多细节问题， 比如HashMap， Heap 等
最让我摸不到头脑的问题， heap的两个属性？？？ 我说了一堆，也没答到点上，最终
的答案是
1) binary tree 构成
2) the relation between the upper level and lower level node (e.g. upper
level node is always greater than lower level for max heap)
二
pow(x, y) 写完之后那三哥问我为啥这么做。。。
// Given a string with missing spaces "FindaString", divide into words i.e.
"Find", "a", "String"
e.g.字典里可能有
Find
a
String
Finda
HelloWorld
boolean isDictionaryWord(String word);
我用recursive 做的， 写完了后人家说还有更好的方法， 但是你没时间了。。。
三。 美女manager
wordladder 2
设计题： facebook 查找好友功能， 很广泛，但最后的时候有一个具体问题我感觉很
有意思
**假设在一个服务器高峰时间，来的查询量很大，你怎么handle （注意，已经具体是
一个服务器了） 我说的是1. 根据user active 程度，划分priority， 然后delay low
priority user request 2. 根据request cost， 决定priority
四。 。。。 美女manager 跟我说第四个人不来了，看他们能不能找个替代的人， 让
我在电脑前等着。
后来recruiter发信，说不面了，他收集反馈，如果反馈好， 继续给我安排，如果不好
。。。
总结， 整个过程网络连接很差，总断， 一直在电话与skype 交换着， 而且貌似他家
电话也是voip的，根本听不清。。。
事后我想着肯定要挂了，所以就给recruiter打了个电话，反映了下情况。 虽然我就这
么回事了，但是也得让人家知道你们这么弄skype interview 实际上比面对面的效果要
差很多，他说他们也在一直trying to improve the interview experience.
希望对之后面试他家的同学有帮助。
***********************************
UPDATE：已收到正式拒信。
除了第二个三哥的第二道题没给出他要求的最优解， 其他的问题都是bug free，也挂
了。 | s***y
发帖数: 203 | | p*****p
发帖数: 379 | 3 感觉对于ebay这个级别来说题偏难啊，感觉有故意卡人的倾向 | p****e
发帖数: 3548 | | n**m
发帖数: 122 | 5 感谢分享先
**假设在一个服务器高峰时间，来的查询量很大，你怎么handle （注意，已经具体是
一个服务器了） 我说的是1. 根据user active 程度，划分priority， 然后delay low
priority user request 2. 根据request cost， 决定priority
-------------------------------------------------------
我的一点想法，既然是设计题，已经是一个服务器了也不排除可以转发到其他服务器上
去处理吧
另外我认为用user active 程度来划分priority的策略不太好，有失公平性，不如FIFO
从另一个方面想,本来active程度不高的user好不容易来用了一把却体验一把最糟糕的
响应速度，下次他还会来吗? | x*****0
发帖数: 452 | | f********x
发帖数: 2086 | | r*******6
发帖数: 99 | 8 divide word那个题如果有不止一种的divide方法就要recursion吧。。。
that
【在 f*******7 的大作中提到】
: 之前已经面了三轮电话面试，题目也贴出来了。
: 本来说的是onsite，结果最后改成了4 轮Skype Interview
: 一
: [1, 2, 3] => false
: [1, 2, 3, 2] => true
: [1, 2, 3, 2, 3] => false
: [1, 2, 3, 4, 4, 4, 5, 5, 5] => false
: Given an integer array, determine whether there exists an element such that
: the number of occurrences of the element strictly exceeds the number of
: occurrences of any other element.
| y*******o
发帖数: 6632 | 9 memory cache, multithreading, batch operation,
add more machine, more cpu? 异步查询
low
FIFO
【在 n**m 的大作中提到】
: 感谢分享先
: **假设在一个服务器高峰时间，来的查询量很大，你怎么handle （注意，已经具体是
: 一个服务器了） 我说的是1. 根据user active 程度，划分priority， 然后delay low
: priority user request 2. 根据request cost， 决定priority
: -------------------------------------------------------
: 我的一点想法，既然是设计题，已经是一个服务器了也不排除可以转发到其他服务器上
: 去处理吧
: 另外我认为用user active 程度来划分priority的策略不太好，有失公平性，不如FIFO
: 从另一个方面想,本来active程度不高的user好不容易来用了一把却体验一把最糟糕的
: 响应速度，下次他还会来吗?
| f*******7
发帖数: 943 | 10 这些方法我在之前的讨论都说了，然后她继续细化出这个问题了
【在 y*******o 的大作中提到】
: memory cache, multithreading, batch operation,
: add more machine, more cpu? 异步查询
:
: low
: FIFO
| | | f*******7
发帖数: 943 | 11 之前讨论过distribution了 这是细化之后的问题，如果我继续答distribution，那就
将对话又循环回去了
low
【在 n**m 的大作中提到】
: 感谢分享先
: **假设在一个服务器高峰时间，来的查询量很大，你怎么handle （注意，已经具体是
: 一个服务器了） 我说的是1. 根据user active 程度，划分priority， 然后delay low
: priority user request 2. 根据request cost， 决定priority
: -------------------------------------------------------
: 我的一点想法，既然是设计题，已经是一个服务器了也不排除可以转发到其他服务器上
: 去处理吧
: 另外我认为用user active 程度来划分priority的策略不太好，有失公平性，不如FIFO
: 从另一个方面想,本来active程度不高的user好不容易来用了一把却体验一把最糟糕的
: 响应速度，下次他还会来吗?
| c*****4
发帖数: 1777 | 12 第一题应该先排序。排序后只用三个变量计数就行了。是O(n)。其实考算法绝大多数最
终都是如何排序。不要想得太复杂。
第三个不知道怎么递归，是不是两个指针就行了，一个指着头，一个指着当前位置，如
是词则输出，然后头指到当前的下一个位置。至少比递归少用一个栈。
最后一个我没有用过fb，不过对查询量大的问题一般的解决方案是cache结果。因为查
询量大，命中的机会也多。
抛砖引玉
另，你面试的是什么Level的？L2还是L3。感觉不是L4的题。
that
【在 f*******7 的大作中提到】
: 之前已经面了三轮电话面试，题目也贴出来了。
: 本来说的是onsite，结果最后改成了4 轮Skype Interview
: 一
: [1, 2, 3] => false
: [1, 2, 3, 2] => true
: [1, 2, 3, 2, 3] => false
: [1, 2, 3, 4, 4, 4, 5, 5, 5] => false
: Given an integer array, determine whether there exists an element such that
: the number of occurrences of the element strictly exceeds the number of
: occurrences of any other element.
| t**********r
发帖数: 2153 | 13 不用排序。直接从输入建立二叉树。排序的复杂度怎么也是nlgn
★ 发自iPhone App: ChineseWeb 7.8
【在 c*****4 的大作中提到】
: 第一题应该先排序。排序后只用三个变量计数就行了。是O(n)。其实考算法绝大多数最
: 终都是如何排序。不要想得太复杂。
: 第三个不知道怎么递归，是不是两个指针就行了，一个指着头，一个指着当前位置，如
: 是词则输出，然后头指到当前的下一个位置。至少比递归少用一个栈。
: 最后一个我没有用过fb，不过对查询量大的问题一般的解决方案是cache结果。因为查
: 询量大，命中的机会也多。
: 抛砖引玉
: 另，你面试的是什么Level的？L2还是L3。感觉不是L4的题。
:
: that
| l****i
发帖数: 2772 | 14 请问，为什么要建立二叉树？用一个hashtable就能搞定吧。
【在 t**********r 的大作中提到】
: 不用排序。直接从输入建立二叉树。排序的复杂度怎么也是nlgn
:
: ★ 发自iPhone App: ChineseWeb 7.8
| f*******7
发帖数: 943 | 15 这么做cover不了这个case
字典: fi, a, string, find
因为遍历的时候第一次找到fi，但是后面的永远找不到了，所以我现在也没想出o(n)的
解法，动态规划？
这个职位应该是fresh master level的职位
———————————————————— | c*****4
发帖数: 1777 | 16 不用想了，如果字典这样，要知道所有的词，还要搞LR什么的语法分析树，1个小时都
做不出来。而且不会是O(n)。L2不用想得太复杂。
挂了也不要紧，见工就是被羞辱的过程。见多了经验就来了。我觉得见之前他们压根就
没打算要你。这需要运气，你以为全部都打不出来，也可能有offer。
【在 f*******7 的大作中提到】
: 这么做cover不了这个case
: 字典: fi, a, string, find
: 因为遍历的时候第一次找到fi，但是后面的永远找不到了，所以我现在也没想出o(n)的
: 解法，动态规划？
: 这个职位应该是fresh master level的职位
: ————————————————————
| c*****4
发帖数: 1777 | 17 他们考的是算法，不是解决方案。硅谷的人个个“dream big”，其实美国才几号人，
一个PC server就能把全美国人的信息装进去。他们以为自己都是“大数据”。你要是
回答hashtable就铁定没戏了。这也是面试经验。
【在 l****i 的大作中提到】
: 请问，为什么要建立二叉树？用一个hashtable就能搞定吧。
| c*****4
发帖数: 1777 | 18 建二叉树的过程就是等于排序的过程吧？建二叉树需要额外的空间。对面试者而言方案
不够优化。我觉得面试者希望你回答快速排序，无需额外的空间。他们会说如果是大数
据，你没有足够的存储空间缓存所需的数据。举例说这个序列可以是1万亿个。
如果是谷歌面试，或者是L4面试，在大数据情况下有些特殊的近似算法（因为谷歌用得
最多，因为谷歌的数据”比较大“）。在多少置信度下返回值（真／假）是正确的。大
数据排序不现实。
【在 t**********r 的大作中提到】
: 不用排序。直接从输入建立二叉树。排序的复杂度怎么也是nlgn
:
: ★ 发自iPhone App: ChineseWeb 7.8
| c*****4
发帖数: 1777 | 19 最后一题想起来了，你是L2不超过L3，她可能想你回答：
如果流量大就加机器。
和算法无关。这是真人真事eBay搜索team面试的答案。变态吧。
that
【在 f*******7 的大作中提到】
: 之前已经面了三轮电话面试，题目也贴出来了。
: 本来说的是onsite，结果最后改成了4 轮Skype Interview
: 一
: [1, 2, 3] => false
: [1, 2, 3, 2] => true
: [1, 2, 3, 2, 3] => false
: [1, 2, 3, 4, 4, 4, 5, 5, 5] => false
: Given an integer array, determine whether there exists an element such that
: the number of occurrences of the element strictly exceeds the number of
: occurrences of any other element.
| l****i
发帖数: 2772 | 20 第一题，难道不是考算法，写code么？为什么不能用hashtable？没看懂你说的意思。
【在 c*****4 的大作中提到】
: 他们考的是算法，不是解决方案。硅谷的人个个“dream big”，其实美国才几号人，
: 一个PC server就能把全美国人的信息装进去。他们以为自己都是“大数据”。你要是
: 回答hashtable就铁定没戏了。这也是面试经验。
| | | t**********r
发帖数: 2153 | 21 嗯，hash也可以。我只是说不用排序。
★ 发自iPhone App: ChineseWeb 7.8
【在 l****i 的大作中提到】
: 请问，为什么要建立二叉树？用一个hashtable就能搞定吧。
| t**********r
发帖数: 2153 | 22 排序一样需要额外空间的。这道题排序没有起到任何作用。二叉树还能压缩点数据量。
其实楼上说的hash是个不错的法子。
★ 发自iPhone App: ChineseWeb 7.8
【在 c*****4 的大作中提到】
: 建二叉树的过程就是等于排序的过程吧？建二叉树需要额外的空间。对面试者而言方案
: 不够优化。我觉得面试者希望你回答快速排序，无需额外的空间。他们会说如果是大数
: 据，你没有足够的存储空间缓存所需的数据。举例说这个序列可以是1万亿个。
: 如果是谷歌面试，或者是L4面试，在大数据情况下有些特殊的近似算法（因为谷歌用得
: 最多，因为谷歌的数据”比较大“）。在多少置信度下返回值（真／假）是正确的。大
: 数据排序不现实。
| y******e
发帖数: 8 | 23 我想问第一题到底有没有什么tricky的东西？ 一般容易想到的用hashtable就是O(N)的
复杂度，但需要额外空间。 如果用排序（比如快排这种in place排序），那不用额外
空间，但复杂度至少也是O(NlogN)。 有更好的O（n）并且constant space的算法吗？ | f*******7
发帖数: 943 | 24 第一题的tricky不在题本身，而是在于边写题的时候提到什么datastructure，面试官
就会问你这个data structure相关的东西，问的很深。边写边问，边问边写。思路不要
被打乱最重要，而且有时他们会故意说你说的办法不可行，那你就得说服他们为什么这
么用。
所以以后建议大家做题的时候要多思考，每一个细小的步骤都是。而不是说拿做题速度
做为一种对自己的挑战。
【在 y******e 的大作中提到】
: 我想问第一题到底有没有什么tricky的东西？ 一般容易想到的用hashtable就是O(N)的
: 复杂度，但需要额外空间。 如果用排序（比如快排这种in place排序），那不用额外
: 空间，但复杂度至少也是O(NlogN)。 有更好的O（n）并且constant space的算法吗？
| b*******l
发帖数: 590 | 25 楼主好RP，每次面经都写出来。BLESS楼主马上拿到大OFFER！
另，eBay好变态啊。 |
|
