GOOGLE 4/14 电面

发个google 跪经， 一个三哥面的。感觉他人应该不错，有试着提示我，可是那英语好难理解呀。。。
好了，上题：
Find the total number of patterns of the Androi

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

n. The order of keys used matters.

看到这个题一点想法都没有。。。

1. package google;
   
2. 
   
3. import java.util.*;
   
4. 
   
5. public class AndroidKeyBoard {
   
6.         char[][] board = { { '1', '2', '3' }, { '4', '5', '6' }, { '7', '8', '9' } };
   
7. 
   
8.         public List<String> generate() {
   
9.                 // Set<String> result = new HashSet<String>();
   
10.                 List<String> result = new ArrayList<>();
    
11.                 for (int i = 0; i < board.length; i++) {
    
12.                         for (int j = 0; j < board[0].length; j++) {
    
13.                                 helper(result, "", i, j);
    
14.                         }
    
15.                 }
    
16.                 System.out.println(result.size());
    
17.                 return result;
    
18.         }
    
19. 
    
20.         private void helper(List<String> result, String temp, int x, int y) {
    
21.                 if (x < 0 || y < 0 || x >= board.length || y >= board[0].length
    
22.                                 || board[x][y] == '*')
    
23.                         return;
    
24. 
    
25.                 char t = board[x][y];
    
26. 
    
27.                 temp += board[x][y];
    
28.                 if (temp.length() >= 4) {
    
29.                         result.add(temp);
    
30.                 }
    
31. 
    
32.                 board[x][y] = '*';
    
33.                 helper(result, temp, x - 1, y + 1);
    
34. 
    
35.                 // 8 directional
    
36.                 helper(result, temp, x - 1, y - 1);
    
37.                 helper(result, temp, x - 1, y);
    
38.                 helper(result, temp, x, y - 1);
    
39.                 helper(result, temp, x, y + 1);
    
40.                 helper(result, temp, x + 1, y + 1);
    
41.                 helper(result, temp, x + 1, y);
    
42.                 helper(result, temp, x + 1, y - 1);
    
43. 
    
44.                 // cross!
    
45.                 helper(result, temp, x - 2, y - 1);
    
46.                 helper(result, temp, x + 2, y - 1);
    
47.                 helper(result, temp, x - 2, y + 1);
    
48.                 helper(result, temp, x + 2, y + 1);
    
49. 
    
50.                 helper(result, temp, x + 1, y - 2);
    
51.                 helper(result, temp, x - 1, y - 2);
    
52.                 helper(result, temp, x + 1, y + 2);
    
53.                 helper(result, temp, x - 1, y + 2);
    
54. 
    
55.                 // allow jump
    
56.                 if (x + 1 < board.length && board[x + 1][y] == '*')
    
57.                         helper(result, temp, x + 2, y);
    
58.                 if (y + 1 < board[0].length && board[x][y + 1] == '*')
    
59.                         helper(result, temp, x, y + 2);
    
60.                 if (x > 0 && board[x - 1][y] == '*')
    
61.                         helper(result, temp, x - 2, y);
    
62.                 if (y > 0 && board[x][y - 1] == '*')
    
63.                         helper(result, temp, x, y - 2);
    
64.                 if (x > 0 && y > 0 && board[x - 1][y - 1] == '*')
    
65.                         helper(result, temp, x - 2, y - 2);
    
66.                 if (x + 1 < board.length && y + 1 < board[0].length
    
67.                                 && board[x + 1][y + 1] == '*')
    
68.                         helper(result, temp, x + 2, y + 2);
    
69.                 if (x > 0 && y + 1 < board[0].length && board[x - 1][y + 1] == '*')
    
70.                         helper(result, temp, x - 2, y + 2);
    
71.                 if (x + 1 < board.length && y > 0 && board[x + 1][y - 1] == '*')
    
72.                         helper(result, temp, x + 2, y - 2);
    
73.                 board[x][y] = t;
    
74.         }
    
75. 
    
76.         public static void main(String args[]) {
    
77.                 AndroidKeyBoard android = new AndroidKeyBoard();
    
78.                 android.generate();
    
79.         }
    
80. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

不用Android 理解了半天 要第一次面这个我肯定也跪
弄懂题意后感觉是DFS
不过看了大神解法又跪了 好多case 还考虑到knight move 真是牛b
https://www.careercup.com/question?id=5663422257561600

啥意思，没看明白题目......

兄弟你这题的确有点难。。。。

补充内容 (2016-4-15 09:51):
DFS，从任意点[x][y]开始遍历，当距离等于5的时候，count+1。遍历的时候有8个方向。。。我记着实际中这个lock好像可以是这样：
比如
012
345
678
一个五步path为1->2->4->3->4

woridage1 发表于 2016-4-15 09:37
啥意思，没看明白题目......

OAB
OOC
OED

这个的意思是对于键盘
012
345
678

一个五步的path是 1->2->5->8->7

Fustang 发表于 2016-4-15 09:42
OAB
OOC
OED

是用递归加回溯吗，分别从9个点开始9次，然后每次分别往四个方向进行检索，访问过的给设置成一个特殊的符号，直到层数为 4或者其他要求的层数就计数器加一，然后返回。

Fustang 发表于 2016-4-15 10:09
不仅是相邻的方向
还可以diag move（斜线）和knight move（日字）
以及jump已经lit的点

感觉careerup那哥们的解法也不太对吧。。

感觉像subset啊

看见 这种题目 太容易 让人懵了。其实 应该问清楚 需不需要考虑knight move