Amazon OA2 due on 12/15

刚做完的OA2，12/15 的due。
Work simulation：
首先时间够用，我每个题都仔细看了email／chat，做完还能剩40分钟。 所以时间很充足。
内容大概是：1. dealline与requirement。看着选吧。
                   2. log问题。找相同原因就行。我看的log是某个service出问题了，给了你一个report。第一问是为什么会出现德语，看report发现出现德语的共同点是locate都在德国，所以答案选

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

integer，而testcase set的是double 。

Codiing：1. 翻转linkedlist。
              2. subtree问题。         

就这些。bless us！

recursion是O(N)么.我看到的算法是

1. 
   
2. class TreeNode {
   
3.         int val;
   
4.         TreeNode left;
   
5.         TreeNode right;
   
6.         TreeNode(int x) { val = x; }
   
7. }
   
8. 
   
9. public class Subtree {
   
10.         public boolean isSubTree(TreeNode T1, TreeNode T2) {
    
11.                 if (T2 == null)        return true;
    
12.                 if (T1 == null)        return false;
    
13.                 return (isSameTree(T1,T2) || isSubTree(T1.left, T2) || isSubTree(T1.right, T2));
    
14.         }
    
15.         public boolean isSameTree(TreeNode T1, TreeNode T2) {
    
16.                 if (T1 == null && T2 == null)        return true;
    
17.                 if (T1 == null || T2 == null)        return false;
    
18.                 if (T1.val != T2.val)        return false;
    
19.                 return (isSameTree(T1.left, T2.left) && isSameTree(T1.right, T2.right));
    
20.         }
    
21. }
    

复制代码

水逼一枚 发表于 2015-12-14 16:09
还有就是你说的这个duplicate的问题只是在constuctr回binary tree是不行的，但是你用inorder + preorder/ ...

1.     b           b
   
2.    /           /
   
3.   a           a
   
4. / \         /
   
5. a   a       a
   
6.            /
   
7.                   a

复制代码

左树右树三种遍历方式全相等.根据13楼code答案是false.

补充内容 (2015-12-15 00:59):
第七行的a向左移动6个字符.图片被弄乱了.

dengke 发表于 2015-12-13 09:15
http://algorithms.tutorialhorizon.com/given-two-binary-trees-check-if-one-binary-tree-is-a-subtree-o ...

我OA没遇到subtree所以不知道具体要求.
不过tree serialization的时候, 如果tree含重复节点, 是不能用inorder+preorder/postorder做线性化的.如果subtree这道题说可以有duplicate node.那么这两种O(N)做法就不ok,只有用naive的方法了.
当然如果subtree说了不能有duplicate, 就没问题

感谢楼主分享.求问楼主的"翻转链表"是链表折半再翻转?记得好像是OA1的题目啊.

换题啦？楼主能详细说一下翻转链表和subtree的问题吗？我17号due！！

楼主觉得subtree 最优解法是recursion吗， 我用iterate 写的，时间复杂度一样，但是用了stack，马上video了，想知道最优解

是Count Univalue Subtree那道原题吗？还没刷完leetcode不好意思。。。

leonidas1573 发表于 2015-12-13 06:45
感谢楼主分享.求问楼主的"翻转链表"是链表折半再翻转?记得好像是OA1的题目啊.

是的
字数字数字数

dengke 发表于 2015-12-13 07:15
换题啦？楼主能详细说一下翻转链表和subtree的问题吗？我17号due！！

翻转列表面经里就有啊，reverse second half linkedlist。奇数从中间开始翻。
subtree就是判断root2 是否root1的subtree，return -1 or 1.

LOUIS懒蟲 发表于 2015-12-13 07:59
楼主觉得subtree 最优解法是recursion吗， 我用iterate 写的，时间复杂度一样，但是用了stack，马上video了 ...

我用的是recursion。我觉得都差不多吧。

dengke 发表于 2015-12-13 08:10
是Count Univalue Subtree那道原题吗？还没刷完leetcode不好意思。。。

不是。就是判断是不是subtree。

http://algorithms.tutorialhorizon.com/given-two-binary-trees-check-if-one-binary-tree-is-a-subtree-of-another/
http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/
subtree问题找到了用inorder和postorder做的O(N)算法。。。