L的几道面试题。

第一题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 可以有重复元素,结果不允许重复

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s