f******c
发帖数: 80 | 1 刚amazon一面，白人男，问的题目挺简单，都是类似于论坛里出现过的题目
1、介绍了他所在的组，blablabla。。。
2、问了些几道java概念，final 和finally区别，thread怎么用等等。。。。
下面是两道老的算法题，全程念code。。。。。
3、老题目，given an unsorted array and an integer, 找array里是否存在一个pair
之和等于integer。他要求O(n)，不能首先sort the array. 他提示用Set来做，做完还
问了怎么写test cases 验证代码正确。
4、判断两个BST是否完全相同，让用recursive 和non-recursive两种方法都做一遍，
念code。
然后就结束了，我在让写test cases的时候，不知道怎么写了。。。
现在amazon的面试题目都是经常出现的题目，唯一问题是面的时候用结结巴巴的口语念
代码真是念得头大啊。。。（想面amazon的还是好好临阵磨枪代码怎么念。。。）， |
f*******t
发帖数: 7549 | |
g*****k
发帖数: 623 | 3 bless
non-recursive 判断BST是否相同，除了pre-order iterative traversal
外还有什么好办法吗？
pair
【在 f******c 的大作中提到】
: 刚amazon一面，白人男，问的题目挺简单，都是类似于论坛里出现过的题目
: 1、介绍了他所在的组，blablabla。。。
: 2、问了些几道java概念，final 和finally区别，thread怎么用等等。。。。
: 下面是两道老的算法题，全程念code。。。。。
: 3、老题目，given an unsorted array and an integer, 找array里是否存在一个pair
: 之和等于integer。他要求O(n)，不能首先sort the array. 他提示用Set来做，做完还
: 问了怎么写test cases 验证代码正确。
: 4、判断两个BST是否完全相同，让用recursive 和non-recursive两种方法都做一遍，
: 念code。
: 然后就结束了，我在让写test cases的时候，不知道怎么写了。。。
|
f******c
发帖数: 80 | 4 我就用了in-order traversal and convert to two arrays,then compare...没有问有
没有更好的方法。。
【在 g*****k 的大作中提到】
: bless
: non-recursive 判断BST是否相同，除了pre-order iterative traversal
: 外还有什么好办法吗？
:
: pair
|
g*****k
发帖数: 623 | 5 in-order? 该用pre-order啊。
【在 f******c 的大作中提到】
: 我就用了in-order traversal and convert to two arrays,then compare...没有问有
: 没有更好的方法。。
|
f******c
发帖数: 80 | 6 该用in-order, left->node->right
【在 g*****k 的大作中提到】
: in-order? 该用pre-order啊。
|
g*****k
发帖数: 623 | 7 think again,
2
1 3
和
1
2
3
【在 f******c 的大作中提到】
: 该用in-order, left->node->right
|
f******c
发帖数: 80 | 8 用in-order 两个都是1，2，3啊
【在 g*****k 的大作中提到】
: think again,
: 2
: 1 3
: 和
: 1
: 2
: 3
|
g*****k
发帖数: 623 | 9 那这两个BST完全相同?
【在 f******c 的大作中提到】
: 用in-order 两个都是1，2，3啊
|
f******c
发帖数: 80 | 10 对，看来弄错了。。。
【在 g*****k 的大作中提到】
: 那这两个BST完全相同?
|
|
|
g*****i
发帖数: 2162 | 11 我觉得inorder,preorder, postorder的iterative都可以吧,但是我们不是比较结果,而
是过程. 入栈的时候两个数要都有node入,如果有exception说明结构不同.出栈的时候
值要一样.
【在 g*****k 的大作中提到】
: bless
: non-recursive 判断BST是否相同，除了pre-order iterative traversal
: 外还有什么好办法吗？
:
: pair
|
s******n
发帖数: 226 | 12 BST inorder 不唯一确定树
【在 g*****i 的大作中提到】
: 我觉得inorder,preorder, postorder的iterative都可以吧,但是我们不是比较结果,而
: 是过程. 入栈的时候两个数要都有node入,如果有exception说明结构不同.出栈的时候
: 值要一样.
|
S********y
发帖数: 565 | |
g*****i
发帖数: 2162 | 14 但是我只要保证类似如下情况:当a树插入一个left child的时候,另外的b数也能插入一
个left child.right child也一样.当a树的stack pop一个值的时候,b树也能pop一个值
并且值相同. 这些用来判断两树相同应该已经够了.
【在 s******n 的大作中提到】
: BST inorder 不唯一确定树
|
s******n
发帖数: 226 | 15 你说的是对的
但是iterative的inorder相对preorder要复杂一些，用preorder更clean一些，我觉得
，而且只看pop的时候两个值相同就行。
【在 g*****i 的大作中提到】
: 但是我只要保证类似如下情况:当a树插入一个left child的时候,另外的b数也能插入一
: 个left child.right child也一样.当a树的stack pop一个值的时候,b树也能pop一个值
: 并且值相同. 这些用来判断两树相同应该已经够了.
|
p********o
发帖数: 640 | 16 弱弱的 问一句 。。
第3 题目是什么意思啊 就是 找到 2个数字 加起来等某一个数字么？
为啥要用 set
hashtable 可以不？ |
m**q
发帖数: 189 | 17 只看pop的两个值是不够的，比如getback上面举得例子。
两个树pop pre-order traversal pop的顺序都是1，2，3
guangyi说的看过程大概是可以的，或者就干脆最直接的
preorder + inorder 或者 postorder + inorder
【在 s******n 的大作中提到】
: 你说的是对的
: 但是iterative的inorder相对preorder要复杂一些，用preorder更clean一些，我觉得
: ，而且只看pop的时候两个值相同就行。
|
s******n
发帖数: 226 | 18 可能我没说清楚，不只是看pop什么值
比如 inorder
while(cur || !s.empty()){
if(cur){
1// s.push(cur); cur = cur.left;
}else{
2// cur = s.pop();
visit(cur);
cur = cur.right;
}
}
1和2 check两个地方，就是push和pop都检查，也看分支，这样就没有问题了
【在 m**q 的大作中提到】
: 只看pop的两个值是不够的，比如getback上面举得例子。
: 两个树pop pre-order traversal pop的顺序都是1，2，3
: guangyi说的看过程大概是可以的，或者就干脆最直接的
: preorder + inorder 或者 postorder + inorder
|
r*******y
发帖数: 1081 | 19 #3. How to use Set? divide the array into two sets and one contains the
numbers less than one half of the integer and the other set contains the
numbers greater than one half of the integer? then what to do? |
f*******t
发帖数: 7549 | 20 对array中每一个数a，在set里查找是否有sum-a，然后把a放进set
【在 r*******y 的大作中提到】
: #3. How to use Set? divide the array into two sets and one contains the
: numbers less than one half of the integer and the other set contains the
: numbers greater than one half of the integer? then what to do?
|
|
|
r*******y
发帖数: 1081 | 21 but this is O(n^2) if not using hashing?
【在 f*******t 的大作中提到】
: 对array中每一个数a，在set里查找是否有sum-a，然后把a放进set
|
a**********2
发帖数: 340 | 22 我觉得三种DFS都可行，在stack里面存pair instead of
TreeNode×
【在 g*****k 的大作中提到】
: 那这两个BST完全相同?
|
R****i
发帖数: 104 | 23 除了比较1 2 3以外， 还可以比较以下指针结构吧。
比如本例中的1一个left == right == null； 另外一个的left == null, right !=
null.
【在 g*****k 的大作中提到】
: think again,
: 2
: 1 3
: 和
: 1
: 2
: 3
|
c**m
发帖数: 535 | 24 第三题，unsorted array，O(n)的时间内，只能是hashtable吧 |
y******n
发帖数: 47 | 25
一样的, 其实是hashset,底层实现是hashtable
【在 p********o 的大作中提到】
: 弱弱的 问一句 。。
: 第3 题目是什么意思啊 就是 找到 2个数字 加起来等某一个数字么？
: 为啥要用 set
: hashtable 可以不？
|
y******n
发帖数: 47 | 26
既然是BST, 那么只用preorder或者postorder序列就可以判断出来了吧, 不需要两个序
列. 一般的binary tree需要两个序列
【在 m**q 的大作中提到】
: 只看pop的两个值是不够的，比如getback上面举得例子。
: 两个树pop pre-order traversal pop的顺序都是1，2，3
: guangyi说的看过程大概是可以的，或者就干脆最直接的
: preorder + inorder 或者 postorder + inorder
|
p****e
发帖数: 37 | 27 这么做有一个问题，就是如果有一个数a刚好是sum的一半，结果就不对了。如果写代码
的话还要特殊处理一下
【在 f*******t 的大作中提到】
: 对array中每一个数a，在set里查找是否有sum-a，然后把a放进set
|
