|
g****n
发帖数: 431 | 2 来这个版的，和看这个书的，不都是为了找工作。有时只是兴趣。 |
|
|
Z*****Z
发帖数: 723 | 4 right. i was careful to avoid the word 'definition'. i use 'interpretation'
instead |
|
|
g****n
发帖数: 431 | 6 恩，interpretation，这个倒是可以~~~ hoho
' |
|
f*******r
发帖数: 1086 | 7 有一个面试题目就是对于一个bst，
check是否存在 Root to leaf path sum equal to a given number:
以下是geeksforgeeks上的样例代码:
int hasPathSum(struct node* node, int sum)
{
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
我自己也写了类似的code，但是测试发现貌似不对，比如如果我有一个
bst如 |
|
r****o
发帖数: 1950 | 8 能不能看看我写的对不对?
bool hasPathSum(struct node* node, int sum)
{
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
if ((node->left&&node->right)||(!node->left && !node->right))
return(hasPathSum(node->left, subSum) || hasPathSum(node->right,
subSum));
else if (node->left)
return hasPathSum(node->left, s |
|
g*******y
发帖数: 1930 | 9 consider a sub-tree in BST, in general, all the nodes in the subtree must
have
values within a range: [min, max] |
|
i**********e
发帖数: 1145 | 10 longest increasing sequence 的方法来找最大的 BST（不管是 subtree 与否） 是个
容易掉入的误区。
你可以参考一下我贴的图片，这就是其中的反例之一.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
a*******8
发帖数: 2299 | 11 给出一颗tree, 该tree没有任何特征, 即可以有多个子节点, 父节点和左右子节点也没
有大小关系。但每个节点的值不相等。 现给出几个值, 如(12, 24) 请找出从根节点到
值为12 和24的节点的subtree |
|
x******3
发帖数: 245 | 12 store the subtree size in each node, lgN time complexity |
|
m*****y
发帖数: 93 | 13 多谢
btw: 只用一个preorder，subtree的size是怎样得到的？ |
|
r*****n
发帖数: 20 | 14 不考虑unicode 我觉得trie还是比较可行的做法：
1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
2、对于第二层结点开始的subtrees, 找各自的maxheight
3、选出两个height最大的substree 就是答案
1. O(n), where n is the number of words in the dictionary
2. O(|E|*m), where m is the (average) total number of nodes in each substree
and |E| is the size of the alphabetic set.
3. O(1) |
|
j*****u
发帖数: 1133 | 15 if there's a count of subtree nodes on each node, every time you either go t
o left child or right - dropping half nodes, thus O(lgN) assume the bst is b
alanced
achieve |
|
z*s
发帖数: 209 | 16 各位，不好意思。昨天回国了，没上mitbbs。
更正一下：二叉树那道题我说如果再查找中数之前就知道以每个节点为根的子树中节点
的个数的话，假设节点总数n是奇数，m=(n+1)/2，根的左子树的节点数是k，右子树(n-
k-1)。这样的话，就把找中数转换成找第m小的数：
if (m == k+1) return root;
else if (m <= k) find_m(root->lchild, m);
else find_m(root->rchild, m-k-1);
当然，我跟他说都是基于节点个数是奇数，而且没有重复的数的假设。这道题只是让我
说出算法的思路，没让写代码。我说的方法他认可了，所以之后我也没有细想。
我当时说这个方法的复杂度是O(log n)。大家看看这种方法对吗？如果对的话，复杂度应该是多少？
后面那道写代码的题我说错了！他让我写的是 创建我所说的bst that each node
contains the number of descendants in the subtree rooted at this node，就是
一个创建二叉排序数的过程，很简单。
第... 阅读全帖 |
|
g*********s
发帖数: 1782 | 17 后面那道写代码的题我说错了！他让我写的是 创建我所说的bst that each node
contains the number of descendants in the subtree rooted at this node，就
是一个创建二叉排序数的过程，很简单。
what is "创建二叉排序数"? u mean creating a bst given an array, or given
the bst, calculate each node's sub-tree size? the former is not that
straightforward while the latter is easy.
n-
度应该是多
少？ |
|
M7
发帖数: 219 | 18
面了
换。
不很理解这道题，通过交换subtree来使两个不等的binary tree相等?
dynamic programming from upper left to lower right?
no idea... 你怎么回答的？
会怎
反复震荡？这不是物理题吗？
数。
是棋
会右
如果是N个士兵。最多N/2秒就稳定下来了？
这是OO design的题目？
。 |
|
w*z
发帖数: 75 | 19 how about z is the parent of x and y, and x and y are in different subtrees
站: BBS 未名空间站 (Fri Feb 4 00:49:26 2011, 美东)
nodes
eve
kno
,z |
|
j*****u
发帖数: 1133 | 20 Then I misunderstood the question, in this case
1. Get path from root -> x and root -> y
2. Get the lowest common ancestor w of x and y
3. Check if z is on x -> w or w -> y
Complexity is still the same
subtrees |
|
m****i
发帖数: 650 | 21
creates
u
accumulated
2 BSTs have n nodes each, therefore, the combined sorted array is even
size. It can guarantee that the left and right subtree are equal size. |
|
i****c
发帖数: 102 | 22 这题有意思！
1）easy, recursive or iterative algorithm
2) preorder+inorder, preorder+marker, level-by-level, etc.
3) I will prefer to use preorder+marker so that we can find the path to
leaves
without constructing trees in memory
A quick thought, we can do serilization by repeating parent nodes (correct
me if you find errors)
e.g., a tree, root is A, A's left is B, right is C, B's right is D, and C's
left and right are E and F respectively.
then we have AB?DACECF, ? indicates a null
4) distribute small... 阅读全帖 |
|
g***s
发帖数: 3811 | 23 not right. e.g.
A (F B C)
B (B C F)
F (X Y Z)
F (X Y Z)
1) remove all un-matched node
2) Use DP from bottom(leave) to up(root) scan. Get the node number for
largest matched subtrees for each node. |
|
y******5
发帖数: 43 | 24 In your example:
Level 1: A(val:1, Tree1) B(val:1, Tree2)
Level 2: F(val:2), B(val:2), C(val:3)
Level 3: X(val:3), Y(val:4), Z(val:5)
So, we backtrack: Z -> F -> A (or B). Then, we can get the largest match
subtree:
A (or B) -> F -> (X, Y, Z), right?
Probably I did not express my thought clearly. |
|
g***s
发帖数: 3811 | 25 Mark nodes from leaves(height from 0) based on left/right node. and put
into hashmap.
hashmap : (left_node_marked_value,right_node_marked_value) ->
marked_value
marked_value = 0 ;
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] =
marked_value++;
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
BTW:
A subtree of a tree T is a tree consisting of a node in T and all of its
descen... 阅读全帖 |
|
g******0
发帖数: 221 | 26 I am sorry, I don't quite understand what the problem is:
Given a binary Search Tree, find two biggest same subtrees.???
二叉树 是 binary search tree, or binary tree?
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！ |
|
c******w
发帖数: 102 | 27 Interviewed Feb 2011 (took a day)
Got interview through a recruiter. Interviewer was terrible; he kept
stumbling going 'uhh do you mean this' it's obvious they have no managers (
they told me) and no real recruiters cause everyone is an engineer.
You are given a pyramid; the numbers for example is 2 on the first level, 3
-1 on the second level, 4 7 8 on the third, etc. How do you calculate the
maximum sub sequence of any path traversing the pyramid?
Use dynamic programming. Treat the pyramid as ... 阅读全帖 |
|
t******y
发帖数: 884 | 28 You can do it as follows:
1. O(n)
1.1 for i = 0 .. n-2
1.2 compare interval[i] and interval[i-1], consider (intersection, no
intersection) cases, to find the (min_l, min_h)
1.3 return the final interval
2. use a variant of interval tree algorithm
to preprocess the data as interval tree ordered by lower bound of each
interval, and store additional field to hold the minimum date(start, end) of
its subtrees of each node.
then the time is O(1) (get value from root).
For each node insertion, it tak... 阅读全帖 |
|
g*****k
发帖数: 623 | 29 only one step to reach the leaf.
for suffix tree, the internal node provide random access, so it is constant
time to traverse the subtree along the edge "e" in this case.
search |
|
f****4
发帖数: 1359 | 30 节点里面存the number of nodes of current tree/subtree是
clrs 14.1
BST min & BST Succ
clrs 12.2
clrs(Introduction to algorithms 2nd) |
|
i*****f
发帖数: 578 | 31 Good recursion. But looks not exactly what lz asked - X,Y has to be leaf. In
your case what if root only has one child? It measures the distance from
root to deepest child in the right subtree? |
|
s**x
发帖数: 7506 | 32 这个怎么样？
也用 BST, every node has extra info to remember how many nodes on its left
subtree, and original index in the array. then scan the array from right to
left, so we can easily build a whole BST as the array tells us how many
nodes are less than a node.
at the end scan the BST by in-order and fill the numbers from 1 to n. |
|
k****n
发帖数: 369 | 33 There is a straightforward solution:
Suppose we have a set of 1 to n, then from the 1st element of the count-
array c[], a[i] is the c[i]'th element left in the set, when we move forward
, we also need to delete a[i] from the set.
So the problem is, how to find and delete k'th element in lgn time.
This is traditional. A BST with subtree size should be enough. |
|
x****3
发帖数: 62 | 34 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
x****3
发帖数: 62 | 35 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
e*****3
发帖数: 610 | 36 以前见过这种pushLeft的帮法，你可以调试一下。
public void inorderTraverse(Node root) {
Stack s = new Stack();
pushLeft(root, s);
while (s.size() > 0) {
Node node = s.pop();
print(node); // Visit the current node
pushLeft(node.right, s); // Visit the right subtree
}
}
private void pushLeft(Node node, Stack stack) {
while (node != null) {
stack.push(node);
node = node.left;
}
} |
|
H********h
发帖数: 11 | 37 My Kindle team 电面:
Round1, a Chinese person, very nice
1. Check if the input integer array contains two numbers such that the sum
equals to the input value. (CareeCup 150)
2. Implement divide only via plus only. (CareeCup 150)
3. Implement HashTable.
3. Large scale discussing.
Round2, an Indian person, 被其灭
1. 公司组织树状结构(binary tree), 找出考评最优的部门. 其实就是找出sum最大
subtree.
2. OO desing for Chess.
每次都被A3灭, 不知是我倒霉还是.... |
|
H********h
发帖数: 11 | 38 My Kindle team 电面:
Round1, a Chinese person, very nice
1. Check if the input integer array contains two numbers such that the sum
equals to the input value. (CareeCup 150)
2. Implement divide only via plus only. (CareeCup 150)
3. Implement HashTable.
3. Large scale discussing.
Round2, an Indian person, 被其灭
1. 公司组织树状结构(binary tree), 找出考评最优的部门. 其实就是找出sum最大
subtree.
2. OO desing for Chess.
每次都被A3灭, 不知是我倒霉还是.... |
|
z****u
发帖数: 104 | 39 链接里的程序是不是有问题？程序如下：
int diameter2(TreeNode t, int* height)
{
int lh = 0, rh = 0;
int leftD = 0, rightD = 0;
if(t == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}
leftD = diameter2(root->left, &lh);
rightD = diameter2(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;
return max(lh + rh + 1, leftD, rightD);
}
return max(lh + rh + 1, leftD, rightD);
应该是
r... 阅读全帖 |
|
a**********2
发帖数: 340 | 40 正在学习ihas1337code的blog
Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;
Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);
if (L && R) return root; // if p and q are on both sides
return L ? L : R; // either one of p,q is on one side OR p,q is not in
L&
R subtrees
}
如果p是q的ancestor，这段code就返回p,但是实际上应该返回p的parent吧？如果p是
root，那么应该返回NULL。不知道是不是我理解错了
我觉得应该把if (root == p || root == q) return root;
改为 if(root == p || ro... 阅读全帖 |
|
|
l**********1
发帖数: 415 | 42 向大牛们求教：
1）N*N期盼，从(x,Y)到（0，0）的所有路径，只能向左或下走。貌似career-cup上只
有求一条路的。那位牛人给个所有路径的code？
2）一个二叉树，每个节点都是正或负整数，如何找到一个subtree whose sum is the
max.
谢谢！ |
|
r**********1
发帖数: 292 | 43 如果你说这个函数没返回subtree的"root",是有这个问题。但是，对于sum值，是没问
题的。和peking2一样的啊。而且算法关键是recursive就行了啊。
对于包子，我也不在乎。但是我是前几个发帖子的，而且实现给了关键点了啊，怎么着
，我要个包子，我是理直气壮的吧。 |
|
L***Q
发帖数: 508 | 44 大概三周前phone interview，现在还有印象的是三个问题。
1. 两个computer分别在两个lan，两个lan之间是internet。问题：一个computer往另一个computer发packet时候，layer2、layer3的全过程。
2. 32bit integer reverse。我给了两种答案，一个是bit by bit；一个是网上流传的用mask的方法。interviewer说她不知道第二种
3. 给一个binary tree，如何判断是不是BST。我又给了两个solution。一个是从root往下，每个node给children传valid range。第二个solution是从leaf往root，每个node把以自己为root的subtree的range传给自己的parent。
上周四San Jose去onsite，首先感谢去之前在版上bless我的同志们。面的这个group是做data forwarding software的，全组老印。manager老印给人感觉很不错，口音也不重。一共面了6个人，其中两个小印一看就是非要考倒我不可的架势。第一个小印问... 阅读全帖 |
|
a*****a
发帖数: 495 | 45 靠，这样的interview不给offer，跟我上次一样，
就是人家已经有了内部人选了
另一个computer发packet时候，layer2、layer3的全过程。
的用mask的方法。interviewer说她不知道第二种
root往下，每个node给children传valid range。第二个solution是从leaf往root，每
个node把以自己为root的subtree的range传给自己的parent。
是做data forwarding software的，全组老印。manager老印给人感觉很不错，口音也
不重。一共面了6个人，其中两个小印一看就是非要考倒我不可的架势。第一个小印问
一些network的题，我回答，br />
题，编程，和简历问题：
switch scheduling的，所以对router和switch内部的大致情况知道一些。在回答这个
题的时候，除了computer networks教材上讲的东西外，我提到了line card的设计，
high speed router可能是分布式
packet是发到自己所在lan还是别的lan的机器？一个... 阅读全帖 |
|
p*****2
发帖数: 21240 | 46 来自主题: JobHunting版 - 今天上一题
subtree的什么value呀？每个node的value的sum吗？ |
|
w**z
发帖数: 8232 | 47 来自主题: JobHunting版 - 今天上一题 correction.
搞糊涂了，那是另一个题，搞混了
The number of subtrees with all the value are the same
public int FindNumberOfSubTreesWithSameValue(Node root)
5
1 2
1 3
1
answer ：
4 |
|
C***U
发帖数: 2406 | 48 如果能把返回值改一下的话 可以用recursion做 |
|
|
|
