狗家阳谷挂经 攒人品

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

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

第二轮：tech lead老爷爷，设计一个迷宫生成算法，input是迷宫的长，宽，还有起点 终点坐标，返回整个maze，要求必须随机生成，且起点到终点有且只有一条路，且function run一

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