wish 第二轮电面

一个口音纯正的美国人面的。题目没有在面筋里看过（也有可能之前bolt的onsite把面筋运都用完了hhh)
题目：

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

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

很想house robber III

想请问楼主如何解题的呢？ 思路如何？

        public int longestUnConnected(Node root){
                Map<Integer, Set<Node>> levelMap = levelTaversal(root);
                Map<Integer, Integer> levelSize = new HashMap<>();
       
                for(Map.Entry<Integer, Set<Node>> mapEntry: levelMap.entrySet()) {
                        levelSize.put(mapEntry.getKey(), mapEntry.getValue().size());
                }
               
                int[] dp = new int[levelMap.size() + 1];
                dp[0] = 0;
                dp[1] = levelSize.get(1);
               
                int max = Integer.MIN_VALUE;
                int res = Integer.MIN_VALUE;
                for(int i = 2; i < dp.length; i++) {
                        for(int j = 0 ; j < i -1; j++) {
                                max = Math.max(max, dp[j]);
                        }
                        dp[i] = max + levelSize.get(i);
                        max = Integer.MIN_VALUE;
                }
               
                for(int i = 0; i < dp.length;i++) {
                        res = Math.max(res, dp[i]);
                }
               
                return res;
        }
       
        public Map<Integer, Set<Node>> levelTaversal(Node root){
                Map<Integer, Set<Node>> res = new HashMap<>();
                Queue<Node> q = new LinkedList<>();
                q.add(root);
                int index = 1;

                while(!q.isEmpty()) {
                        int qLen = q.size();
                        Set<Node> s = new HashSet<>();
                        for(int i = 0; i < qLen; i++) {
                                Node node = q.poll();
                                s.add(node);
                                if(node.left != null) q.offer(node.left);
                                if(node.right != null) q.offer(node.right);
                        }
                        res.put(index, s);
                        index++;
                }
               
                return res;
        }

求问下lz内推的啥职位哦 感谢么么

jyttwc901231 发表于 2019/08/09 03:49:34
public int longestUnConnected(Node root){
                Map<Integer, Set<Node>> levelMap = levelTaversal(root);...

想请问层主time和space complexity是多少？而且有没有python版本？

lz能简单说下思路吗

jyttwc901231 发表于 2019-8-9 03:49
public int longestUnConnected(Node root){
                Map levelMap = levelTaversal(root);
                Map levelSize = ...

请问要怎么解释， 一层的node一定会在一起呢

package wishPhoneInterview;

public class unconnectedTreeNode {
       
        public int longestUnConnected(Node root){
                if(root == null) return 0;
                if(root.childAmount != 0) return root.childAmount;
                if(root.left == null && root.right == null) return root.childAmount = 1;
               
                int excludeRoot = longestUnConnected(root.left) + longestUnConnected(root.right);
               
                int includeRoot = 1;
                if(root.left != null) {
                        includeRoot += longestUnConnected(root.left.left) + longestUnConnected(root.left.right);
                }
               
                if(root.right != null) {
                        includeRoot += longestUnConnected(root.right.left) + longestUnConnected(root.right.right);
                }
               
                return root.childAmount = Math.max(excludeRoot, includeRoot);
        }
       
        public static void main(String[] args) {
               
               
                unconnectedTreeNode ut = new unconnectedTreeNode();
                Node r = new Node(18);
                Node q = new Node(17);
                Node p = new Node(16);
                Node o = new Node(15);
                Node n = new Node(14);
                Node m = new Node(13);
                Node l = new Node(12);
                Node k = new Node(11);
                Node j = new Node(10);
                Node i = new Node(9);
                Node h = new Node(8);
                Node g = new Node(7);
                Node f = new Node(6);
                Node e = new Node(5);
                Node d = new Node(4);
                Node c = new Node(3);
                Node b = new Node(2);
                Node a = new Node(1);
               
                a.left = b;
                a.right = c;
                b.left = d;
                b.right = e;
                c.left = f;
                c.right = g;
                d.left = h;
                h.left = i;
                h.right = j;
                i.left = k;
                i.right = l;
                j.left = m;
                j.right = n;
            n.right = o;
            o.right = p;
            p.left = q;
            p.right = r;
               
                System.out.println(ut.longestUnConnected(a));
        }
       
}


class Node{
        int value;
        int childAmount;
        Node left;
        Node right;
        public Node(int value) {
                this.value = value;
                this.childAmount = 0;
                this.left = null;
                this.right = null;
        }
}

请问楼主onsite了吗