征Mr.Right# Piebridge - 鹊桥
f*a
1 楼
电面2：
还是一个国人大哥，LeetCode上的Insert Interval，API稍微有点变化，给的是一个链
表节点。
由于还有时间，还考了一个count tweets的设计题。需要实现如下API：
class CountingSvc {
void tweet(long timestamp, int tweetLength);
double avgLength(long begin, long end, long threshold);
};
另外给了一个hint，TreeMap，让自己customize一下object。
可惜我一看是range query就往线段树上想了，于是给出了如下结构，并解释了原理。
class Node {
long totalLen;
long count;
long begin;
long end;
Node left;
Node right;
}
最后追问了下如何去做模糊处理。我还是在线段树上想，就加了一个threshold。
double avgLength(long begin, long end, long threshold);
如果线段树上节点和所给的begin，end组合成的节点很相似，就不需要继续往下进行查
询处理了。
随便写了一个计算相似度的公式：abs(begin1 - begin2) + abs(mid1 - end2) <=
threshold，还在琢磨怎么弄更好，他就说很满意了。
虽然这题给我的hint是个TreeMap，但对这种封装好的红黑树无感，毕竟insert操作不
能灵活修改算法。其实如果给个自定义的BST，就在节点上加两个2个prefix sum的域就
可以了。
还是一个国人大哥，LeetCode上的Insert Interval，API稍微有点变化，给的是一个链
表节点。
由于还有时间，还考了一个count tweets的设计题。需要实现如下API：
class CountingSvc {
void tweet(long timestamp, int tweetLength);
double avgLength(long begin, long end, long threshold);
};
另外给了一个hint，TreeMap
可惜我一看是range query就往线段树上想了，于是给出了如下结构，并解释了原理。
class Node {
long totalLen;
long count;
long begin;
long end;
Node left;
Node right;
}
最后追问了下如何去做模糊处理。我还是在线段树上想，就加了一个threshold。
double avgLength(long begin, long end, long threshold);
如果线段树上节点和所给的begin，end组合成的节点很相似，就不需要继续往下进行查
询处理了。
随便写了一个计算相似度的公式：abs(begin1 - begin2) + abs(mid1 - end2) <=
threshold，还在琢磨怎么弄更好，他就说很满意了。
虽然这题给我的hint是个TreeMap，但对这种封装好的红黑树无感，毕竟insert操作不
能灵活修改算法。其实如果给个自定义的BST，就在节点上加两个2个prefix sum的域就
可以了。
