狗家详细面经

Round 1:

coding problem:

Given an input string, find out the longest palindrome by deleting any characters or swap any pair of characters of the input string.

同一轮有个讨论题,假如有个摄像头可以截取城市某个特定区域的夜景图,现在给我们两个夜景图片,可以抽象成两个M * M(摄像头可拍摄区域大小固定)的grids/matrix ,M1, M2。摄像头是在移动的,所以M1,M2不一定代表同一区域,而抽象成的matrix由0,1组成,1代表这个区域亮灯,0表示不亮灯,原先在M1亮灯的区域在之后不一定还亮着,原先不亮的也可能会亮起来。问从M1到M2,摄像头最有可能做的线性变换/移动是怎样的,最有可能是通过,假定某种线性变换后,M1变换成M1’, 去看M1’和M2的overlap的1的个数,多的话,可能性就高。

Round 2:

Given a word and a dictionary, determine if it can be composed by concatenating words from the given dictionary.

follow ups:

每次对于一个特定位置(sustring 0,…, i),都要回头看之前的每个子问题(j < i), 效率很差,怎么提高。

提了下把substring 0… j是true的j放到一个list里,每次都去看list里的那些j对应的子问题。

Round 3:

给两个interface,

Interface Callback {
execute();
}

Interface AsyncTask {
onComplete(Callback callback);
}

Q1:

如果有两个有dependency的asyncTask,怎么实现

Q2:

如果有一个list of asyncTasks, 彼此之间没有dependency,怎么保证它们全部执行完了之后可以print out “hello world”

Round 4:

有个游戏,是有一个input string(比如“a8*&b”, string里有letter,digit或者其他的各种字符),还有wordList words,需要找到wordList里面包含input string里所有的letter的最短的string/word。