j********2 发帖数: 82 | 1 大部分是在这里看到的。不少是常见题。
1. An online stream, with infinite numbers, tell me the most frequent number
.
2. streaming logging, 设计方案能随时求最近分钟和小时和天的top clicks.
3. how to add a counter to www.google.
4. LOCAL MINIMUM. EXTEND到N*N的ARRAY的LOCAL MINIMUM的算法.
5. scramble string. How to do it in polynomial time?
6. 给一个list of sentences, 然后找出一个pair,common words 最大。举例:
This is a good day
This is a bad day
That was good day
return 第一个和第二个句子,因为有四个common words.
7.given a text file with 3 columns -- all integers:
id,parent,weight
each line is a node, 'parent' refers to 'id' of another node.
Print out, for each node, the total weight of a subtree below this node.
Someone says 不用建树,直接边扫描边打印就好, how? |
y*****3 发帖数: 451 | |
b*****c 发帖数: 1103 | |
k*******r 发帖数: 355 | 4 第一题里面, An online stream, with infinite numbers, 这个是无限流含有限个
unique数,还是无限流含无限个unique数
如果是有限个unique数那很容易,如果是无限个unique数我就不会做了,高手来讲讲 |
c********p 发帖数: 1969 | |
w*****e 发帖数: 748 | 6 这无限unique还可能有解么?
【在 k*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题里面, An online stream, with infinite numbers, 这个是无限流含有限个 : unique数,还是无限流含无限个unique数 : 如果是有限个unique数那很容易,如果是无限个unique数我就不会做了,高手来讲讲
|
b******7 发帖数: 123 | 7 可以是在给定任何时间,确实挺难。
【在 w*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这无限unique还可能有解么?
|
s********f 发帖数: 510 | 8 第一题应该问的是近似的最常见数. 因为如果是要求确定的, 需要无限的存储空间。这
里有近似解的答案:http://stackoverflow.com/questions/3260653/algorithm-to-find-top-10-search-terms?newreg=e0d277c9365f499fbf54de491a7b1d1f
我的理解是用一个slot有限的存储空间,如果新读进来的数是有的,就在那个位置+1。
如果没有,看还有没有空slot,有就放进去,记数为1。如果也没有空slot了,就把记
数最少的数扔掉,然后把新数放进去,记数为1。
上面的帖子讲了只要最常见的数出现次数高于1/(1+k), k是总的slot数,就可以保证找
到。所以实际应用中,k足够大,就基本保证了结果。 |
k***n 发帖数: 5 | |
D**********d 发帖数: 849 | 10 第七题的思路:
void PrintSubtreeSum(vector< vector > &Input){
size_t NodeNum = Input.size();
if(NodeNum == 0) return;
vector result(NodeNum,0);
for(size_t i = 0; i < NodeNum; ++i){
result[i] += Input[i][2];
int p = Input[i][1]; // parent index
while(p > -1){// assume root node's parent index is -1
result[p] += result[i];
p = Input[p][1];
}
}
for(size_t i = 0; i < NodeNum; ++i){// print out result
cout << "Node " << i << ": " << result[i] << endl;
}
} |
|
|
l***i 发帖数: 632 | 11 看到这个stackoverflow的贴
才发现原来muthu写书啦
【在 s********f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题应该问的是近似的最常见数. 因为如果是要求确定的, 需要无限的存储空间。这 : 里有近似解的答案:http://stackoverflow.com/questions/3260653/algorithm-to-find-top-10-search-terms?newreg=e0d277c9365f499fbf54de491a7b1d1f : 我的理解是用一个slot有限的存储空间,如果新读进来的数是有的,就在那个位置+1。 : 如果没有,看还有没有空slot,有就放进去,记数为1。如果也没有空slot了,就把记 : 数最少的数扔掉,然后把新数放进去,记数为1。 : 上面的帖子讲了只要最常见的数出现次数高于1/(1+k), k是总的slot数,就可以保证找 : 到。所以实际应用中,k足够大,就基本保证了结果。
|
v***n 发帖数: 562 | 12 先mark
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看到这个stackoverflow的贴 : 才发现原来muthu写书啦
|
S******6 发帖数: 55 | 13 探讨下,我觉得这道题目是为了找每个id下面链接id的weight和,要避免死循环。
所以我在您code基础上做了点修改:
void PrintSubTreeSum(vector > &Input)
{
int size = Input.size();
if(size == 0) return;
vector res(size, 0);
for(int i = 0; i < size; i++)
{
map mp;
res[i] += Input[i][2];
mp.push_back(Input[i][0]);
int p = Input[i][1];
while(mp.find(p) == mp.end())
{
mp.push_back(p);
res[i] += Input[p][2];
p = Input[p][1];
}
}
for(int i = 0; i < size; i++)
{
cout << "Id : " << Input[i][0] << " with subTree weight : " << res[i]
<< endl;
}
}
【在 D**********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第七题的思路: : void PrintSubtreeSum(vector< vector > &Input){ : size_t NodeNum = Input.size(); : if(NodeNum == 0) return; : vector result(NodeNum,0); : for(size_t i = 0; i < NodeNum; ++i){ : result[i] += Input[i][2]; : int p = Input[i][1]; // parent index : while(p > -1){// assume root node's parent index is -1 : result[p] += result[i];
|
x******f 发帖数: 18 | 14 对于第7题, 最优的复杂度应该是O(n), 7楼和13楼给的答案复杂度高了。
一个算法是: 用一个数组 A, A[i] 存储指向节点i的节点总数。 计算的时候, 先计
算A[i] = 0 的所有 i 的sub-tree的和。 然后把i指向的节点在A里对于的值减1.
这其实是一个topological ordering问题。 |
x******f 发帖数: 18 | 15 大致代码如下:
void PrintSubTreeSum(vector > &Input)
{
int size = Input.size();
if(size == 0)
return;
vector InDegree(size, 0);
vector TotalWeight(size,0);
vector ParentIdx(size,-1);
for(int i=0;i
{
InDegree[Input[i][1]]++;
TotalWeight[Input[i][0]] = Input[i][2];
ParentIdx[Input[i][0]] = Input[i][1];
}
queue dq;
for(int i=0;i
{
if(InDegree[i]==0)
dq.push(i);
}
while(!dq.empty())
{
int curIdx = dq.front();
dq.pop();
cout << "Id : " << curIdx << " with subTree weight : " <<
TotalWeight[curIdx] << endl;
int ParIdx = ParentIdx[curIdx];
if(ParIdx<0)
continue;
InDegree[ParIdx]--;
TotalWeight[ParIdx] += TotalWeight[curIdx];
if(InDegree[ParIdx]==0)
dq.push(ParIdx);
}
} |
b**m 发帖数: 1466 | 16
how to build A in O(n) time?
【在 x******f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对于第7题, 最优的复杂度应该是O(n), 7楼和13楼给的答案复杂度高了。 : 一个算法是: 用一个数组 A, A[i] 存储指向节点i的节点总数。 计算的时候, 先计 : 算A[i] = 0 的所有 i 的sub-tree的和。 然后把i指向的节点在A里对于的值减1. : 这其实是一个topological ordering问题。
|
k*****m 发帖数: 14 | 17 2. streaming logging, 设计方案能随时求最近分钟和小时和天的top clicks.
是啥解法?? |
n*****f 发帖数: 17 | 18 1,2是典型的streaming algorithm
4的一维版本O(logn)解法很简单,二维版本的O(n)D&C解法很漂亮,详见
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf |
b*****c 发帖数: 1103 | |
p*****9 发帖数: 273 | |
|
|
d*******g 发帖数: 15 | |
A*********c 发帖数: 430 | 22 赞。
【在 n*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1,2是典型的streaming algorithm : 4的一维版本O(logn)解法很简单,二维版本的O(n)D&C解法很漂亮,详见 : http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
|
k****i 发帖数: 128 | 23 谁有2d local minimum的code?还有怎么proof?包子求 |