g***j
发帖数: 1275 | 1 请问这三题怎么做的？
第三轮，扯点工作经验，然后考了从inorder, preorder数组构建二叉树，我这题写的
有bug, 当时想就废了.
这个地方你有什么bug?
第四轮，国人哥们，安慰了我一下。出了2道题，第一个是给个数组，打乱了，比如
索引 0 1 2 3 4
值 3 2 1 4 0
数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0 1 -> 2
-> 1， 求最长环的长度.
这个怎么做？对space有要求么？如果对space没有要求，直接扫描就可以吧？
第二题，直线上有一个机器人从原点开始移动，每次可以向左移，也可以向右移，移动
n步，再回到原点的概率是多少, 可以写程序实现。
怎么写程序实现？模拟？ |
|
f*********d
发帖数: 140 | 2 O(n)时间 O(1)空间的遍历是morris遍历吧，而且只能是inorder的吧？
有O(n)时间 O(1)空间的 前序后续遍历算法吗？ 有的话请教教我撒，先谢谢了~~ |
|
d**********x
发帖数: 4083 | 3 但是我想我说的那个不是post-order，而是倒过来的in-order
no stack.
just iteration.
OH... i just googled it and didn't check the solution on leetcode
what i hit was just the comments:
gt said on March 14, 2011 Reply
There is something called MORRIS inorder traversal which does not require
any stack usage to perform the traversal… it uses a tree-transformation
technique to get the traversal done iteratively … not sure if we could
tweak it for post or pre-order traversal … i vaguely recollect it is not
possibl... 阅读全帖 |
|
d*******8
发帖数: 30 | 4 发一下面经吧：
1. Binary Tree Inorder Traversal
2. UTF-8 String 编码
3. 3sum的问题
感觉问的都是很基础的东西。第一个表interview算法还行，但是写code有点慢。第二
个因为写过，就直接写出来了nlogn的算法，感觉面试官还不知道从2sum变形过来一样。
两周后回信说
We carefully reviewed your background, experience, and interview feedback
and unfortunately we didn't find there to be a close enough match for a
Software Engineering Internship position at this time. We will continue to
use our database to match your profile with new opportunities and will reach
out to you if we find an opening fo... 阅读全帖 |
|
s********l
发帖数: 998 | 5 不是找最大的kth吗？
你怎么先跑到左边去了呢？
inorder traversal 反过来就可以了把~ |
|
j******2
发帖数: 362 | 6 这题在矿工界就跟binary tree inorder traversal在码工界一样。 |
|
w*******y
发帖数: 85 | 7 1.两颗二叉树，但是一个节点可能有多个PARENT,判断是否相同。哎，STRUGGLE了很久
，最后写出来了，也不知道对不对。就是INORDER TRAVERSE的改一改
Example:
1
/ \
/ \
2 3
and
1
/ \
/ \
2 3
are identical. But
1
/ \
/ \
2 2
and
1
/ \
\ /
2
are NOT identical.
Also
1
/ \
/ \
2 \
/ \ /
/ \ /
2 2
\
\
2
and
1
/ \
/ \
2 \
/ \ \
/ \ \
2 2 /
\ /
\ /
2
are not identical.
第二面，LOCAL MINIMUM, 老题，早上刚练，不过问我PRO... 阅读全帖 |
|
f*****7
发帖数: 92 | 8 BST可以嘛？
add，delete就是常规操作
getRandom，就用蓄水池抽样，inorder一次 |
|
x*******6
发帖数: 262 | 9 分别serialize preorder和inorder的data，取出时再重新构建tree可行否？ |
|
s****0
发帖数: 117 | 10 devilphoenix的是正解，兄弟。
1 额外空间
hashtable：key=元素，value=一个object标明开始结束
扫描链表，union-find
2 不用额外空间
a double link list -> BST optionally merge sets.
b inorder traversal BST
赞题目。 |
|
|
c***s
发帖数: 192 | 12 想象一下用O(N)空间时是咋算的，
然后将扫描数组的操作转换成inorder traversal. |
|
b****g
发帖数: 192 | 13 O(N)空间难道不是首先要inorder遍历一遍吗？ |
|
l*****a
发帖数: 14598 | 14 inorder traverse不用‘额外空间吗 |
|
l*****a
发帖数: 14598 | 15 inorder traverse不用‘额外空间吗 |
|
c***s
发帖数: 192 | 16 你不需要记录所有nodes的话就不需要额外空间啊。
只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。 |
|
c***s
发帖数: 192 | 17 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
如果考虑的话那就是O(logN)的空间了。
下面是我用java 写的函数。
swap[2]用来记录上一个访问的node。
swap[0]和swap[1]保存错位的nodes。
void find_node(TreeNode root, TreeNode[] swap) {
if(root == null) return;
find_node(root.left, swap);
if(swap[2] != null && swap[2].val > root.val) {
if(swap[0] == null) swap[0] = swap[2];
swap[1] = root;
}
swap[2] = root;
find_node(root.right, swap);
} |
|
b****g
发帖数: 192 | 18 其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？ |
|
c***s
发帖数: 192 | 19 想象一下用O(N)空间时是咋算的，
然后将扫描数组的操作转换成inorder traversal. |
|
b****g
发帖数: 192 | 20 O(N)空间难道不是首先要inorder遍历一遍吗？ |
|
l*****a
发帖数: 14598 | 21 inorder traverse不用‘额外空间吗 |
|
l*****a
发帖数: 14598 | 22 inorder traverse不用‘额外空间吗 |
|
c***s
发帖数: 192 | 23 你不需要记录所有nodes的话就不需要额外空间啊。
只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。 |
|
c***s
发帖数: 192 | 24 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
如果考虑的话那就是O(logN)的空间了。
下面是我用java 写的函数。
swap[2]用来记录上一个访问的node。
swap[0]和swap[1]保存错位的nodes。
void find_node(TreeNode root, TreeNode[] swap) {
if(root == null) return;
find_node(root.left, swap);
if(swap[2] != null && swap[2].val > root.val) {
if(swap[0] == null) swap[0] = swap[2];
swap[1] = root;
}
swap[2] = root;
find_node(root.right, swap);
} |
|
b****g
发帖数: 192 | 25 其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？ |
|
c********t
发帖数: 5706 | 26 然后是题目： BST的第二大元素
应该是 从右子树开始inorder travesal的第二个吧。要求必须iteration吗？ |
|
e****e
发帖数: 418 | 27 bless! recursion is a simple solution based on coldknight's suggestion. It's
the reverse inorder.
first right sub-tree
then itself
last left sub-tree. |
|
e****e
发帖数: 418 | 28 我觉得你的反例已经说明只用InOrder和PreOrder是不行的。我也给出一个反例说明即
使有PostOrder还是不行。
T1:
1
/
2
T2:
1 |
|
c**y
发帖数: 172 | 29 特殊字符就是()
以下是个inorder的例子
printf("(");
inrodervisit(p_node->p_leftchild);
printf(")");
printf(p_node->value);
printf("(");
inrodervisit(p_node->p_rightchild);
printf(")");
这样每次访问一个新的subtree，总是会打印一个（）surrounding这个subtree的序列
。 |
|
|
c******3
发帖数: 60 | 31 谢谢大家的bless。今天总体还是算顺利的没有见到新的算法题（庆幸？)，就不贴了。
比如tree non-recursive iteration (inorder), interval merge and insert,
binary matrix coloring (0->1, 1->0 except 1s surrounded by 0s)
不过 open ended 的system design的问题一大堆，不好过关。
比如：
how would you design youtube?
do you know about GFS? what could you do to improve it? and why?
what would you improve gmail? why?
How would you design counters for youtube videos? |
|
c******3
发帖数: 60 | 32 谢谢大家的bless。今天总体还是算顺利的没有见到新的算法题（庆幸？)，就不贴了。
比如tree non-recursive iteration (inorder), interval merge and insert,
binary matrix coloring (0->1, 1->0 except 1s surrounded by 0s)
不过 open ended 的system design的问题一大堆，不好过关。
比如：
how would you design youtube?
do you know about GFS? what could you do to improve it? and why?
what would you improve gmail? why?
How would you design counters for youtube videos? |
|
w****a
发帖数: 710 | 33 背景：新鲜小硕，申的是2013北美new grads，SDE
地点：都柏林office
没签nda，直接放送了。坐等拒信，明年再来。
第一轮：
写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
需要描述详细时空复杂度，最好情况最坏情况和平均情况。
第二轮：
第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
开始他都没看懂。中间出了一点点小问题，但是改对了。因为我没考虑到1这个情况，4
的0次方是1。太粗心了。然后他让我别用hash_set，用普通方法做一个。我就写了个循
环的方法。循环的方法倒是一次性bug free了。pow4伺候完就开始第二题了。
最短路径那个时间不够了没做完。 不过没做完他倒是没说啥因为开始做这题的时候已
经就剩下10分钟了，他说没做完没事，讲下思路就行。我就没怎么花心思在code上，重
点讲了BFS，画了图给他描述了... 阅读全帖 |
|
m*****k
发帖数: 731 | 34 findNext() is 'same' as inorder, parent pointer is not needed. |
|
w****a
发帖数: 710 | 35 背景：新鲜小硕，申的是2013北美new grads，SDE
地点：都柏林office
没签nda，直接放送了。坐等拒信，明年再来。
第一轮：
写一个bst的类，要求包含查找最小的节点的方法。并利用这个函数实现findNext()。
最后再写一个函数输出BST的inorder，非递归，用前面两个函数很容易写。
需要描述详细时空复杂度，最好情况最坏情况和平均情况。
第二轮：
第一题是isPow4。写了两种方法，查表法和循环法。分别解释时空复杂度。第二题是图
的最短路径。有障碍物。pow4他问的比较多，我还解释了INT_MAX是多少，long long一
开始他都没看懂。中间出了一点点小问题，但是改对了。因为我没考虑到1这个情况，4
的0次方是1。太粗心了。然后他让我别用hash_set，用普通方法做一个。我就写了个循
环的方法。循环的方法倒是一次性bug free了。pow4伺候完就开始第二题了。
最短路径那个时间不够了没做完。 不过没做完他倒是没说啥因为开始做这题的时候已
经就剩下10分钟了，他说没做完没事，讲下思路就行。我就没怎么花心思在code上，重
点讲了BFS，画了图给他描述了... 阅读全帖 |
|
m*****k
发帖数: 731 | 36 findNext() is 'same' as inorder, parent pointer is not needed. |
|
d**********x
发帖数: 4083 | 37 都看工作领域。。。
visitor我手边的例子就是解析网页之后，遍历dom tree然后将class为ooxx的元素
handle全部提出来，或者对这些种类的元素做某些改变
inorder |
|
p*****2
发帖数: 21240 | 38
你这个理解其实有些误区。因为吧，Code Lee上的一题可能是几题。
不如inorder transversal其实包含了很多题
1. dfs
2. iterative (我知道有三种解法）
3. morris
这样就是算5道题了，然后preorder+postorder就是10几道道题了。 |
|
f****s
发帖数: 74 | 39 有个不需要的版本，顺便再练一遍。
void inorder(Node* root){
if(!root)
return;
stack s;
Node* cur=root;
while(1){
while(cur){
s.push(cur);
cur=cur->left;
}
if(s.empty())
break;
cout<val;
s.pop();
cur=cur->right;
}
}
|
|
k*******2
发帖数: 84 | 40 觉得好多题都是这样，貌似很基础，但是没做过的话真心不容易一下子给出neat的bug
free代码，很容易给人基础不牢的感觉。。我觉得包括reverse linked list, inorder
遍历的循环解法都是这类。。看来还是我太弱了。。不知道要做多少题才能质变啊。。 |
|
c********r
发帖数: 286 | 41 cool, make scene. 那个前序中序恢复BST是不是这个 Construct Binary Tree from
Preorder and Inorder Traversal？ |
|
p*****2
发帖数: 21240 | 42
Id Question Difficulty Freqency Data Structures Algorithms
1 Two Sum 2 5
array
set
sort
two pointers
2 Add Two Numbers 3 4
linked list
two pointers
math
3 Longest Substring Without Repeating Characters 3 2
string
hashtable
two pointers
4 Median of Two Sorted Arrays 5 3
array
binary search
5 Longest Palindromic Substring 4 2
string
6 ZigZag Conversion 3 1
string
7 Reverse Integer 2 3
math
8 ... 阅读全帖 |
|
b******7
发帖数: 92 | 43 1)canJump
从右往左是经典dp，
f(i)表示第i+1个点跳到底n个点最小步骤
f(i) = min{1 + f(i+k)}, k = 1... A[i]
2）BST 加successor
void add_successor(TreeNode * root)
{
if(root == NULL) return NULL;
TreeNode * pre = NULL;
stack s;
for(TreeNode * p = root; p != NULL; p= p->left)
s.push(p);
while(!s.empty())
{
TreeNode * cur = s.top();
s.pop();
if(pre != NULL) pre->successor = cur;
pre = cur;
for(TreeNode * p = cur... 阅读全帖 |
|
f*********m
发帖数: 726 | 44 请问下面几个题是怎么答的？
面试官2：
（1）一个urn里有red，blue，green三种小球，分别的个数都已知。给一个uniform
random number generator产生[0，1]之间的数，要求写一个function随机选取小球，
选取的概率跟球的分布一致
面试官5：
（2）硬币问题：给一个unfair coin，Head和Tail的概率未知。现在已知扔了N次得到K
次Head，分别用MLE和MAP估计第N+1次出现Head的概率。
（3）先是定义：如果一个binary tree的一个subtree里所有node的key都一样，则这个
subtree叫identical tree（一个identical tree的子树理论上也是identical tree，
但计算时只算最大的那个）。 现在给任意一个binary tree，求它所包含的identical
tree的数量，比如[1，1,1]算1个，[1,2,2]算2个，[1,1,2]也算2个。
第三题能不能用Inorder，postorder, preorder 把树分别走一遍，发现不同的key就把
identical... 阅读全帖 |
|
s******r
发帖数: 65 | 45 今天真衰，只做了两道。
12. Construct binary tree from inorder and preorder/postorder traversal (
recursion, traversal properties)
13. The Painter's partition problem (dp) 吭哧吭哧。。。
征刷友啊，嘿嘿，刚开始leetcode。。。 |
|
h**o
发帖数: 548 | 46 请教正确答案。
网上答案是下面这样的，但如果有个child不存在哪？难道返回另一个child?
网上还有种方法用inorder找candidate, 再用preorder找最先出现的candidate，那如
果一个child不存在， 不就找到root了吗？
Node* find_lowest_common_ancestor_BT(Node* root, Node* child1, Node* child2){
if (!root) return NULL;
Node* left=NULL;
Node* right= NULL;
//if either child1 or 2 are root than root is LCA
//and since this algorithm goes from top to down, in the case of one
child is
//ancestor of the other child, the ancestor child will be hit and return.
int... 阅读全帖 |
|
l*****a
发帖数: 14598 | 47 来自主题: JobHunting版 - 问到G家题 为什么不是找previous/next node with inorder traverse |
|
s*********t
发帖数: 52 | 48 inorder一遍，再postorder一遍，然后再恢复，行不 |
|
p*****3
发帖数: 488 | 49 value,left offset,right offset
offset为0代表null, serialize和unserialize都是inorder |
|
h*****n
发帖数: 15 | 50 序列化不是好解 因为对于不balance的树 空间复杂是2^n次，链表的话
个人觉得inorder+postorder 才是比较好的解 O（2n）还是线性解 |
|
