Google电面面经 9/2

刚面完不久，应该是跪了
1 两大数相加，用数组表示的，不难

2 给一个树，看有没有相同的子树

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

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

比较这些fingerprint，我还是没明白

luzhuzeng 发表于 2015-9-9 13:50
有能运行的code能share一下吗？

public class Solution {
        private boolean contains;
        private TreeNode node1, node2;
        
        public boolean SameSubTree(TreeNode root){
                if(root == null){
                        return true;
                }
               
                contains = false;
                node1 = null;
                node2 = null;
               
                HashMap<List<Integer>, TreeNode> record = new HashMap<List<Integer>, TreeNode>();
                search(root, node1, node2, record);
               
                return contains;
        }
        
        private List<List<Integer>> search(TreeNode root, TreeNode n1, TreeNode n2, HashMap<List<Integer>, TreeNode> record){
                ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
               
                if(root == null){
                        res.add(new ArrayList<Integer>());
                        res.add(new ArrayList<Integer>());
                        return res;
                }
               
                List<List<Integer>> left = search(root.left, n1, n2, record);
                List<List<Integer>> right = search(root.right, n1, n2, record);
               
                List<Integer> inorder = new ArrayList<Integer>();
                List<Integer> preorder = new ArrayList<Integer>();
                List<Integer> key = new ArrayList<Integer>();
               
                inorder.addAll(left.get(0));
                inorder.add(root.val);
                inorder.addAll(right.get(0));
               
                preorder.add(root.val);
                preorder.addAll(left.get(1));
                preorder.addAll(right.get(1));
               
                key.addAll(inorder);
                key.addAll(preorder);
               
                if(record.containsKey(key)){
                        contains = true;
                        node1 = record.get(key);
                        node2 = root;
                }
               
                record.put(key, root);
               
                res.add(inorder);
                res.add(preorder);
                return res;
        }
        
}

补充内容 (2015-9-9 15:06):
偷懒，用的list；如果真要达到O（n），改成String就可以了

坐看云起 发表于 2015-9-9 01:06
偷懒，用的list；如果真要达到O（n），改成String就可以了

lz有个疑问，你相当于给每个node都存了属于它自己的preorder和inorder,这样算下来光空间就O(n^2)了，那么时间自然也至少是O(n^2)； 比如你每次addall，不管是list也好还是string也好，不都要append上去吗？不都是O(n)吗每次？同时你用一整个list做key去hash，难道计算这个list的hash的时候是O(1)吗？我不清楚list的hash怎么做的，但是如果list很大很大(比如1mission)，我们还能认为计算hash的时候是O(1)吗？我觉得计算hash也得是O(n)吧，因为你需要知道你的list都是什么。有很多疑问不明白，望指教,谢谢!

我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段 <node, preorder + inorder> , 每一个node 有唯一一个 fingerprint. 然后扔到hash表里判重就行了, 可以找出有多少个节点是重的, 最大的子树是多大.

复杂度O(n), n为 树中node的数目.

fingerprint 之所以选择为 preorder+inorder, 因为这个可以唯一确定一棵树.

补充内容 (2015-9-8 14:28):
可以对root的一次 preorder 和 inorder, 求出所有 node的 preorder和inorder, 记录一个time stamp, 详见<算法导论, DFS章节>

对了，求点米呀

啥意思呀第二个题，哪个大牛给解释下

同问第二题，求思路！！！

同求。。。

论坛匿名用户 发表于 2015-9-3 06:44
对了，求点米呀

楼主， 您的米都这么多了。。

第二题感觉可以对树做一次遍历，然后对应遍历的每一个node cur，做一次isSubtree(TreeNode root,TreeNode cur) 调用，找到另外一个包含在root 下并且与当前以cur为根节点的相同的子树，注意一下不要与cur重复。复杂度应该是n方吧。

sosisarah 发表于 2015-9-8 12:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...

楼上的，感谢你的讨论哦，那对于每一个node做一次preorder + inorder, 感觉是o(n^2) 呀。感觉空间复杂度是o(n), 时间复杂度为o(n^2)

hbsophia 发表于 2015-9-8 13:19
楼上的，感谢你的讨论哦，那对于每一个node做一次preorder + inorder, 感觉是o(n^2) 呀。感觉空间复杂度 ...

这个可以在对 root节点的一次 preorder 和 inorder中求出所有node的 preorder和inorder顺序的.