由买买提看人间百态

topics

全部话题 - 话题: 结点
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
l****p
发帖数: 397
1
来自主题: JobHunting版 - Twitter实习最后一轮面试总结
最后一轮面试由4次视频面试组成,每次45分钟,总共持续3小时。相比前两轮面试,这
轮的面试官都是比较有经验的工程师,问的问题难度也相应加大。
第一次面试。上来先问一些我研究相关的问题。然后出编程题:给一个二叉树,找出最
长不重复的结点间路径。
第二次面试。面试官大部分时间都在聊他们组在做的项目,面临的问题,然后问我的兴趣
第三次面试。来自另外一个组的面试官继续聊他的工作,关于performance test方面的
。然后问我是不是对统计学很熟,我说了解一些,用得更多的是数据挖掘和机器学习的
。接下来他就问我聚类算法,我先把k-means给他说了一下。然后问如果数据量很大怎
么办。我说可以用一些top-down或bottom-up的算法,想办法分布到多台机器上去算。
接下来又问我如何构建一个Bayesian Network,我说我用现成的包,自己没写过,然后
一边回忆Bayesian Network。他好像不想拷问我具体的原理,就开始说他怎么用
Bayesian Network来查找性能瓶颈的。他问我一般跑那些数据挖掘的程序要花多少天,
我说几个小时到一两天吧。那时间主要花在哪?我说把数... 阅读全帖
m****i
发帖数: 650
2
来自主题: JobHunting版 - Twitter实习最后一轮面试总结
第一次面试。上来先问一些我研究相关的问题。然后出编程题:给一个二叉树,找出最
长不重复的结点间路径。
这个啥意思呢
m****i
发帖数: 650
3
来自主题: JobHunting版 - Twitter实习最后一轮面试总结
第一次面试。上来先问一些我研究相关的问题。然后出编程题:给一个二叉树,找出最
长不重复的结点间路径。
这个啥意思呢
l****p
发帖数: 397
4
来自主题: JobHunting版 - Twitter实习最后一轮面试总结
怎么预处理比较好呢?用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
来自主题: JobHunting版 - 如何秒杀99%的海量数据处理面试题
海量数据处理:十道面试题与十个海量数据处理方法总结
作者: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
来自主题: JobHunting版 - 如何秒杀99%的海量数据处理面试题
海量数据处理:十道面试题与十个海量数据处理方法总结
作者: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
来自主题: JobHunting版 - CLRS算法书中BFS的疑问
谢谢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
来自主题: JobHunting版 - binary tree的in-order iterator怎么写?
这道题看起来简单,用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
来自主题: JobHunting版 - binary tree的in-order iterator怎么写?
没有visited flag的话,同一个结点可能反复压栈。peking2的code
用了HashSet也是一样的道理。
l*****a
发帖数: 14598
11
来自主题: JobHunting版 - binary tree的in-order iterator怎么写?
真的吗?
stack其实就是recursion.难道recursion里会重复调用同一个结点?
我明天写写看看,你业可以拿出来证据
h****e
发帖数: 928
12
来自主题: JobHunting版 - 请教一道单链表问题
可以举出反例吗?我试了几种情况都没有错。
我的做法是看到一个重复的结点就跳过去,而不是一批一批地跳。
这样只要用一层while循环就可以了,还减少了需要的边界条件
检查。
c****p
发帖数: 6474
13
来自主题: JobHunting版 - 上一题看看
logk*N
建个k个结点的heap,
先把前k个元素建heap,每次extract一个就加个新的并heapnify。

positions
c****p
发帖数: 6474
14
来自主题: JobHunting版 - 贡献一个NV的verification面经
最后那题用个结点数为2的最小堆。
z****h
发帖数: 164
15
来自主题: JobHunting版 - 回报本版A-M-G面巾
http://www.leetcode.com/2010/10/print-edge-nodes-boundary-of-
binary.html
只是打印边缘接点。
螺旋打印二叉树要求中间结点也打印吧?
求答案。
谢谢
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
来自主题: JobHunting版 - 保持状态一天至少要做几题?
说实话,删除BST结点很tricky的,就是CLRS书里的几个
版本给出的解法都不一样:老教授们到现在都还在纠结
茴该怎么写才好,怎样才能让老小伙计们能学得更透彻
一些。
h**********l
发帖数: 6342
18
来自主题: JobHunting版 - 问个二叉树删除结点的问题
难道不是吗?

树最
BST
K*********n
发帖数: 2852
19
来自主题: JobHunting版 - 问个二叉树删除结点的问题
就是,不会考这种问题是吧。好久不复习数据结构,今天写一个非BST的二叉树,写着写
着就遇到这个问题了,手生,莫笑哈。
p*****2
发帖数: 21240
20
来自主题: JobHunting版 - 问个二叉树删除结点的问题

树最
BST
随便找个叶子写起来也不是很简洁吧?
K*********n
发帖数: 2852
21
来自主题: JobHunting版 - 问个二叉树删除结点的问题
还好啊,就while一下,顺着左边或者右边找到一个叶子,拿上来就行了。反正没有限定
。我主要觉得,想这样的问题是不是很蛋疼……
p*****2
发帖数: 21240
22
来自主题: JobHunting版 - 问个二叉树删除结点的问题

限定
把代码发上来看看。
K*********n
发帖数: 2852
23
来自主题: JobHunting版 - 问个二叉树删除结点的问题
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;
... 阅读全帖
p*****2
发帖数: 21240
24
来自主题: JobHunting版 - 问个二叉树删除结点的问题


还有parent?你原贴里没说呀。
p*****2
发帖数: 21240
25
来自主题: JobHunting版 - 问个二叉树删除结点的问题

为什么应该有father呢?
p*****2
发帖数: 21240
26
来自主题: JobHunting版 - 问个二叉树删除结点的问题

你这个能删除root吗?
K*********n
发帖数: 2852
27
来自主题: JobHunting版 - 问个二叉树删除结点的问题
没有写root的问题,这个写得很糙,是只写了很一般的情况
K*********n
发帖数: 2852
28
来自主题: JobHunting版 - 问个二叉树删除结点的问题
好吧,这个确实不是必须定义的。实现不用管,主要是说算法。
p*****2
发帖数: 21240
29
来自主题: JobHunting版 - 问个二叉树删除结点的问题

所以想写简洁不容易呀。我看你代码行数已经超过30行了,而且有parent,还没有包括
所有情况。
你看能不能写一个不超过30行的,没有parent,的全部代码?
K*********n
发帖数: 2852
30
来自主题: JobHunting版 - 问个二叉树删除结点的问题
嗯,没有parent就完全不一样了。如果要简洁的话,那些if的部分确实需要好好整整,
有些条件判断是重复的。
K*********n
发帖数: 2852
31
来自主题: JobHunting版 - 问个二叉树删除结点的问题
谢谢指导,我打算直接写BST版本了,再贴
p*****2
发帖数: 21240
32
来自主题: JobHunting版 - 问个二叉树删除结点的问题

我觉得不是BST的挺好。我今天有时间练练。
主要考虑的是时间复杂度,空间复杂度要最优。还要保持balanced
K*********n
发帖数: 2852
33
来自主题: JobHunting版 - 问个二叉树删除结点的问题
复杂度我觉得还好,这么写,如果是recursion的话。迭代的不好写。要是搞balance的
话,那就又复杂多了,再拓展到多叉树……哇哈哈
p*****2
发帖数: 21240
34
来自主题: JobHunting版 - 问个二叉树删除结点的问题
我写了一个
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
Z*****Z
发帖数: 723
35
来自主题: JobHunting版 - 问个二叉树删除结点的问题
膜拜
d****o
发帖数: 1055
36
来自主题: JobHunting版 - 问个reverse linked list
写了一个增加一个空头结点的简单代码。
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
来自主题: JobHunting版 - 问一个google题
我来抛砖引玉,1万个combination。每个一个结点,
相邻做有向图,比如0000->0001->0015,求遍历途径
g*****g
发帖数: 34805
40
来自主题: JobHunting版 - leader election没人考?
没被问过,这个俺产品里做过。底层用JGroups,每人起来的时候保存个
timestamp,最老的是老大,有结点挂,JGroups会发消息通知每个节点,
是leader再选举就行。
g*****g
发帖数: 34805
41
来自主题: JobHunting版 - leader election没人考?
split之后就会有多个老大了,合并之后可以回到一个。
jgroups用的是multicast,好处是可以动态地加减节点。
我不知道你需要多高的并发,维护cluster需要的消息数
很少。至少我在400个结点的环境里没有发现问题。
g****y
发帖数: 240
42
来自主题: JobHunting版 - 一道题
bu不用啊,根结点是最后知道sum的
g****y
发帖数: 240
43
来自主题: JobHunting版 - 一道题
bu不用啊,根结点是最后知道sum的
t****a
发帖数: 1212
44
来自主题: JobHunting版 - 刚才重新回顾了一下那题
勉强hack好了,不过还是弄不明白这里头的执行顺序,太诡异了,真不能随便用全局变
量阿。
http://kangtu.me/~kangtu/study/interview.html#sec-12
有愿意改进的朋友请指点指点
PS: 画digraph需要给结点赋予唯一的名称,而生成一个hashmap表示这个树就没这个限
制,容易多了。
n*****s
发帖数: 6495
45
来自主题: JobHunting版 - 弱问怎么判断两个binary tree相同?

那先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
来自主题: JobHunting版 - 新鲜G面筋(2)
可以建一个二叉树,叶子保存interval, 内部结点保存所有孩子区间长度 这样就能保
证uniform了
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)