l****p
发帖数: 397 | 1 最后一轮面试由4次视频面试组成，每次45分钟，总共持续3小时。相比前两轮面试，这
轮的面试官都是比较有经验的工程师，问的问题难度也相应加大。
第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
第二次面试。面试官大部分时间都在聊他们组在做的项目，面临的问题，然后问我的兴趣
第三次面试。来自另外一个组的面试官继续聊他的工作，关于performance test方面的
。然后问我是不是对统计学很熟，我说了解一些，用得更多的是数据挖掘和机器学习的
。接下来他就问我聚类算法，我先把k-means给他说了一下。然后问如果数据量很大怎
么办。我说可以用一些top-down或bottom-up的算法，想办法分布到多台机器上去算。
接下来又问我如何构建一个Bayesian Network，我说我用现成的包，自己没写过，然后
一边回忆Bayesian Network。他好像不想拷问我具体的原理，就开始说他怎么用
Bayesian Network来查找性能瓶颈的。他问我一般跑那些数据挖掘的程序要花多少天，
我说几个小时到一两天吧。那时间主要花在哪？我说把数... 阅读全帖 |
|
m****i
发帖数: 650 | 2 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
|
m****i
发帖数: 650 | 3 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
|
l****p
发帖数: 397 | 4 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
很远的话，那也是很耗时的。
Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周 |
|
P*A
发帖数: 189 | 5 来自主题: JobHunting版 - 讨论一道题 用BST挺好，比heap维护更方便，
修改了一下，可以不用把pair当作key来排序，在hash里面记录BST结点的指针
multimap bst;
hash_map > hm;
foreach given key k
0. if(hm.find(k)==hm.end()) {
hm.insert(make_pair(k, make_pair(1, bst.end())));
if (bst.size () < K) {
// bst里元素不足K
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
continue;
}
1. f = ++hm[k].first;
2. if (hm[k].second != bst.end()) {
// bst里有k了，那么更新freq值
bst.erase (hm[k].se... 阅读全帖 |
|
r******r
发帖数: 700 | 6 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 7 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
h****e
发帖数: 928 | 8 谢谢longway2008的支持。
flyinocean12，下面是书中的BFS算法，s是开始结点。
BFS(G, s)
1 for each vertex u in G.V - {s}
2 u.color = WHITE
3 u.d = INFINITY
4 u.parent = NIL
5 s.color = GRAY
6 s.d = 0
7 s.parent = NIL
8 Q = {};
9 ENQUEUE(Q, s)
10 while Q<>{}
11 u = DEQUEUE(Q)
12 for each v in G.Adj[u]
13 if v.color==WHITE
14 v.color = GRAY
15 v.d = u.d + 1
16 v.parent = u
17 ENQUEUE(Q,v)
18 u.color = BLACK
然后练习题是这么说的：
Ex 22.... 阅读全帖 |
|
h****e
发帖数: 928 | 9 这道题看起来简单，用stack实现起来还是有一些小tricks的，例如
要记录那些结点已经被访问过了，减少不必要的压栈出栈操作等。
下面是我写的代码：
class SNode {
Node node;
boolean visited = false;
public SNode(Node n) {
node = n;
}
}
class BinaryTreeIterator {
Stack stack = new Stack();
public BinaryTreeIterator(Node root) {
SNode s = new SNode(root);
stack.push(s);
}
public boolean hasNext() {
return !stack.empty();
}
public Node next() {
SNode s = stack.pop();
do... 阅读全帖 |
|
h****e
发帖数: 928 | 10 没有visited flag的话，同一个结点可能反复压栈。peking2的code
用了HashSet也是一样的道理。 |
|
l*****a
发帖数: 14598 | 11 真的吗？
stack其实就是recursion.难道recursion里会重复调用同一个结点？
我明天写写看看，你业可以拿出来证据 |
|
h****e
发帖数: 928 | 12 可以举出反例吗？我试了几种情况都没有错。
我的做法是看到一个重复的结点就跳过去，而不是一批一批地跳。
这样只要用一层while循环就可以了，还减少了需要的边界条件
检查。 |
|
c****p
发帖数: 6474 | 13 来自主题: JobHunting版 - 上一题看看 logk*N
建个k个结点的heap，
先把前k个元素建heap，每次extract一个就加个新的并heapnify。
positions |
|
|
|
h****e
发帖数: 928 | 16 这样你是不是需要maintain每一层的所有的结点呢？可能空间要求就
上去了吧。
我的做法如下。这样写的好处是面试时可以写得出来，但是就是不知道
复杂度是不是最优了：
// it is also easy to write an iterative insertion function
void insert_node(Node*& root, int v) {
if (root==0) {
root = new Node(v);
return;
}
if (root->data>v) {
insert_node(root->left, v);
} else {
insert_node(root->right, v);
}
}
Node* construct_tree(vector > nodes)
{
Node* root = 0;
for (int i=0; i阅读全帖 |
|
h****e
发帖数: 928 | 17 说实话，删除BST结点很tricky的，就是CLRS书里的几个
版本给出的解法都不一样：老教授们到现在都还在纠结
茴该怎么写才好，怎样才能让老小伙计们能学得更透彻
一些。 |
|
|
K*********n
发帖数: 2852 | 19 就是，不会考这种问题是吧。好久不复习数据结构，今天写一个非BST的二叉树，写着写
着就遇到这个问题了，手生，莫笑哈。 |
|
p*****2
发帖数: 21240 | 20
树最
BST
随便找个叶子写起来也不是很简洁吧？ |
|
K*********n
发帖数: 2852 | 21 还好啊，就while一下，顺着左边或者右边找到一个叶子，拿上来就行了。反正没有限定
。我主要觉得，想这样的问题是不是很蛋疼…… |
|
|
K*********n
发帖数: 2852 | 23 Node *del(Node *tree, int n){
Node *nodeFather = tree -> father;
if (tree -> val == n){
if (tree -> left == NULL && tree -> right == NULL){ // a leaf
if (nodeFather -> left == tree){
nodeFather -> left == NULL;
free(tree);
return nodeFather;
}else{
nodeFather -> right == NULL;
free(tree);
return nodeFather;
... 阅读全帖 |
|
|
|
|
K*********n
发帖数: 2852 | 27 没有写root的问题，这个写得很糙，是只写了很一般的情况 |
|
K*********n
发帖数: 2852 | 28 好吧，这个确实不是必须定义的。实现不用管，主要是说算法。 |
|
p*****2
发帖数: 21240 | 29
所以想写简洁不容易呀。我看你代码行数已经超过30行了，而且有parent，还没有包括
所有情况。
你看能不能写一个不超过30行的，没有parent，的全部代码？ |
|
K*********n
发帖数: 2852 | 30 嗯，没有parent就完全不一样了。如果要简洁的话，那些if的部分确实需要好好整整，
有些条件判断是重复的。 |
|
|
p*****2
发帖数: 21240 | 32
我觉得不是BST的挺好。我今天有时间练练。
主要考虑的是时间复杂度，空间复杂度要最优。还要保持balanced |
|
K*********n
发帖数: 2852 | 33 复杂度我觉得还好，这么写，如果是recursion的话。迭代的不好写。要是搞balance的
话，那就又复杂多了，再拓展到多叉树……哇哈哈 |
|
p*****2
发帖数: 21240 | 34 我写了一个
def merge(node1, node2):
if node1==None or node2==None:
return node1 if node2==None else node2
node1.right=merge(node2,node1.right)
return node1
def delete(root, node):
if root==None:
return None
elif root==node:
return merge(node.left,node.right)
else:
root.left=delete(root.left,node)
root.right=delete(root.right,node)
return root |
|
|
d****o
发帖数: 1055 | 36 写了一个增加一个空头结点的简单代码。
node* reverse(node* head, int begin, int end){
assert(begin
if(head==NULL) return NULL;
node* newHead = new node();
newHead->next = head;
node* cur = newHead;
int cnt = end-begin+1; //3
while(begin>=2){ //
cur=cur->next;
if(!cur) return NULL;
begin--; //1
}
node* end=cur;
while(cnt>0){//
end = end->next;
if(!end) return NULL;
cnt--;
... 阅读全帖 |
|
s****a
发帖数: 238 | 37 如果是BST，中序遍历，结果进一个队列，找到结点后继续遍历，直到和队列头的误差
小于队列尾的误差 |
|
a*******y
发帖数: 1040 | 38 不太明白这个“找到结点后继续遍历，直到和队列头的误差
小于队列尾的误差”
继续便利是指以这个节点为根节点在inorder吗？
那下一次遍历以那个节点那?还有“队列头的误差
小于队列尾的误差”是什么道理？ |
|
g*****g
发帖数: 34805 | 39 我来抛砖引玉，1万个combination。每个一个结点，
相邻做有向图，比如0000->0001->0015，求遍历途径 |
|
g*****g
发帖数: 34805 | 40 没被问过，这个俺产品里做过。底层用JGroups，每人起来的时候保存个
timestamp，最老的是老大，有结点挂，JGroups会发消息通知每个节点，
是leader再选举就行。 |
|
g*****g
发帖数: 34805 | 41 split之后就会有多个老大了，合并之后可以回到一个。
jgroups用的是multicast，好处是可以动态地加减节点。
我不知道你需要多高的并发，维护cluster需要的消息数
很少。至少我在400个结点的环境里没有发现问题。 |
|
|
|
|
n*****s
发帖数: 6495 | 45
那先BFS按照层序给所有结点标上号，然后挨个比较left child和right child行不行？ |
|
K*********n
发帖数: 2852 | 46 对，这个问题如果需要in place的话，跟BFS主要的区别就是不能光dequeue，得知道de
queue出来的这个结点在哪层，是否需要新建linkedlist。怎么能知道？ |
|
c********t
发帖数: 5706 | 47 我现在说的不是这道题啊，是说怎么一次遍历按层打印一个btree，结点没有next, 没
有tail。怎么判断什么时候是处理完了一层？
当然如果有这种方法，这题也同层打印一样了。 |
|
K*********n
发帖数: 2852 | 48 对，这个问题如果需要in place的话，跟BFS主要的区别就是不能光dequeue，得知道de
queue出来的这个结点在哪层，是否需要新建linkedlist。怎么能知道？ |
|
c********t
发帖数: 5706 | 49 我现在说的不是这道题啊，是说怎么一次遍历按层打印一个btree，结点没有next, 没
有tail。怎么判断什么时候是处理完了一层？
当然如果有这种方法，这题也同层打印一样了。 |
|
B********t
发帖数: 147 | 50 可以建一个二叉树，叶子保存interval, 内部结点保存所有孩子区间长度 这样就能保
证uniform了 |
|
