Google | Hello World

Google | Hello World
1. boogle question
我能想到的就是dfs来找。一个一个搜索，如果有搜索到就是true，不然就是false， 要注意dfs的时候visited matrix来记录走过的地方。
给定一个2darray， 里面的integer是没有重复的，怎样找到最长的连续数列O(mn）复杂度。
如果用dfs的方法或者BFS的方法，复杂度应该是mxnx(m+n)，如果要用O(mn)的话，应该是用dp的方法
int [][] min = new int [m][n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if (i == 0 && j == 0)
min[i][j] = 1;
else if (i == 0) {
min[i][j] = num[i][j-1] == num[i][j] ? min[i][j-1] + 1 : 1;
}
else if (j == 0) {
min[i][j] = num[i-1][j] == num[i][j] ? min[i-1][j] + 1 : 1;
} else {
if (num[i][j] == num[i-1][j] + 1)
min[i][j] = min[i-1][j-1] + 1;
else if (num[i][j] == num[i][j-1] + 1)
min[i][j] = min[i][j-1] + 1;
else
min[i][j] = 1;
}
}
}
2. 给定一个array，输入是0到99之间的整数，输出一个string包括所有miss掉的数，如果相邻长度超过2，则输出比如3-5而不输出单个数。
这个就是按个扫过来，扫到了漏掉的数就加进结果数组里。如果结果数组的最后一个是你的前一个数，那么替换掉最后一个数，另外如果结果数组的倒数第二个数不是-，要加上一个-

3. 给定一个target的整数，将他分解成square的和，保证这个分解的term最少。 这道题挺难，我能像到的就是从头1扫到sqrt(target). 然后计算,这样的复杂度应该是n!.

int numberOfTerm(int n) {
if (n == 1)
return 1;
int min = n;
for(int i = 1; i < sqrt(target); i++) {
min = Math.min(numberOfTerm(n-i*i) + 1, min);
}
return min;
}

然后可以看到其实可以用dp的方法优化：

int numberOfTerm(int n) {
int[] numOfT = new int [n];
for (int i=0; i<numOfT.length; i++) {
if (i == 0)
numOfT[i] = 0;
else
numOfT[i] = i;
for (int j=1; j<=sqrt(i); j++) {
numOfT[i] = Math.min(numOfT[i], numOf[i-j*j] + 1);
}
}
return numOfT[n-1];
}

4. 给定一个2darray，里面包含integer，水可以从integer大的地方向小的或相等的地方流。 假设上边和左边是pacific，右边和下边是atlantic， 求所有能到达两个大洋的路径。
这道题因为要记路径，所以用DFS来做， 对于matrix里的每个点都做DFS，看他能不能到达两个大洋，如果能达到的话，就把路径记下来。
后来提示也可以用BFS的方法，从每个大洋的边界上的点开始BFS，找到所有能到达atlantic的点，同理也可以找到所有能到达pacific的点，最后两个一比较就可以找到那些两个大洋都可以达到的点了。

5. 给定一些box的w和l，假设box1可以放在box2的条件是宽和长都小于box2，求最长的可能放进盒子的序列，实际上这道题很像Career cup上一道身高和重量叠人墙的题目。我们只需要将box按长度sort，然后如果长度相同再按宽度sort，然后扫描一遍整个数组，看看连续的宽最多有多少即可。 6. system design，设计一个键盘的输入法，不需要一个一个按，而是快速的滑动，怎样设计，怎样给suggestion
给suggestion应该涉及到用trie的数据结构。此外如果用trie的话还要注意排序的问题，如果trie要排序的话还要记下每个char的频率。

Read full article from Google | Hello World