|
d******i
发帖数: 76 | 2 1. 计算以当前节点为根的subtree的最大值，左右孩子都考虑
2. 更新最终最大值
3. 返回当前节点单条路径所能形成的最大值， 即只考虑一个孩子（如果两个孩子节点
都为负数，则返回当前节点的值）
递归 |
|
|
f*********m
发帖数: 726 | 4 interval search算法在该书14.3节（第三版）。
对于下面的树([start，end](maximum end point value in the subtree of the node
))：
[16，21](30)
/ \
[8，9](23) [24，30](30)
/ \ / \
[5，8](8) [15，23](23) [17，19](19) [26，26](26)
若去搜索[22，25]的overlap interval,书上的算法只能找到左边的[15，23]，漏掉了
右边的[24，30]。
书上的算法只保证只找到一个。要找到所有的是不是需要同时搜索左右两个children？
这样复杂度会变成nlogn吧，不如直接做个线性search？
书上是用augmented tree来实现interval tree的，有没有其他形式的interval tree，
可以找到所有的... 阅读全帖 |
|
d**********n
发帖数: 132 | 5 先谢谢jordan，有想过直接从底层往上return，但是如果不保存height，之后每个父结
点判断时，还得迭代进入subtree求height？ |
|
d**********n
发帖数: 132 | 6 嗯，这样的确方便不少，不过有一个地方还没怎么想清楚，如果重新迭代，subtree的
Info是会再计算一遍，还是已经存储了呢，是不是开个全局的structure会更省力？ |
|
z*****e
发帖数: 231 | 7 some thoughts about the first question:
recursively determine if the left substree and right subtree is the same.
Also to avoid the recursive call on the same node multiple times, use the
hash table to store the visited node.
What is the exact question for the second one? |
|
w********p
发帖数: 948 | 8 3. 继续判断这个二叉树是不是平衡树
A balanced binary tree is commonly defined as a binary tree in which the
depth of the two subtrees of every node differ by 1 or less,[3] although in
general it is a binary tree where no leaf is much farther away from the root
than any other leaf. (Different balancing schemes allow different
definitions of "much farther".[4]) Binary trees that are balanced according
to this definition have a predictable depth (how many nodes are traversed
from the root to a leaf, root counting ... 阅读全帖 |
|
l*******b
发帖数: 2586 | 9 记得这题大家说有点bug
brutal force好像复杂度很高吧 |
|
c**y
发帖数: 172 | 10 brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
PostOrder是不是就可以了呢（对于没有duplicate的元素）？ |
|
e****e
发帖数: 418 | 11 我觉得你的反例已经说明只用InOrder和PreOrder是不行的。我也给出一个反例说明即
使有PostOrder还是不行。
T1:
1
/
2
T2:
1 |
|
c********t
发帖数: 5706 | 12 1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
是
2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？
不可以，见ls迪迪贴 |
|
c**y
发帖数: 172 | 13 多谢回复，还是有两个问题不明白，能否详细指教一下。
这个用特殊字符的方法一定要比较Both PreOrder（或者PostOrder）和InOrder的序列
吗？如果是的话，原因是什么呢？
啥是ls迪迪贴呀？另外问题2可能我没有表述清楚。我的意思是比较三个序列（分别由
InOrder，PreOrder和PostOrder Traversal的方法生成，但是不加任何特殊字符）。这
样三个序列不能唯一的确定一个Binary Tree吗？ |
|
c********t
发帖数: 5706 | 14 1. 我感觉两两组合都可以 Pre+post也应该可以，看看有没有人能给出反例
2. 楼上迪迪说的例子,就是反例啊
tree 1
1
/
2
tree 2
1 |
|
s*****1
发帖数: 134 | 15 我也觉得此题很莫名，如果null用特殊符号算的话，单用preorder就行了，我举不出单
用preorder的反例~似乎serialize 和 deserialize 也只用preorder~ |
|
c**y
发帖数: 172 | 16 多谢回复。迪迪的帖子证明了即便inorder，preorder，和postorder都用也是不行的。
关于如果允许使用特殊字符的话，好像只要一个就可以了，either inorder, preorder
或者postorder都可以。通过使用特殊字符，一个binary tree的信息可以被一个序列完
全复制和恢复。因此只要一个序列就可以了。例如
2
/ \
1 3
Inorder: (1)2(3)
Preorder: 21()3()
Postorder: ()1()32
多谢各位 |
|
|
o***d
发帖数: 313 | 18 1)书上说的是time: O(n^2)吧?
2)她似乎说错了,她说:
getHeight() is called repeatedly on the same node.
但实际上处理subtree时,原来tree's getHeight() is done already, not in stack
anymore |
|
l********5
发帖数: 230 | 19 先祝大家新春快乐~~~新年新气象~~
本人cs master刚毕业，OPT中，Feb.1开始的，至今未找到工作，，，近期连续浪费三
个onsite实在伤感。。。眼瞅着3个月期限一天一天过去。。。。。
接下来是BB的onsite，给recruiter发了我的schedule尚未有回复，，看到有人约好了
onsite也被cancel，表示十分慌张。。。在此先报一下之前几个onsite的情况攒攒人品
了。。。
comScore Dec.10,2012
算是比较著名的市场调研数据分析公司，总部在Reston,VA，算是DC郊区。公司不大但
是各方面都挺正规，订机票酒店也不需要自己操心。工作环境看起来也不错，乒乓球桌
桌球台啥的也都有。。
先是学校的oncampus skype面试，一个戴眼镜的小印，大部分时间是问简历，project
啥的，穿插地问了些基本SQL，问了个1-100 missing number，然后介绍他们的情况，
在介绍的时候还不忘穿插小问题：“ blablabla，你说这个情况应该怎么办呢？“ 幸
好没走神，基本都回答出来了。
后来两周要我去onsite，跟我确认了下时间... 阅读全帖 |
|
l**h
发帖数: 893 | 20 搜索了一下，网上一种常见的解法如下：pathLen一直增加，不断把节点的值加进去。
我怎么觉得有错， 比如
1
/ \
2 3
\ /\
4 5 6
打印出来岂不是
1, 2, 4
1, 2, 4, 3, 5
1, 2, 4, 3, 6
了?
http://k2code.blogspot.com/2011/05/root-to-leaf-path.html
/*
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.
*/
void printPaths(struct node* node) {
int path[1000]; printPathsRecur(node, path, 0);
}
/*
Recursive helper function -- given a node, and an array containing
the path from the r... 阅读全帖 |
|
o********8
发帖数: 821 | 21 1.
Question: 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.
2. given a matrix of 0,1, find the max square with only 1s
剩下两个都比较容易，就不列出来了 |
|
f*********m
发帖数: 726 | 22 这里说的是概念上的Tree。
若把整个大问题放在root，可以用DP解决的问题会有很多重复的subtree。除了这些还
有别的区别吗，尤其是（概念上）构建tree的时候？
比如说，是按照从左到右（从小问题到大问题）构建好（即，把小问题放在tree的高层
,把最后的大问题放在叶子），还是从右到左构建好（即，把大问题放在高层）？有没
有比较好的通用策略？ |
|
i**********e
发帖数: 1145 | 23 这是问题给的 "Height-Balanced binary tree" 的定义：
“a height-balanced binary tree is defined as a binary tree in which the
DEPTH of the two subtrees of EVERY node never differ by more than 1.”
请重复读清楚问题至少三遍，然后再看看你画的图，你就明白了 :) |
|
c****m
发帖数: 179 | 24 5.1？是说尽量把每两个node划分为一个subtree，递归枚举所有情况，寻找valid的
case？ |
|
b***e
发帖数: 1419 | 25 (Balanced) Tree that records the size of each subtree in the subroot. |
|
h**o
发帖数: 548 | 26 problem: check whether a tree is a subtree
第二法： 在 大树 中 找 和 小树 根 一样 的 点， 对 此 点 和 小树 作
TreeMatch。。。
为何 the space complexity is O(lg(n) + lg(m)). why? 我没 看见 任何
additional space used 啊. |
|
J****3
发帖数: 427 | 27 Computes the largest subtree common to two binary trees?
大家给点思路？hash吗？这个common 和 tree里Node的value有关还是只要形状一样就
行？ |
|
z****e
发帖数: 54598 | 28 我觉得可以用，但是貌似不是最佳的dp
最佳dp可以直接根据以前算出来的结果推出所要的答案
比如n[i] = n[i-1] + n[i-2]这种
这样的就可以大幅降低复杂度，尤其是i很大的时候
问题在于subtree这种
后面需要的结果未必能直接从之前算出来的结果中直接算出来
我觉得不用也罢
用了的话，对方估计会追问为什么要用dp
你要证明dp能够降低复杂度
如果证明不出来，容易弄巧成拙 |
|
s******n
发帖数: 20 | 29 这个题的例子根本就不是BST: The right subtree of a node contains only nodes
with keys greater than the node's key.
the |
|
g****o
发帖数: 547 | 30 我是第5版书
（1）4.7题 求不带parent指针的binary tree的LCA(不考虑node不在tree里的情况）
书上的解法很罗嗦，很容易漏掉某种情况,leetcode的代码就简洁多了，如下：
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
}
想确认下leetcode的代吗覆盖所有corner case了吗？ 至少我没看出什么问题。
(2)9.5题 Write a meth... 阅读全帖 |
|
j********2
发帖数: 82 | 31 大部分是在这里看到的。不少是常见题。
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,par... 阅读全帖 |
|
S******6
发帖数: 55 | 32 探讨下，我觉得这道题目是为了找每个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];
}
}... 阅读全帖 |
|
x******f
发帖数: 18 | 33 大致代码如下：
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)... 阅读全帖 |
|
m*******4
发帖数: 34 | 34 Write a function that returns the size of the largest subtree that is
complete.
请问怎么解啊 |
|
s******d
发帖数: 424 | 35 想知道这属于什么难度的 是不是不同的组难度有差别？
Round 1 (Written)
1. Given an array, output an array where every index conains nearest
greatest element to that element on right side.
2. Program to convert sorted array to Binary Search Tree
3. Find first non-repeating character in String
ex: geeksforgeeks: f
geeksforgeeksFirst:o
Round 2 (F2F)
1. Given linked list as a-x-b-y-c-z
output it as a-b-c-z-y-x
that is reverse alternate element and append to end of list
2. Output nearest number greater than given number such t... 阅读全帖 |
|
v*****y
发帖数: 68 | 36
对于每个Node,需要存储i，range (number of left nodes in left subtree),left,
right
如果新的node插进来，如果这个node的位置在node1的左子树，需要更新node1的range。
楼上也提到了，这个方法不能保证树的平衡，在构造树的时候，可以使用其他方法保证
他的平衡性。 |
|
r*******2
发帖数: 104 | 37 一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的HR说It's a tough call
，另一个组的HR说very close，不知道是不是套话，总之很沮丧……来版上求问一下大
家问题可能出在哪，并且附上大概的面试过程和coding题目。
第一组：
第1轮：是一个SDE II，看名字像是中东人。coding题目是给定2棵树，判定是否其中一
棵是另一棵的subtree，同时用了DFS和BFS，写完code讨论了几个testcases和复杂度就
结束了。
第2轮：一个白哥Senior Lead，问的题目是一个maze（用2D matrix表示，有的坐标上
有障碍），给定起点和终点，找出从起点到终点的path，还是用的常规的DFS解法，搜
索过程排除有障碍的和访问过的坐标。
第3轮：一个小黑Lead II带去一起lunch，午饭之后问了大概半小时设计题，设计当软
件窗口（比如Word窗口）大小变化的时候每个子图标栏的大小如何变化，大概定义了一
下各个class，挑了其中一个function写了code。
第4轮：一个三哥Principle Lead，先问了一个ASCII和Kanji字... 阅读全帖 |
|
r*******2
发帖数: 104 | 38
好的，我把我的解题过程也说一下。Leetcode原题就不用说了。
第一组：
第1轮：判断subtree。假设两棵树T1和T2，先用DFS在T1里找到和T2的root一样的结点
，然后从找到的结点开始和T2进行比较，我用了BFS，就是用queue，一边一个queue，
同时push/pop进行比较，如果碰到不一样的就return false。做完了想起来其实就是
Leetcode上的Same Tree，直接还用DFS递归比queue省事。
第2轮：找出maze中的path。开一个matrix标记maze的每一个点是否访问过，然后DFS搜
索，从起点开始，查找它的上下左右邻居，如果没有访问过也没有obstacle，就作为一
个选择进行下一步搜索，一直递归下去直到找到终点为止。
第3轮：设计题。
第4轮：ASCII和Kanji字符的题以前面过，当时没做出来，答案就是回来网上搜的（参
考这个网址http://discuss.joelonsoftware.com/default.asp?interview.11.334807.4）。Spiral Matrix是Leetcode原题就不说了。
第... 阅读全帖 |
|
l*********r
发帖数: 136 | 39 背景：中部弱校master，去年五月毕业，刚工作一年（中部小公司），骑驴找马中。
Onsite一共五轮：
--------------------------------------
第一轮（中东人）：
给一个字符串，让压缩并解压，压缩算法类似leetcode中的count and say
输入：aabbbccd 压缩结果：2a3b2cd（注意，'d'前面没有'1'）
引申：输入中如果有数字的话，解压时需要注意歧义问题，例如2a可以解压为'2a'或
者'aa'，问如何解决。答曰用类似ascii码中加反斜杠的做法，或者加个header来标
志压缩过的位，表示同意。
第二轮（老印）：
（leetcode） edit distance，以DP解之，喜。
（leetcode） word ladder，直接给出BFS，不喜，要优化，想了半天给出的答案皆不
喜，最后提示我可以双向BFS，时间不够，没有给出代码。
-----------------午饭-------------------
第三轮（老白）
给一个int的矩阵arr，让返回一个同样大小的result矩阵，每一个result[i][j]... 阅读全帖 |
|
c*******r
发帖数: 610 | 40 最近面了几家公司，上店面经, 攒点人品
amazon
三哥，given a binary matrix， find out the total number of islands， （
geeksforgeeks原题）
跟这里的面经一模一样：http://www.mitbbs.com/article_t/JobHunting/32721661.html
面得很早1月底瑞苦肉特找我就随便面了下，很久没有准备算法了，知道是dfs，但是写
不出来，汗啊，挂了，自此以后努力准备3个月的算法
bloomberg
版上国人大哥内推的，无论如何应该感谢。
国人大哥先要面试我才决定给我内推（可能大哥办事认真）。 内推后另一位国人大哥
面的，虽然
说的是英文，告诉我的是英文名，但是改不了口音，一堆c++问题，好多都忘了，大概
有几道是下面的：
1. c++ pointer/reference, when to use pointer, when to use reference
2. implement linked list. implement copy assignment operator fo... 阅读全帖 |
|
c*******r
发帖数: 610 | 41 我可能意思没表达清楚，不是找distinct subtree。 另外这个例子是面试官给的，他
指出那5个。
所以子树不是非要从根节点开始。 |
|
M*****M
发帖数: 20 | 42 来自主题: JobHunting版 - 一道面试题 类似找最大BST subtree， bottom up.
bool findsubtree(TreeNode *node, unordered_set &set, vector
&vec) {
if(not node) {
return true;
}
unordered_set leftset;
unordered_set rightset;
bool left = findsubtree(node->left, leftset, vec);
bool right = findsubtree(node->right, rightset, vec);
if(left&&right) {
//leftset and rightset overlap
for(auto ele:leftset) {
if(rightset.find(ele)!=rightset.end()) {
... 阅读全帖 |
|
s****n
发帖数: 220 | 43 来自主题: JobHunting版 - 一道面试题 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
|
s****n
发帖数: 220 | 44 来自主题: JobHunting版 - 一道面试题 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
|
s****n
发帖数: 220 | 45 来自主题: JobHunting版 - 一道面试题 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
|
s****n
发帖数: 220 | 46 来自主题: JobHunting版 - 一道面试题 the nodeset will remove the duplicated elements in the subtree, which will
affect the decision for the parent tree. |
|
w****n
发帖数: 37 | 47 签下Facebook，我漫长的找工作经历终于告一段落。这里写下点经历回馈大家。我是CS
PhD new grad。做的方向和工作没什么关系。曾经在一家大的硬件公司做过intern，
然后拒掉了他们的 return offer。
我初期投简历的时候，除了Google和一些小公司，基本上收不到任何回应。当时心急火
燎，没有任何正面反馈，心情很是沮丧。后来都到了要毕业，打算停止投简历的时候，
却忽然来了很多的onsite，最终转化为了最终接受的offer。甚至微软和亚马逊给我
onsite的时候，我都已经接受了别的offer，不打算去他们家面了。现在想想，应该是
赶上了公司的招聘季，所以才会有机会。这里要鼓励大家一定要有信心，不拿到满意的
offer绝不罢休。另外保持一个积极的心态也很重要。我刚刚开始面试的时候心里比较
没谱，总觉得自己不会的很多，所以面试时是一种诚惶诚恐的心态。后来逐渐改善，自
我暗示说看上去很难的题目，其实也没什么，只管会什么说什么。最后虽然还是有很不
会的题目，可是表现会好很多。
我的准备工作基本上是做leetcode。后来觉得leetcode熟悉了，就做了一些Topc... 阅读全帖 |
|
d********r
发帖数: 567 | 48 cong! chi
签下Facebook，我漫长的找工作经历终于告一段落。这里写下点经历回馈大家。我是CS
PhD new grad。做的方向和工作没什么关系。曾经在一家大的硬件公司做过intern，
然后拒掉了他们的 return offer。
我初期投简历的时候，除了Google和一些小公司，基本上收不到任何回应。当时心急火
燎，没有任何正面反馈，心情很是沮丧。后来都到了要毕业，打算停止投简历的时候，
却忽然来了很多的onsite，最终转化为了最终接受的offer。甚至微软和亚马逊给我
onsite的时候，我都已经接受了别的offer，不打算去他们家面了。现在想想，应该是
赶上了公司的招聘季，所以才会有机会。这里要鼓励大家一定要有信心，不拿到满意的
offer绝不罢休。另外保持一个积极的心态也很重要。我刚刚开始面试的时候心里比较
没谱，总觉得自己不会的很多，所以面试时是一种诚惶诚恐的心态。后来逐渐改善，自
我暗示说看上去很难的题目，其实也没什么，只管会什么说什么。最后虽然还是有很不
会的题目，可是表现会好很多。
我的准备工作基本上是做leetcode。后来觉得leetcode熟悉... 阅读全帖 |
|
l********s
发帖数: 358 | 49 DFS and serialize the subtree to a string, insert the string in a HashSet.
If the string already exists in the HashSet, we have two identical sub-
trees. |
|
b******g
发帖数: 3616 | 50 这个DFS如何保证：当serialize出来的两个string一样时，一定这两个subtree也
identical呢？ |
|
