狗家昂赛特

发个面经攒rp。。。。内推的学长说上周五要送hc，然后惶惶不可终日等了好几天，今天hr告诉学长说上周没送，这周五送，还我浪费掉的感情！！
hr小哥说好的keep me updated，却让内推的人updated，吐槽一下。。。但是hr小哥还是很好的，面试当天还发了一些tips


第一轮，中国小哥，提前15min接我，然后就开始中文blabla聊天了，到时间进去面试，瞬间严肃了，心累累。题目是之前看到的别人面过的题，判断一个围棋棋子是不是alive（当时看的题目是判断一个棋盘是不是死的，感觉更烦。。。）当初看到这题的时候和非cs的室友讨论了半天怎么做，因为当时以为棋子被周围一大圈其他棋子围起来就算dead。面试官一讲完题，心里就拔凉拔凉的，后来不知道怎么镇定下来了，然后就问了一个黑棋被一大圈白棋圈起来算不算dead，他说不算，这下瞬间轻松了哈哈哈。写了个bfs，写完后面试官说我有个小错，后来自己发现改了。之后就是followup，面试官有点解释不清楚，然后就自己说了，然后继续follow up，我自己提了个方法，他不太满意，准备让我写psyd

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

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

ont>最后代码就写了一点点，心里当时已经是死灰一片，最后和他repeat了一下思路，貌似之前他还没有理解我要干什么，最后问他怎么做，说我on the right track。出来后感觉三哥就是个坑，占用那么多时间说其他的。。。

希望hr小哥周五成功送达hc，然后又可以焦灼的等结果了！







补充内容 (2016-10-26 10:26):
求点大米TT

补充内容 (2016-11-1 02:00):
hr小哥说要加面两轮==

画三角形那道题可不可以理解为level order traversal 的变种，bfs那种的。据我观察，每加深一层，就是把一个当前的三角形分成三个三角形（中间的倒三角形不算，这样画出的边也没有重合）写了一下代码，constructor没有详写

1. public class Point {
   
2.         int x, y;
   
3.         public Point() {}
   
4. }
   
5. public class Triangle {
   
6.         Point A, B, C;
   
7.         public Triangle(Point A, Point B, Point C){}
   
8. }
   
9. public Point getMid(Point A, Point B) {
   
10.         int x = (A.x + B.x) / 2, y = (A.y + B.y) / 2; //不考虑double的情况
    
11.         return new Point(x, y);
    
12. }
    
13. 
    
14. public void drawLine(Point A, Point B) {}
    
15. public void drawTri(Triangle tri) {
    
16.         drawLine(tri.A, tri.B);
    
17.         drawLine(tri.B, tri.C);
    
18.         drawLine(tri.A, tri.C);
    
19. }
    
20. public void drawGraph(Point A, Point B, Point C, int depth) {
    
21.         Triangle basic = new Triangle(A, B, C);
    
22.         Queue<Triangle> q = new LinkedList<Triangle>();
    
23.         q.offer(basic);
    
24.         for(int i = 0; i < depth; i++) {
    
25.                 int size = q.size();
    
26.                 for(int j = 0; j < size; j++) {
    
27.                         basic = q.poll();
    
28.                         Point mid_AB = getMid(basic.A, basic.B);
    
29.                         Point mid_AC = getMid(basic.A, basic.C);
    
30.                         Point mid_BC = getMid(basic.B, basic.C);
    
31.                         q.offer(new Triangle(basic.A, mid_AC, mid_AB));
    
32.                         q.offer(new Triangle(basic.B, mid_BC, mid_AB));
    
33.                         q.offer(new Triangle(basic.C, mid_BC, mid_AC));
    
34.                 }
    
35.         }
    
36.         while(!q.isEmpty()) {
    
37.                 drawTri(q.poll());
    
38.         }
    
39. }

复制代码

第一轮：围棋问题，可以用queue做BFS或用recursion做DFS. 判断一片棋子死活就是判断有没有空格邻居。类似Leetcode "number of islands".
我的C++ DFS:

1. int val; // 1: black, 2: white, 0: empty
   
2. 
   
3. // dfs subroutine to explore same color tokens
   
4. bool findEmptyNeighbor(vector<vector<int>>& board, int i, int j) {
   
5.   // didn't find empty grid if out of board
   
6.   if (i < 0 || i > 18 || j < 0 || j > 18
   
7.       // or visited same color token or opponent token
   
8.       || board[i][j] == INT_MAX || board[i][j] == -val) return false;   
   
9.   board[i][j] = INT_MAX; // set as "visited"
   
10.   // explore 4 neighboring grids
    
11.   return  findEmptyNeighbor(board, i-1, j) ||
    
12.           findEmptyNeighbor(board, i+1, j) ||
    
13.           findEmptyNeighbor(board, i, j-1) ||
    
14.           findEmptyNeighbor(board, i, j+1);
    
15. }
    
16. 
    
17. bool isAlive(vector<vector<int>>& board, int i, int j) {
    
18.   // validate given location (i, j)
    
19.   if (i < 0 || i > 18 || j < 0 || j > 18 || board[i][j] == 0) return false;  
    
20.   val = board[i][j];
    
21.   return findEmptyNeighbor(board, i, j);
    
22. }

复制代码

补充内容 (2016-10-26 11:23):
我用的就是实际的围棋棋盘19*19, 但如果是一般2D grid的话也同样实现。

1. import turtle
   
2. 
   
3. 
   
4. ninja = turtle.Turtle()
   
5. ninja.speed(10)
   
6. 
   
7. 
   
8. class Point(object):
   
9.     def __init__(self, x, y):
   
10.         self.x = x
    
11.         self.y = y
    
12. 
    
13. 
    
14. def draw_line(p1, p2):
    
15.     ninja.penup()
    
16.     ninja.goto(p1.x, p1.y)
    
17.     ninja.pendown()
    
18.     ninja.goto(p2.x, p2.y)
    
19. 
    
20. 
    
21. def draw_trangle(p1, p2, p3):
    
22.     draw_line(p1, p2)
    
23.     draw_line(p2, p3)
    
24.     draw_line(p3, p1)
    
25. 
    
26. 
    
27. def dfs(p1, p2, p3, depth):
    
28.     draw_trangle(p1, p2, p3)
    
29.     if depth:
    
30.         m1 = Point((p1.x+p2.x)/2., (p1.y+p2.y)/2.)
    
31.         m2 = Point((p2.x+p3.x)/2., (p2.y+p3.y)/2.)
    
32.         m3 = Point((p3.x+p1.x)/2., (p3.y+p1.y)/2.)
    
33.         depth -= 1
    
34.         dfs(p1, m1, m3, depth)
    
35.         dfs(p2, m1, m2, depth)
    
36.         dfs(p3, m2, m3, depth)
    
37. 
    
38. 
    
39. if __name__ == '__main__':
    
40.     p1 = Point(-100, 0)
    
41.     p2 = Point(100, 0)
    
42.     p3 = Point(0, 173)
    
43.     dfs(p1, p2, p3, 2)
    
44.     turtle.mainloop()

复制代码

我用python turtle写了个画三角形那题的小脚本～

补充内容 (2016-10-27 05:12):
triangle写错了。。。

可以详细说说棋子那道题吗？

棋子那道题的follow up是什么啊？

chestnut9919 发表于 2016-10-26 09:47
可以详细说说棋子那道题吗？

最近很多帖子都出现过，输入一个围棋棋盘，和一个黑棋子坐标，判断这个棋子是活是死，就是search找有没有和黑棋子相连的空格

mingruiyrh 发表于 2016-10-26 09:56
棋子那道题的follow up是什么啊？

比如现在每个棋子都有一个status变量，代表这个地方是死是活，问题是当下一个棋子的时候如何更新棋子的status

jiongjiongyoush 发表于 2016-10-26 09:57
最近很多帖子都出现过，输入一个围棋棋盘，和一个黑棋子坐标，判断这个棋子是活是死，就是search找有没有 ...

到底怎么才算活啊？为什么被一圈白子围起来还不算死？

chestnut9919 发表于 2016-10-26 10:32
到底怎么才算活啊？为什么被一圈白子围起来还不算死？

必须要紧紧的包围着，不能有空！！！这是重点
  XXX
XOO X
  XXX
比如上图O就是活的

lz哪天面的？

chestnut9919 发表于 2016-10-26 10:32
到底怎么才算活啊？为什么被一圈白子围起来还不算死？

围棋规则：一片相连（也可以单个）的同色棋子当没有“气”的时候就算死棋，而“气“指的是和这片棋子相邻的空位。例如一个单个在(0,0)的白棋要死必须是紧相邻的4个位置(-1,0), (1,0), (0,1), (0,-1)都被黑棋占据。如果只是一圈黑棋远远(中间有空隙)地包围了一圈的话不算白棋死。

LZ是担心面试官用这个“非正规”的规则，那就不容易判断了。

uranus23 发表于 2016-10-26 10:36
lz哪天面的？

10.7
等了快三周了。。