f********a
发帖数: 367 | 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的域就
可以了。 |
f********a
发帖数: 367 | 2 这个TreeMap怎么弄啊？ key是timestamp？ Object就是{totalLen， count}？ |
f********a
发帖数: 367 | 3 up.
Given continuous incoming real time stock price stream,
1) design data structure to support query for max, min price in the past
12 months.
2)implement in code
还有这问题。
我觉得这种问题都差不多。 还有那个RESTFUL API的问题。 都差不多。 |
n******n
发帖数: 12088 | 4 这不就是sliding window max吗？
/* */) 的大作中提到: 】
【在 f********a 的大作中提到】
: up.
: Given continuous incoming real time stock price stream,
: 1) design data structure to support query for max, min price in the past
: 12 months.
: 2)implement in code
: 还有这问题。
: 我觉得这种问题都差不多。 还有那个RESTFUL API的问题。 都差不多。
|
n******n
发帖数: 12088 | 5 没看懂问题。
/* */) 的大作中提到: 】
【在 f********a 的大作中提到】
: up.
: Given continuous incoming real time stock price stream,
: 1) design data structure to support query for max, min price in the past
: 12 months.
: 2)implement in code
: 还有这问题。
: 我觉得这种问题都差不多。 还有那个RESTFUL API的问题。 都差不多。
|
f********a
发帖数: 367 | 6 en, copy paste错了
那原题和那个REST server差不多， 我觉得。 你觉得怎么解呢？ 这个treemap的怎么
弄？ key就是timestamp么？
【在 n******n 的大作中提到】
: 这不就是sliding window max吗？
:
: /* */) 的大作中提到: 】
|
n******n
发帖数: 12088 | 7 哪个题？
/* */) 的大作中提到: 】
【在 f********a 的大作中提到】
: en, copy paste错了
: 那原题和那个REST server差不多， 我觉得。 你觉得怎么解呢？ 这个treemap的怎么
: 弄？ key就是timestamp么？
|
f********a
发帖数: 367 | 8 我觉得就是， 一个API， 每一个tweet， 都会去call 一下那个void tweet 的
function。 然后如果我要average length of tweets in a certain time period的
话， 就call the second function
【在 n******n 的大作中提到】
: 没看懂问题。
:
: /* */) 的大作中提到: 】
|
g**4
发帖数: 863 | |
