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 的大作中提到】
: 第一题里面， An online stream, with infinite numbers, 这个是无限流含有限个
: unique数，还是无限流含无限个unique数
: 如果是有限个unique数那很容易，如果是无限个unique数我就不会做了，高手来讲讲
|
b******7
发帖数: 123 | 7 可以是在给定任何时间，确实挺难。
【在 w*****e 的大作中提到】
: 这无限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 的大作中提到】
: 第一题应该问的是近似的最常见数. 因为如果是要求确定的, 需要无限的存储空间。这
: 里有近似解的答案：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 的大作中提到】
: 看到这个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 的大作中提到】
: 第七题的思路：
: 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 的大作中提到】
: 对于第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 的大作中提到】
: 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？包子求 |
