狗家阳谷挂经 攒人品

这周一面的，本来感觉面的还不错，今天收到电话说挂了，原因是多个面试官说coding effiency不太够...algorithm design communication啥都没问题....诶...
面的swe，总共五轮，面试官都是白人男性...

第一轮：马甲版 利口 而久久， follow up：如果已知分数比如1B3C，如何设计算法猜词？变种 利口 巴斯散，follow up 没写码，时间不太够，太仓促没答的很好...

第二轮：tech lead老爷爷，设计一个迷宫生成算法，input是迷宫的长，宽，还有起点 终点坐标，返回整个maze，要求必须随机生成，且起点到终点有且只有一条路，且function run一次一定会生成一个valid的迷宫，不会出错，老爷爷给了一点小hint，我脑子里顿时冒出来一个bfs的解，一气呵成写完了，老爷爷看着很满意，说这就

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

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

atrix里面大部分都是0该怎么办？答：用hahsmap记录然后再更新，然后写了几行码，然后还剩5分钟聊天

第五轮：L家跳来的小哥，来了道L家高频，利口 留疤 原题，这题第一个版本写的时候space没有处理好，和面试官一起处理了下corner case，最后还剩10分钟，先讨论了我的码该怎么优化空间，然后问小哥问题

所以请问地里的各位大佬，我这个写题速度是慢了嘛？该如何改进？求各位大佬指点...
最后求个大米...

您好！
本帖隐藏的内容需要积分高于 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

顺便po一下我刚才码的迷宫生成的bfs 和 dfs两个解好了... 再多攒点人品好了

1. import java.util.*;
   
2. 
   
3. public class Maze{
   
4. 
   
5.     int[] start, end;
   
6.     Cell[][] maze;
   
7.     boolean[][] visited;
   
8.     int[][] dirs = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
   
9. 
   
10. 
    
11. 
    
12.     class Cell{
    
13.         boolean up_open;
    
14.         boolean down_open;
    
15.         boolean left_open;
    
16.         boolean right_open;
    
17.     }
    
18. 
    
19.     public Maze(int height, int width, int[] start, int[] end ){
    
20.         maze = new Cell[height][width];
    
21.         visited = new boolean[height][width];
    
22. 
    
23.         for (int i=0; i<maze.length; i++)
    
24.             for (int j=0; j<maze[0].length; j++){
    
25.                 maze[i][j] = new Cell();
    
26.             }
    
27.         
    
28.         this.start = start;
    
29.         this.end = end;
    
30.     }
    
31. 
    
32.     public void bfs_construct(){
    
33.         Queue<int[]> q = new LinkedList();
    
34.         q.offer(start);
    
35.         visited[start[0]][start[1]] = true;
    
36. 
    
37.         while (!q.isEmpty()){
    
38.             int[] pos = q.poll();
    
39.             ArrayList<Integer> dir_set = getRandomDir();
    
40. 
    
41.             for (int i: dir_set){
    
42.                 int new_x = pos[0] + dirs[i][0];
    
43.                 int new_y = pos[1] + dirs[i][1];
    
44.                 if (inBound(new_x,new_y) && !visited[new_x][new_y]){
    
45.                     Cell curr_cell = maze[pos[0]][pos[1]];
    
46.                     Cell next_cell = maze[new_x][new_y];
    
47.                     if (i == 0){
    
48.                         curr_cell.up_open = true;
    
49.                         next_cell.down_open = true;
    
50.                     }
    
51.                     else if (i == 1){
    
52.                         curr_cell.down_open = true;
    
53.                         next_cell.up_open = true;
    
54.                     }
    
55.                     else if (i == 2){
    
56.                         curr_cell.left_open = true;
    
57.                         next_cell.right_open = true;
    
58.                     }
    
59.                     else if (i == 3){
    
60.                         curr_cell.right_open = true;
    
61.                         next_cell.left_open = true;
    
62.                     }
    
63.                     q.offer(new int[]{new_x, new_y});
    
64.                     visited[new_x][new_y] = true;
    
65.                 }
    
66.             }
    
67.         }
    
68.     }
    
69. 
    
70.     public void dfs_construct(int x, int y){
    
71.         if (!inBound(x, y)) return;
    
72.         visited[x][y] = true;
    
73.                 // pick random neighbor
    
74.                 ArrayList<Integer> dir_set = getRandomDir();
    
75.                 for (int i: dir_set){
    
76.                     int new_x = x + dirs[i][0];
    
77.                     int new_y = y + dirs[i][1];
    
78.                     if (inBound(new_x,new_y) && !visited[new_x][new_y]){
    
79.                         Cell curr_cell = maze[x][y];
    
80.                         Cell next_cell = maze[new_x][new_y];
    
81.                         if (i == 0){
    
82.                             curr_cell.up_open = true;
    
83.                             next_cell.down_open = true;
    
84.                         }
    
85.                         else if (i == 1){
    
86.                             curr_cell.down_open = true;
    
87.                             next_cell.up_open = true;
    
88.                         }
    
89.                         else if (i == 2){
    
90.                             curr_cell.left_open = true;
    
91.                             next_cell.right_open = true;
    
92.                         }
    
93.                         else if (i == 3){
    
94.                             curr_cell.right_open = true;
    
95.                             next_cell.left_open = true;
    
96.                         }
    
97.                         dfs_construct(new_x, new_y);
    
98.                     }
    
99.                 }
    
100.     }
     
101. 
     
102.     Random rand = new Random();
     
103.     private ArrayList<Integer> getRandomDir(){
     
104.         ArrayList<Integer> dir_set = new ArrayList();
     
105.         while (dir_set.size()< 4){
     
106.             int d = rand.nextInt(4);
     
107.             if (!dir_set.contains(d)) dir_set.add(d);
     
108.         }
     
109.         return dir_set;
     
110.         
     
111.     }
     
112. 
     
113.     private boolean inBound(int i, int j){
     
114.         if (i < 0 || j < 0 || i > maze.length-1 || j > maze[0].length-1) return false;
     
115.         return true;
     
116.     }
     
117. 
     
118.     public void print(){
     
119.         for (int i=0; i<maze.length; i++){
     
120.             String s1 = "";
     
121.             String s2 = "";
     
122.             String s3 = "";
     
123.             for (int j=0; j<maze[0].length; j++){
     
124.                 Cell curr_cell = maze[i][j];
     
125.                 s1 += " ";
     
126.                 if (curr_cell.up_open) s1 += " "; else s1 += "-";
     
127.                 s1 += " ";
     
128.                
     
129.                 if (curr_cell.left_open) s2 += " "; else s2 += "|";
     
130.                 if (start[0] == i && start[1] == j)
     
131.                     s2 += "S";
     
132.                 else  if (end[0] == i && end[1] == j)
     
133.                     s2 += "E";
     
134.                 else
     
135.                     s2 += " ";
     
136.                 if (curr_cell.right_open) s2 += " "; else s2 += "|";
     
137. 
     
138.                 s3 += " ";
     
139.                 if (curr_cell.down_open) s3 += " "; else s3 += "-";
     
140.                 s3 += " ";
     
141.             }
     
142.             System.out.println(s1);
     
143.             System.out.println(s2);
     
144.             System.out.println(s3);
     
145.         }
     
146.     }
     
147.     public static void main(String[] args){
     
148.         Maze m = new Maze(10, 10, new int[]{1,3}, new int[]{8,7});
     
149.         // m.print();
     
150.         // m.bfs_construct();
     
151.         m.dfs_construct(1,3);
     
152.         m.print();
     
153.         System.out.println();
     
154.     }
     
155. }
     

复制代码

如果是swe的话 应该是没hc了吧..

我两轮code都没写完也送HC了，不知道HC怎么看

c0dingc0ding 发表于 2019-3-2 13:49
我两轮code都没写完也送HC了，不知道HC怎么看

我也看不懂 都是谜。。

yuhaoz3 发表于 2019-3-2 12:27
如果是swe的话 应该是没hc了吧..

跳槽和new grad情况不一样？不过我也就一年半经验。。

楼主请问，第一题的第一个follow up有没有什么好方法吗？
给一个历史猜词记录怎么判断是不是好的猜想？

请问一下楼主，那个generate maze怎么做的呀？

simpleg 发表于 2019-3-2 17:55
princeton 算法书的网站 介绍了一种方法，可以借鉴。

https://algs4.cs.princeton.edu/41graph/Maze.j ...

谢谢回复，不管有没有用，已加米

lz第三轮没给提示吗 需要parent指针才能O(1)