转:
四轮都是华人面孔
第一轮是一个国人妹子，一上来愉快地闲聊了一会，然后到时间开始 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;
}
}