谷歌 onsite 面筋

转:
四轮都是华人面孔
第一轮是一个国人妹子,一上来愉快地闲聊了一会,然后到时间开始 coding 。有一个 game 是在 binary tree 里 occupy 尽可能多的 node 算是胜利,有玩家 A 和 B ,除了第一次每一次只能选择和自己选过的 node 相连的 node ,假设已知 A 选择的 node ,求问 B 应该选择哪个 node 才能 occupy 最多的 node 。 follow up 是如果你是 A , 就是第一个选 node 的人,你选择哪个 node 可以赢。 follow up 只说了想法没有写 code ,优化到 O ( n )
第二轮是典型背包问题,给一些 task ,以及每个 task 的 priority 和需要用 cpu 的个数,假设有 10 个 cpu ,求可能达到的最大 priority 的和, follow up 是返回这个 combination
第三轮是 leetcode 扒以吴,我用的 bfs , 问了下怎么优化 hashmap 少用一点空间,没想出来
第四轮是给两个 string , source 和 target ,求问最少需要 repeat source 几次才可以得到 target , repeat 完的 string 可以删除任意 character 。先是暴力解然后优化的。
报个 timeline , 9 月中旬内推, 9.25 收到 OA , 10 月底收到 onsite , 11.19 面, 12.6 通知过 hc 感觉我整体还是比较简单一点,碰到四个华人真的很幸运啦,希望大家都能有好运啦

A和B选择的node互斥吗?

可以把A选的node看成新的root节点。原来A选的node的父节点也看成一个subtree。这样一共有3个subtree。然后B选node最多的subtree就可以了。根据我对题的理解,A可能能占领两个subtree(因为选完第一个点以后,B只能在选的subtree里面链接)。所以A一定赢得方法就是,选一个节点,保证以此节点为root的三个subtree中没有一个subtree的节点数大于另外两个subtree的节点数和。那A就一定能赢

public class Solution {
    
    public TreeNode pickNode(TreeNode root, TreeNode a) {
        
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        TreeNode parent = null;
        TreeNode leftChild = new TreeNode(0);
        TreeNode rightChild = new TreeNode(0);
        int totalNodes = 0;

        while (!q.isEmpty()) {
            totalNodes++;
            TreeNode cur = q.poll();
            if (cur.left == a || cur.right == a) {
                parent = cur;
            }
            if (cur == a) {
                leftChild = cur.left;
                rightChild = cur.right;
            }
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(right);
            }   
        }
        
        int leftNodes = countNodes(leftChild);
        int rightNodes = countNodes(rightChild);
        
        //default value in case A picked root Node
        int parentNodes = Integer.MIN_VALUE;
        
        //A didn't pick the root node
        if (parent != null) {
            parentNodes = totalNodes - leftNodes - rightNodes - 1;//minus the node A already picked
        }
        
        
        if (leftNodes > rightNodes && leftNodes > parentNodes) {
            return leftChild;
        } else if (rightNodes > leftNodes && rightNodes > parentNodes) {
            return rightNodes;
        } else {
            return parentNodes;
        }
    }
    
    private int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

对手可以在subtree里插入吧,相当于搞破坏

应该不行。题目里面说了除了第一次以外,都必须选相连的点。相当于选完subtree就没法去别的地方了。所以选subtree的root会cover最多的点

这句话应该就给限制住了

这个是不是直接相连呀?要是隔着点也算相连的话,那就这个tree随便选了。那个麻烦了。

嗯,有道理,我觉得你的分析和代码是对的

注意一下打平手的edge case

请问第三轮的followup有什么办法吗

是说bus route这题吗

如果你看solution的话,并不是用HashMap解的。其中把每个 Bus Route 都 sort 了一下然后 BFS.


import java.awt.Point;

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S==T) return 0;
        int N = routes.length;

        List<List<Integer>> graph = new ArrayList();
        for (int i = 0; i < N; ++i) {
            Arrays.sort(routes[i]);
            graph.add(new ArrayList());
        }
        Set<Integer> seen = new HashSet();
        Set<Integer> targets = new HashSet();
        Queue<Point> queue = new ArrayDeque();

        // Build the graph.  Two buses are connected if
        // they share at least one bus stop.
        for (int i = 0; i < N; ++i)
            for (int j = i+1; j < N; ++j)
                if (intersect(routes[i], routes[j])) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }

        // Initialize seen, queue, targets.
        // seen represents whether a node has ever been enqueued to queue.
        // queue handles our breadth first search.
        // targets is the set of goal states we have.
        for (int i = 0; i < N; ++i) {
            if (Arrays.binarySearch(routes[i], S) >= 0) {
                seen.add(i);
                queue.offer(new Point(i, 0));
            }
            if (Arrays.binarySearch(routes[i], T) >= 0)
                targets.add(i);
        }

        while (!queue.isEmpty()) {
            Point info = queue.poll();
            int node = info.x, depth = info.y;
            if (targets.contains(node)) return depth+1;
            for (Integer nei: graph.get(node)) {
                if (!seen.contains(nei)) {
                    seen.add(nei);
                    queue.offer(new Point(nei, depth+1));
                }
            }
        }

        return -1;
    }

    public boolean intersect(int[] A, int[] B) {
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            if (A[i] == B[j]) return true;
            if (A[i] < B[j]) i++; else j++;
        }
        return false;
    }
}