Google暑期实习电面

两轮紧靠着的电面，都是直接上来就问问题，简历一句话都没问，现在招实习都那么直接吗

第一轮是中国小哥，问题是 给定一个9位的键盘，

1 2 3
4

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

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

是很难，只是我太菜， 当为接下来其他面试攒经验和rp吧~

第一题是分成[1,3,7,9], [2,4,6,8],[5]三种键吗

ls的好像不太对，即使你加上visited

得给每个数字加个obstacle 比如1:[2:3,4:7,5:9] 如果prefix里已经有某个数字e.g.2就可以连对应的那个数字 e.g.3了

第一题

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string>
   
4. #include <iostream>
   
5. 
   
6. #define N   (3)
   
7. 
   
8. using namespace std;
   
9. 
   
10. int visited[N*N] = {0};
    
11. 
    
12. bool can_visit(int i, int j) {
    
13. 
    
14.     if (i == j) {
    
15.         return false;
    
16.     } else if (visited[j-1]) {
    
17.         return false;
    
18.     }
    
19. 
    
20.     //start point
    
21.     if (i == 0) {
    
22.         return true;
    
23.     }
    
24. 
    
25.     int rowi = (i-1) / N + 1;
    
26.     int coli = (i-1) % N + 1;
    
27.     int rowj = (j-1) / N + 1;
    
28.     int colj = (j-1) % N + 1;
    
29. 
    
30.     if (rowi == rowj) {
    
31.         int diff = coli - colj;
    
32.         if (diff == 1 || diff == -1) {
    
33.             return true;
    
34.         } else {
    
35.             int k;
    
36.             int min = coli > colj ?colj :coli;
    
37.             int max = coli > colj ?coli :colj;
    
38.             for (k = min+1; k < max; k++) {
    
39.                 if (!visited[(rowi-1) * N + k - 1]) {
    
40.                     return false;
    
41.                 }
    
42.             }
    
43.             return true;
    
44.         }
    
45.     } else if (coli == colj) {
    
46.         int diff = rowi - rowj;
    
47.         if (diff == 1 || diff == -1) {
    
48.             return true;
    
49.         } else {
    
50.             int k;
    
51.             int min = rowi > rowj ?rowj :rowi;
    
52.             int max = rowi > rowj ?rowi :rowj;
    
53.             for (k = min+1; k < max; k++) {
    
54.                 if (!visited[(k-1) * N + coli - 1]) {
    
55.                     return false;
    
56.                 }
    
57.             }
    
58.             return true;
    
59.         }
    
60.     } else {
    
61.         int diffcol = coli - colj;
    
62.         int diffrow = rowi - rowj;
    
63.         if (diffcol == diffrow || diffcol == -diffrow) {//diagnal line
    
64.             if (diffcol == 1 || diffcol == -1) {//ajacent
    
65.                 return true;
    
66.             }
    
67.             int minrow = rowi > rowj ?rowj :rowi;
    
68.             int maxrow;
    
69.             int startcol;
    
70.             int r;
    
71.             if (rowi == minrow) {
    
72.                 startcol = coli;
    
73.                 maxrow = rowj;
    
74.                 if (coli < colj) {
    
75.                     r = 1;
    
76.                 } else {
    
77.                     r = -1;
    
78.                 }
    
79.             } else {
    
80.                 startcol = colj;
    
81.                 maxrow = rowi;
    
82.                 if (coli < colj) {
    
83.                     r = -1;
    
84.                 } else {
    
85.                     r = 1;
    
86.                 }
    
87.             }
    
88.             int k;
    
89.             for (k = minrow+1; k < maxrow; k++) {
    
90.                 if (!visited[(k-1)*N + startcol + r * (k-minrow)]) {
    
91.                     return false;
    
92.                 }
    
93.             }
    
94.             return true;
    
95.         } else {
    
96.             return true;
    
97.         }
    
98.     }
    
99. }
    
100. 
     
101. string int_to_string(int i) {
     
102.     char buf[1024];
     
103.     snprintf(buf, sizeof(buf), "%d", i);
     
104.     return string(buf);
     
105. }
     
106. 
     
107. void back_track_visit(int len, int cur_len, int cur_pos, string path, int &total)
     
108. {
     
109.     if (cur_len == len) {
     
110.         total++;
     
111.         //cout << path << endl;
     
112.         return;
     
113.     }
     
114. 
     
115.     for (int i = 1; i <= N*N; i++) {
     
116.         if (!can_visit(cur_pos, i)) {
     
117.             continue;
     
118.         }
     
119. 
     
120.         visited[i-1] = 1;
     
121.         back_track_visit(len, cur_len+1, i, path + ">" + int_to_string(i), total);
     
122.         visited[i-1] = 0;
     
123.     }
     
124. }
     
125. 
     
126. int main(void)
     
127. {
     
128.     int total = 0;
     
129.     back_track_visit(9, 0, 0, "", total);
     
130.     cout << total << endl;
     
131. }
     

复制代码

第一题感觉要处理特殊情况，基本每个数字都要处理一下，类似如下的感觉
if pre == '1':
                if 2 in visited and curr == 3:
                    continue
                if 4 in visited and curr == 7:
                    continue
                if 5 in visited and curr == 9:
                    continue
            if pre == '2':
                if 5 in visited and curr == 8:
                    continue                    
            if pre == '3':
                if 2 in visited and curr == 1:
                    continue
                if 5 in visited and curr == 7:
                    continue
                if 6 in visited and curr == 9:
                    continue                    
            if pre == '4':
                if 5 in visited and curr == 6:
                    continue              
            if pre == '6':
                if 5 in visited and curr == 4:
                    continue                 
            if pre == '7':
                if 8 in visited and curr == 9:
                    continue
                if 4 in visited and curr == 1:
                    continue
                if 5 in visited and curr == 3:
                    continue               
            if pre == '8':
                if 8 in visited and curr == 2:
                    continue               
            if pre == '9':
                if 8 in visited and curr == 7:
                    continue
                if 6 in visited and curr == 3:
                    continue
                if 5 in visited and curr == 1:
                    continue           

第一题写了60行了，感觉挺麻烦的

为什么说自己菜，有结果了么

谢谢楼主分享！

谢谢分享～祝你好运呀！！加油！

请教下楼长第一轮那题是只需要count，还是print out all unique path？除了DFS有什么好方法吗？

请问第一题什么意思，不太懂

第一题啥意思？能具体讲下马，看不懂。。。

写了下第一题，不太确定是不是正解，欢迎指教

1. public class KeyboardUniquePath {
   
2. 
   
3.         private int count = 0;
   
4.         public int getNumberOfKeyboardUniquePath(int n) {
   
5.                 if (n <= 0) {
   
6.                         return 0;
   
7.                 }
   
8.                 String[] map = {"24568", "1345679", "24567", "1235789", "12346789", "12356789", "24568", "1345679", "24568"};
   
9.                 helper(map, new StringBuilder(), n, "123456789");
   
10.                 return count;
    
11.         }
    
12.         private void helper(String[] map, StringBuilder sb, int n, String choices) {
    
13.                 if (sb.length() == n) {
    
14.                         count++;
    
15.                         return;
    
16.                 }
    
17.                 for (int i = 0; i < choices.length(); i++) {
    
18.                         char c = choices.charAt(i);
    
19.                         sb.append(c);
    
20.                         helper(map, sb, n, map[(int)(c - '1')]);
    
21.                         sb.deleteCharAt(sb.length() - 1);
    
22.                 }
    
23.         }
    
24.        
    
25.         public static void main(String[] args) {
    
26.                 KeyboardUniquePath su = new KeyboardUniquePath();
    
27.                 System.out.println(su.getNumberOfKeyboardUniquePath(1));
    
28.         }
    
29. }
    

复制代码

补充内容 (2015-12-7 23:16):
如果不能有重复数字的话，加一个if (sb.toString().contains(String.valueOf(c))) continue;就行了，因为最多9个数字，所以这儿也是contant的时间

请问楼主这个求问最长的合法的英语词汇是怎么做的？

bobzhang2004 发表于 2015-12-7 08:41
写了下第一题，不太确定是不是正解，欢迎指教

这个貌似没有处理一个键只能用一次
应该加一个 visited hashset, 如果已经出现 跳过