GOOGLE 4/14 电面

如果各种方向都可以走的话，而且Android lock screen不是如果已经走了一个点，再路过它的时候就不算了么，这样的话，总的pattern数不是C(4,9) *A(4,4) +C(5, 9) * A(5,5) + C(6, 9)*A(6,6) + C(7,9)*A(7,7) + C(8,9)*A(8,8) + C(9,9)*A(9,9) ？

不可以跳着走的

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

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

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

肯定是8个方向，，，玩下安卓解锁就都知道了。

如果没有限制的话，感觉是permutationd的变种

如果不能夸数字， 比如1 不能到 3， 4， 9的话， 要把1，3，7，9单独拿出来考虑。。。额 这个思路感觉还挺复杂的。

123
456
789

补充内容 (2016-4-19 22:21):
1 不能到3， 7 ， 9

组合数学题啊……

电面考这个太难了吧。。。

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. }

复制代码

题意是遍历9宫格所有长度为4-9的pattern，并且点不重复？也不就是number of island的变种吗？抱歉，我看了10分钟的题目，还是看不懂。。。。
OAB
OOC
OED
请问上面这个pattern是什么意思？

hison7463 发表于 2016-5-4 11:30
题意是遍历9宫格所有长度为4-9的pattern，并且点不重复？也不就是number of island的变种吗？抱歉，我看了1 ...

就是从A到E，如果AB位置对调了就是别外一个pattern