eBay 电面

今天电面了eBay，两轮电面。直接上题。
第一轮：
1. Binary Tree Level Order
2. a. how to get top 10 frequent words in a small file?
    b. how to get top 10 frequent words in a

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ether one binary tree is a binary search tree?

第一轮的第二题挺有意思的，尤其是最后一个问，希望听听大家的解法。

tianyangche 发表于 2014-8-12 06:35
我是那么答的，但是这个不是很好，面试官不满意。
他给的解法是：用一个双链表和一个hashmap……

类似LRU链表的这个解法有问题。不能求得准确的最大值，跟LRU的大小有关。
比如我们用一个长度为 2 的 LRU来统计一个输入 stream = 1, 2, 2, 3, 3, 1, 4, 4, 5, 5 ...
注意到 1 是周期性出现的但是在每一个周期内 1 都不是最频繁的数，所以长度为2的LRU只能记录当前周期内出现最频繁的两个数{2,3}，{3,4}, {4,5}。 这样每个周期内 “1” 出现的次数都不会被累计，而实际上最频繁出现的是这个 “1”。
也就是说形如上述输入序列，如果其周期间隔大于LRU容量，就无法统计到正确的最大值。

zhenggao1986 发表于 2014-8-10 13:55
Stream的那个还是维护一个N的小顶堆吧

我是那么答的，但是这个不是很好，面试官不满意。
他给的解法是：用一个双链表和一个hashmap……

关于第一题的第二轮，在geeksforgeeks上看到一个解法，用Trie and Min Heap，觉得挺好的：

http://www.geeksforgeeks.org/fin ... -words-from-a-file/

比用双联表和hashmap好。

能具体说下设计题么???

readman 发表于 2014-7-10 09:03
能具体说下设计题么???

是问我之前做过的一个项目，不是那种OO design 的题

Stream的那个还是维护一个N的小顶堆吧

感谢上题！能再上解答么

一剑终情 发表于 2014-8-13 00:16
感谢上题！能再上解答么

类似于一个LRU cache的感觉……用一个hashmap，一个双链表，每读进来一个数，就更新链表

请问第二题的C是怎么做的呢？

第二题的C可以用trie吧。