L的几道面试题。 | Hello World
第一题lowest common ancestor in binary tree with parent pointer
这道题比较简单，因为提供了parent pointer， 所以我们只要找出两个node的深度，然后把比较深的那个向上走到和比较浅的那个一样的level，然后两个node一起往上走。碰到一起了就是parent node了
find minimum distance between two words in a string array
e.g ("the", "quick", "brown", "fox", "quick")
distance("fox","the") = 3
distance("quick", "fox") = 1
这道题就是用两个pointer来做，一个指向第一个String，一个指向另一个String，他们每次走到一个新的string的话就记录一下长度，然后和min比较。
System Design Tiny URL 一般的做法先将进来的long url assign一个id，然后将这个id用62bit的base转换成short url即可。当新的url来的时候，我们先将它转换成id，然后去index这个id就可以找到long url
follow up 有环的情况
如果有环的话，就要先找到环的节点，然后再找长度。
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。 可以用dynamic program来做，用一个mxn的matrix存每个房子涂指定颜色的cost
cost[i][j] = min of all cost[i-1][0] .. cost[i-1][n-1] except cost[i-1][j].那问题就转换成了给一个array，怎样最快求除了其中一个数以外的min，其实很简单，我们只要存前两个最小的数，因为最小值只可能是最小的数或者第二小的数。
6.algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target） 这道题属于游戏问题，topcoder里面有讲这类问题
https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/
idea就是如果你能走到losing position，那么你现在就处于winning position，不然说明你只能走到winning position，那说明你现在属于losing position，用递归写这道题就是
isWin(Set choosable, target){
if (choosable.isEmpty()){
return false;
}
for(int i : choosable) {
if (i >= target)
return true;
choosable.remove(i);
if (!isWin(choosable, target-i)) {
return true;
}
choosable.add(i);
}
return false;
}
判断一个数组里是否存在三个数可以组成一个三角形 这道题的关键在于如果A+B>C,那么就一定可以组成一个三角形，所以我们可以将所有的数先sort，然后按顺序扫，只需要扫相邻的ABC三个数就可以，因为我们可以保证C+B>A和C+A>B
lc原题all permutation of array，array 可以有重复元素，结果不允许重复
Read full article from L的几道面试题。 | Hello World
第一题lowest common ancestor in binary tree with parent pointer
这道题比较简单，因为提供了parent pointer， 所以我们只要找出两个node的深度，然后把比较深的那个向上走到和比较浅的那个一样的level，然后两个node一起往上走。碰到一起了就是parent node了
find minimum distance between two words in a string array
e.g ("the", "quick", "brown", "fox", "quick")
distance("fox","the") = 3
distance("quick", "fox") = 1
这道题就是用两个pointer来做，一个指向第一个String，一个指向另一个String，他们每次走到一个新的string的话就记录一下长度，然后和min比较。
System Design Tiny URL 一般的做法先将进来的long url assign一个id，然后将这个id用62bit的base转换成short url即可。当新的url来的时候，我们先将它转换成id，然后去index这个id就可以找到long url
5. 如果两个linked list intersect的话如何找到merge point。
如果是这样的要先知道两个list的长度，然后就很容易到merge point了。follow up 有环的情况
如果有环的话，就要先找到环的节点，然后再找长度。
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。 可以用dynamic program来做，用一个mxn的matrix存每个房子涂指定颜色的cost
cost[i][j] = min of all cost[i-1][0] .. cost[i-1][n-1] except cost[i-1][j].那问题就转换成了给一个array，怎样最快求除了其中一个数以外的min，其实很简单，我们只要存前两个最小的数，因为最小值只可能是最小的数或者第二小的数。
6.algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target） 这道题属于游戏问题，topcoder里面有讲这类问题
https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/
idea就是如果你能走到losing position，那么你现在就处于winning position，不然说明你只能走到winning position，那说明你现在属于losing position，用递归写这道题就是
isWin(Set choosable, target){
if (choosable.isEmpty()){
return false;
}
for(int i : choosable) {
if (i >= target)
return true;
choosable.remove(i);
if (!isWin(choosable, target-i)) {
return true;
}
choosable.add(i);
}
return false;
}
判断一个数组里是否存在三个数可以组成一个三角形 这道题的关键在于如果A+B>C,那么就一定可以组成一个三角形，所以我们可以将所有的数先sort，然后按顺序扫，只需要扫相邻的ABC三个数就可以，因为我们可以保证C+B>A和C+A>B
lc原题all permutation of array，array 可以有重复元素，结果不允许重复
Read full article from L的几道面试题。 | Hello World
