一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2192|回复: 33
收起左侧

狗家昂赛特

[复制链接] |试试Instant~ |关注本帖
jiongjiongyoush 发表于 2016-10-26 09:21:17 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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


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

第二轮,外国(白人?)大叔,长得有点像三哥,进来的时候以为是三哥吓死我了。还有一个超帅的shadow白人小哥,sd毕业的,他先来的,自我介绍是shadow,最后聊天的时候他说还没面过人,还说我的学校project比他们难,小哥居然看了我的简历。。。题目是topological sorting,和course schedule ii一样,input什么的都不给,我强行拐到course schedule ii的input format。用了bfs写的,写的过程中变量名一直不统一,被大叔一直问,尴尬。。。写完之后让跑test,分析复杂度,居然分析出来是n^2, 最后问我能怎么优化,我回了句,i think all the parts are necessary,大叔以为unnecessary,准备追问,小哥说我说的是necessary,之后就问我知道这个算法叫什么么,我说topological sorting,他问知道optimal solution么,我说不知道,他说fair enough(不太记得了)。。之后就问可不可以用多个machine解决这个问题。感觉这轮还可以,有说有笑的。-google 1point3acres
-google 1point3acres
午饭,加拿大来的三哥==随便聊聊,lz表示不想和三哥聊天,天真的觉得遇到个三哥之后就不会遇到三哥了。

第三轮,中国大姐,很冷淡。。。吃饭回来在房间门口遇到她了,打了个招呼,用英语聊了聊,感觉没有大哥那么热情。第一题,给一个tree,一个api,check一个node是不是要被delete,返回被delete之后的tree的集合,一看就是recursion,然后边写边说,写完之后发现重复代码太多,然后修改了一下,跑了个test,当时心里还在纠结解法对不对,跑test有点心不在焉,一个test重复了两遍,后来她拍了个照就结束了,长舒一口气。本来以为快要结束了,才发现过了20min,又被甩了第二题,给一个square matrix,一个input k,输出k * k 大小矩阵的 sum结果,相当于computer vision给图像filter一样。看了题也是心里呵呵大。。。提了个解法,用类似range sum的方法保存prefix sum,她说可以就写,然后写的时候也是心累,i j已经要分不清了,过程中自己就一直嘀咕,她感觉就是瞅着我的代码抠,问了两个问题貌似,最后时间到了没写完,问她我的方法对吗,她说对的,只是时间不够了,拍了照走人。

第四轮,“期待已久”的三哥登场了,上来寒暄问我要不要上厕所喝水blabla,之后就问了简历里的project!excume me==然后出了一道鬼知道干什么的题,题目没法描述,哪天画个图片再贴上来,和图形有关的,三角形套三角形,问怎么输出一堆点,然后用已知的画线api生成某一depth的图形,不知道以前面经里有没有这道题。然后就是一直没思路,问hint也没什么有用信息,三哥就说写个简单的情况,然后突然想出点思路,然后三哥一直抠细节,问的心烦,一会问这一会问那,根本没法思考,然后看着电脑的时间不多了,心态也不好了,最后代码就写了一点点,心里当时已经是死灰一片,最后和他repeat了一下思路,貌似之前他还没有理解我要干什么,最后问他怎么做,说我on the right track。出来后感觉三哥就是个坑,占用那么多时间说其他的。。。


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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
补充内容 (2016-10-26 10:26):
求点大米TT

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

评分

9

查看全部评分

本帖被以下淘专辑推荐:

海盗包子 发表于 2016-10-27 03:45:36 | 显示全部楼层
画三角形那道题可不可以理解为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. public void drawLine(Point A, Point B) {}
  14. public void drawTri(Triangle tri) {
  15.         drawLine(tri.A, tri.B);
  16.         drawLine(tri.B, tri.C);
  17.         drawLine(tri.A, tri.C);
  18. }
  19. public void drawGraph(Point A, Point B, Point C, int depth) {
  20.         Triangle basic = new Triangle(A, B, C);
  21.         Queue<Triangle> q = new LinkedList<Triangle>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.         q.offer(basic);
  23.         for(int i = 0; i < depth; i++) {
  24.                 int size = q.size();
  25.                 for(int j = 0; j < size; j++) {
    -google 1point3acres
  26.                         basic = q.poll();
  27.                         Point mid_AB = getMid(basic.A, basic.B);
  28.                         Point mid_AC = getMid(basic.A, basic.C);. Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                         Point mid_BC = getMid(basic.B, basic.C);
  30.                         q.offer(new Triangle(basic.A, mid_AC, mid_AB));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31.                         q.offer(new Triangle(basic.B, mid_BC, mid_AB));
  32.                         q.offer(new Triangle(basic.C, mid_BC, mid_AC));
  33.                 }. From 1point 3acres bbs
  34.         }. visit 1point3acres.com for more.
  35.         while(!q.isEmpty()) {
  36.                 drawTri(q.poll());
  37.         }
  38. }
复制代码
回复 支持 1 反对 0

使用道具 举报

chestnut9919 发表于 2016-10-26 09:47:52 | 显示全部楼层
可以详细说说棋子那道题吗?
回复 支持 反对

使用道具 举报

mingruiyrh 发表于 2016-10-26 09:56:33 | 显示全部楼层
棋子那道题的follow up是什么啊?
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 09:57:48 | 显示全部楼层
chestnut9919 发表于 2016-10-26 09:47
可以详细说说棋子那道题吗?
. From 1point 3acres bbs
最近很多帖子都出现过,输入一个围棋棋盘,和一个黑棋子坐标,判断这个棋子是活是死,就是search找有没有和黑棋子相连的空格
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 10:00:03 | 显示全部楼层
mingruiyrh 发表于 2016-10-26 09:56. more info on 1point3acres.com
棋子那道题的follow up是什么啊?

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

使用道具 举报

chestnut9919 发表于 2016-10-26 10:32:23 | 显示全部楼层
jiongjiongyoush 发表于 2016-10-26 09:57
最近很多帖子都出现过,输入一个围棋棋盘,和一个黑棋子坐标,判断这个棋子是活是死,就是search找有没有 ...

到底怎么才算活啊?为什么被一圈白子围起来还不算死?
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 10:35:49 | 显示全部楼层
chestnut9919 发表于 2016-10-26 10:32
到底怎么才算活啊?为什么被一圈白子围起来还不算死?

必须要紧紧的包围着,不能有空!!!这是重点
  XXX
XOO X
  XXX
比如上图O就是活的
回复 支持 反对

使用道具 举报

uranus23 发表于 2016-10-26 10:36:55 | 显示全部楼层
lz哪天面的?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 10:45:51 | 显示全部楼层
chestnut9919 发表于 2016-10-26 10:32
到底怎么才算活啊?为什么被一圈白子围起来还不算死?

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

LZ是担心面试官用这个“非正规”的规则,那就不容易判断了。
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 10:52:28 | 显示全部楼层
.鐣欏璁哄潧-涓浜-涓夊垎鍦
10.7. 1point 3acres 璁哄潧
等了快三周了。。
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-26 10:56:36 | 显示全部楼层
zzgzzm 发表于 2016-10-26 10:45
围棋规则:一片相连(也可以单个)的同色棋子当没有“气”的时候就算死棋,而“气“指的是和这片棋子相邻 ...

我明白啦!多谢!
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-26 10:58:53 | 显示全部楼层
jiongjiongyoush 发表于 2016-10-26 10:35.鏈枃鍘熷垱鑷1point3acres璁哄潧
必须要紧紧的包围着,不能有空!!!这是重点
  XXX
XOO X
. 1point3acres.com/bbs
明白啦~~ 那就dfs/bfs找到空位就返回true就行了 btw楼主最后一题思路是什么?乍一看有点像quad tree但三角形和depth又是什么。。
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 11:01:25 | 显示全部楼层
chestnut9919 发表于 2016-10-26 10:58. 1point3acres.com/bbs
明白啦~~ 那就dfs/bfs找到空位就返回true就行了 btw楼主最后一题思路是什么?乍一看有点像quad tree但三 ...

TT我一会画个图po上来
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 11:09:44 | 显示全部楼层
输入三个顶点和depth
输出一堆点
问somehow,用这些点两两连线把depth的图画出来
IMG_1496.PNG
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 11:19:32 | 显示全部楼层
第一轮:围棋问题,可以用queue做BFS或用recursion做DFS. 判断一片棋子死活就是判断有没有空格邻居。类似Leetcode "number of islands".
我的C++ DFS:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  1. int val; // 1: black, 2: white, 0: empty

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



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

使用道具 举报

mingruiyrh 发表于 2016-10-26 11:32:41 | 显示全部楼层
第二轮 topological sort的复杂度不是O(V + E)吗?有点疑惑
回复 支持 反对

使用道具 举报

uranus23 发表于 2016-10-26 11:33:25 | 显示全部楼层
jiongjiongyoush 发表于 2016-10-25 21:52
10.7
等了快三周了。。

thx!good luck!
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 11:43:49 | 显示全部楼层

同好运。。看到你比我晚面
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 11:44:37 | 显示全部楼层
mingruiyrh 发表于 2016-10-26 11:32
第二轮 topological sort的复杂度不是O(V + E)吗?有点疑惑
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就是遍历那个dependecy pair有n2的复杂度。。。
回复 支持 反对

使用道具 举报

 楼主| jiongjiongyoush 发表于 2016-10-26 11:48:09 | 显示全部楼层
zzgzzm 发表于 2016-10-26 11:19
第一轮:围棋问题,可以用queue做BFS或用recursion做DFS. 判断一片棋子死活就是判断有没有空格邻居。类似Le ...

findEmptyNeighbor 没有return true的情况==感觉把棋盘改了不太好. visit 1point3acres.com for more.
看来很精通围棋啊!棋盘大小都知道,厉害
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 05:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表