j******a
发帖数: 55 | 1 拿他家练手，结果电面挂掉了，对他家面试安排很不满意，吐槽之余，想和大家讨论一
下题目。
Yelp的Data Mining职位，面试还是general software engineering。第一次随便找了
不知哪个组的人瞎聊，结果HR说要给onsite。然后突然反悔，找了个Data Mining组的
人加Skype面。
上来扯淡5分钟，集中于我的身份问题。。。
why Yelp？
接下来谈了25分钟的Yelp搜索相关问题，用什么feature，以及如何改进搜索结果等等
，我答了学术界常用的改进方法，虽然自己都觉得这些方法不practical，他没有给任
何引导，只是表示大概知道我的意思，不确定这点互相理解了。feature时说到了
mobile相关的feature，是他唯一非常认同的一点，不知道他什么学术背景，让人感觉
像是做system的。。。
然后是那道经典的系统设计题目： 1 million urls from last hour are stored in
the file, find the top K url in terms of the frequency.
直接说了Hashmap扫一遍，然后用size K的Min-Heap过一遍。 然后他就开始追问，如果
input改为一个unlimited data stream,怎么online的update top K urls for last
hour? 我说最笨的方法是你可以动态的update HashMap，然后每次再用Min-Heap过一遍
。如果只想得到近似解，可以用一个size 2K的minHeap，动态的更新Min-Heap. 之后又
补充道，可以对初始的input先sort，然后根据HashMap的变动维护sorted results，每
一次插入只是lg n的开销。他没说什么，我也不确定最优解是什么。他这时候开始在
collabedit上敲函数，想让我coding这个问题，看样子却是个字符串处理。
结果题目还没打完。他说时间不多了，他又问，如果想动态的知道 last day, last
hour, last minute的结果，该怎么改进这个系统，我说先明确最小时间单位，如果是
分钟，就按每分钟存HashMap，然后根据query整合。他说很好的starting point。英语
还是不够好，他经常不太明白我说什么，解释一下，1个小时的时间就到了。想问一下
，大家觉得这个系统设计问题的最优答案是什么？
谢谢。 | g*****e
发帖数: 282 | 2 我在板上发过类似的没人讨论，是记录过去72hour的ip addr access，不断update
counts。实质是一样的。
最容易想到heap。我还想过用3层B tree，依次by second，by minute，by hour。但是
这个B tree的update还是很麻烦，虽然算sum略简单了一点
【在 j******a 的大作中提到】
: 拿他家练手，结果电面挂掉了，对他家面试安排很不满意，吐槽之余，想和大家讨论一
: 下题目。
: Yelp的Data Mining职位，面试还是general software engineering。第一次随便找了
: 不知哪个组的人瞎聊，结果HR说要给onsite。然后突然反悔，找了个Data Mining组的
: 人加Skype面。
: 上来扯淡5分钟，集中于我的身份问题。。。
: why Yelp？
: 接下来谈了25分钟的Yelp搜索相关问题，用什么feature，以及如何改进搜索结果等等
: ，我答了学术界常用的改进方法，虽然自己都觉得这些方法不practical，他没有给任
: 何引导，只是表示大概知道我的意思，不确定这点互相理解了。feature时说到了
| n******n
发帖数: 567 | 3 class Tree{
Node head;
class Node{
urlPair[k] topKlist;
Time start;
Time end;
Time pivot
Node left;
Node right;
public urlPair[] query(Time qstart, Time qend){
if(qstart <= start && qend >= end)
return this.topKlist;
urlPair[] left = new urlPair[k];
urlPair[] right = new urlPair[k];
if(qstart < pivot)
leftResult = left.query(qstart, pivot);
if(qend > pivot)
rightResult = right.query(pivot, qend);
return merge(leftResult, rightResult);
}
public void add(Time start, Time end, urlPair[] in){
urlPair[] topKOfIn = getTopK(in);
Node n = new Node(start, end, topKOfIn);
Node t = head;
while(t != null){
t.end = end;
t.topKList= merge(t.topKList, topKOfIn);
if(t.isTooLarge())
t.split();
t = t.right;
}
}
}
class urlPair{
String url;
int IP;
long count;
}
query log(n), add log(n), n is defined by system | l****o
发帖数: 315 | 4 后天面他家Ads and Search Infra组，不知道会问什么。。。 | g*****e
发帖数: 282 | 5 可能我没有完全理解你的代码，方便讲讲思路么？
我不认为这样update很有效（bst或者heap）。单位时间内x个url/ip被访问，y个url/
ip expire。（x+y)个logN updates，这个N也一直在变。sums要重新计算。很明显有许
多重复计算。我想不出套用或者局部套用DP的法子，也没其他好主意。:(
【在 n******n 的大作中提到】
: class Tree{
: Node head;
: class Node{
: urlPair[k] topKlist;
: Time start;
: Time end;
: Time pivot
: Node left;
: Node right;
: public urlPair[] query(Time qstart, Time qend){
| n******n
发帖数: 567 | 6 就是每一分钟add一个新node, 这个node中记录这个分钟的起始终止时间，和这个分钟
内的topk访问。之后系统设定一个n, 是tree的总共node数，比如说是一个月。其实就
是interval tree 和b+ tree的合体 | g*****e
发帖数: 282 | 7 我去wiki了interval tree。挺有意思的。非常感谢！
【在 n******n 的大作中提到】
: 就是每一分钟add一个新node, 这个node中记录这个分钟的起始终止时间，和这个分钟
: 内的topk访问。之后系统设定一个n, 是tree的总共node数，比如说是一个月。其实就
: 是interval tree 和b+ tree的合体
|
|
