Google onsite - 其中有难题 Remove Extra Edge

第一轮是一个比较严肃的美国小哥，题目不难但我太紧张导致脑子短路: 一个binary tree里有1个extra edge，找到并且fix。我用dfs做的，然后写完小哥让我自己找我的code能不能cover所有的情况, 然后发现并不能，改了几下之后code终于能work。反正这轮磕磕绊绊，要挂就挂在这了。

第二轮是个超酷的打耳钉的美国小姐姐。高频题LC二二尔，先给你一个数，找这个数在不在tree里面，followup找到树的大小。这轮真是使尽各种演技。。。

第三轮美国小哥，题目很长很绕但交流之后其实很简单，简洁地表述下大概就是：用户在手机屏幕上滑动打字， 给你一串string记录了你手指滑动经过的char，举个例子比如， “hrwcewelwlcfo”, 这个手指滑动可以打出一个”hello”。用户从h开始，手指划过“rwc”, 打出一个“e”, 划过”we“, 打出”l“, 划过w, 打出”l“, 再划过”cf“, 打出“o”. 这样就打出“hello”，很神奇有没有？？然后给你一个路径的string和一个dictionary of words, 问你有多少个word可以被用这个路径打出来。路径的第一个字符和最后一个字符一定是会被打出来的。这题本质很简单基本靠交流。 我说了两种方法，一种从路径入手，排列组合，一个一个放到dictionary里面查；另一种一个一个word拿出来，two pointer比较。比较了两种方法的复杂度，还算了一些数学公式，写了第二种的code。followup是如果在同一个位置可以停留多次怎么做，就是在同一个char上可以重复打好多次。比如“hwelpto”也可以打出“hello”，这里“l”重复打了两次，也不难，秒了。

第四轮印度哥, 是sweti，题也很简单，一列车队n辆车，速度分别是1到n，随机排列成一条，然后开始开，不能超车，问你无限时间之后return一个车队cluster array，每个数代表cluster里车的个数，要按顺序。比如input【2， 3， 1， 4】返回的是【2，2】。一开始我以为他要问cars fleet那题，没想到问了个更简单的。。。follow up是现在有一辆车speed是n+1，我们把它加入到这个n车车队的空隙中，总共n+1个空隙，然后问你每种加入，最后导致的车队cluster array，就是return一个array of array。写完followup之后讨论怎么test。

运气太好了，后面两题medium感觉都算不上，就是很简单的算法变了一个形式问。除了第一轮其余三轮都是提早做完题跟面试官各种聊天。题目要是没写清楚大家可以随意留言。

好多树的考点

第一轮，extra edge的定义是什么
第二轮，leetcode number是222？
第四轮、具体问题是啥？
谢谢

如图红线所示

多谢啦！
貌似PreOrder 遍历+Set存储访问过的节点。

参考 https://leetcode.com/discuss/interview-question/358676/Google-or-Remove-Extra-Edge

Given a binary tree, where an arbitary node has 2 parents i.e two nodes in the tree have the same child. Identify the defective node and remove an extra edge to fix the tree.

Example:

Input:
	   1
	  / \
	 2   3
	/ \ /
   4   5

Output:

     1			       1
    / \			      / \
   2   3    or	     2   3
  / \ 			    /   /
 4   5		       4   5

Explanation: We can remove either 3-5 or 2-5.

Solution

public static TreeNode removeEdgeBT(TreeNode root) {
	return removeEdgeBT(root, new HashSet<>());
}

private static TreeNode removeEdgeBT(TreeNode node, Set<TreeNode> seen) {
	if (node == null || !seen.add(node)) return null;
	node.left = removeEdgeBT(node.left, seen);
	node.right = removeEdgeBT(node.right, seen);
	return node;
}

Follow-up 1:
What if the tree is a BST?

Example:

Input:
       3
	  / \
	 2   5
	/ \ /
   1   4

Output:
       3
	  / \
	 2   5
	/   /
   1   4

Explanation: In this case we can only remove 2-4 because if we remove 5-4 the BST will be invalid.

Hint https://leetcode.com/problems/validate-binary-search-tree

Solution

public static TreeNode removeEdgeBST(TreeNode root) {
    return removeEdgeBST(root, null, null);
}

private static TreeNode removeEdgeBST(TreeNode node, Integer min, Integer max) {
    if (node == null) return null;
    if ((min != null && node.val < min) || (max != null && node.val > max)) return null;
    node.left = removeEdgeBST(node.left, min, node.val);
    node.right = removeEdgeBST(node.right, node.val, max);
    return node;
}

Follow-up 2:
What if the tree is an N-ary tree?

Design an algorithm and write code to figure our which trail you are hiking. There are lots of trails around you. And you are hiking, which means the distance between you and all the points are continue changing. It’s an open question. You need to define input and output yourself. I set the input as [trail id: points array] (point: {x,y,z}) as the points for all trails in my area. The output is the trail id you are hiking on.

请问是加州还是西雅图啊