在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4844|回复: 13
收起左侧

Google HR, phone and onsite

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

2016(1-3月) 码农类General 本科 全职@Google - 猎头 - HR筛选 Onsite  | Other | fresh grad应届毕业生

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

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

x
上周面完的onsite,recruiter说有一个人还没交feedback。。。。
. from: 1point3acres
去年年底一个recruiter 在 Linkedin 联系我的,一周后打了电话过来。就讲讲我的实习,why cs?等,
我当时边实习边上课,所以问他给一两个月准备,他说没问题,于是就开始加速刷题
买了Leetcode 的subscription,上面中等,简单的都做了个遍,难的挑着做。然后看了些别人的答案,收获很多。
lc discussion forum上高人好多好多有一个老外大神叫StefanPochmann,从他的解法学到了好多python trickery。

. 1point 3acres 论坛


店面还是蛮简单的。onsite基本是leetcode中等那个level的题,没有特别难的,卡住的。他们问的重题也蛮多的。




下面是题:
phone: Given a list of graph nodes, find top K connected component.
BFS + Heap
Follow up: what if the graph is too large, that it cannot be fit into one computer's memor.
Sharding. 牛人云集,一亩三分地


onsite:
1.Flip GameII 的变种,这个一点印象都没有,中间recursive逻辑花了点时间才里清楚。. 1point3acres
Follow up: How to optimise? 答:memorization. Waral 博客有更多文章,
又问: good direction, can you do better?于是想出来几点提高cache utilization的方法。. 一亩-三分-地,独家发布
想到简化input,面试官提示后想到把string简化成tulpe。-google 1point3acres
. 牛人云集,一亩三分地

2.Shortest distance to '1'. Given a matrix with 1s and 2s, find shortest distance from any 2, to any 1.
从所有的2出发,同步做BFS,遇到1就返回。
来源一亩.三分地论坛. follow up问怎么测试,说了几个test case,讨论了一下就完了。. From 1point 3acres bbs
这轮和面试官的交流比较差,他话很少,表情也比较冷。我也没表达清楚自己。讨论复杂度的时候,
我说是O(n^2),n是matrix一边我没说,于是他以为我重复遍历,浪费了5min

. 一亩-三分-地,独家发布
3. Simulate rain in 1 meter side walk. 我刚好前几天做过这个,于是跟面试官讲了,他就换了道题。
Given a board, each cell with different color and position of a cell, find out the perimeter of the shape consists of
all connected same color cells as the given one.. from: 1point3acres


比如,给这个矩阵和(1,1) Blue
W W W W W W
W B  B  B  W W.1point3acres网
W B  W B  B  W
W B  B  B  W W
周长包括中间的那块而内围,再加外围,答案是18。
. more info on 1point3acres

I had a good insite, that for any side of a B, it either connects with another B, or counts in the perimeter.
想到这个就很好做了

. 1point 3acres 论坛


4. 先问了count of two sum smaller, 说做过,并描述了一下几种方法。
其中有一中方法说要用binary search, we can just use bisect_left in python,他要我implement 这个,于是花了10min搞出来。
一个edge case 没考虑,被指出来之后修了一下。. 留学申请论坛-一亩三分地
然后问Median of Two Sorted Arrays,说这个也刚刚前几天做过,于是他没有题了,然后我们就聊了简历。. 牛人云集,一亩三分地
实习的时候做过一个解决logging system unreliability的模块儿,重点讨论了一下那个。

. From 1point 3acres bbs




面完后回酒店又做了一下,发现第一题做的有点问题。逻辑关系没想清楚。。。
. from: 1point3acres
. 围观我们@1point 3 acres


地里面经做了很多,收获很多。希望我的面经也能帮上大家 :D. 留学申请论坛-一亩三分地



-google 1point3acres
补充内容 (2016-3-18 01:43):
今天电话告知悲剧了。。。。。T_T

评分

1

查看全部评分

 楼主| rk_jh 发表于 2016-3-8 11:54:56 | 显示全部楼层
bobzhang2004 发表于 2016-3-8 11:43
谢谢回复, 应该就是按照下面的代码求出component,然后用quick selection或者是heap求出top k吧
.留学论坛-一亩-三分地
恩,是这样。但还可以优化。
connected components 不需要存在res里边儿。可以弄个heap of size K,每次发现一个connected component 之后,跟heap里面最小的一个比较一下。只保留Top K 个connected component 就行。省点memory。
面试官刻意考了这点,应该是比较重要的。
回复 支持 1 反对 0

使用道具 举报

csgtc 发表于 2016-2-21 14:21:37 | 显示全部楼层
LZ牛逼! 等着拿offer了吧, 进hc了吗
回复 支持 反对

使用道具 举报

 楼主| rk_jh 发表于 2016-2-21 14:30:37 | 显示全部楼层
csgtc 发表于 2016-2-21 14:21
LZ牛逼! 等着拿offer了吧, 进hc了吗

应该还没进HC。有一个面试官没提交feedback,所以还在等他。下周应该会有个update
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-2-22 04:13:30 | 显示全部楼层
楼主是本科吗?感觉本科的题目会比硕士大简单一点
回复 支持 反对

使用道具 举报

 楼主| rk_jh 发表于 2016-2-22 05:16:37 | 显示全部楼层
wtcupup 发表于 2016-2-22 04:13
楼主是本科吗?感觉本科的题目会比硕士大简单一点

恩,是本科。我也觉得考得比地里大多数面经题简单。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 00:43:03 | 显示全部楼层
请问“find top K connected component.”是指与其他node链接最多的吗?"Simulate rain in 1 meter side walk"是说用两个array存左边和右边?
“find out the perimeter of the shape consists of all connected same color cells as the given one.”是数B外面的那一层W吗?数的方法是什么呢?. 1point3acres
回复 支持 反对

使用道具 举报

 楼主| rk_jh 发表于 2016-3-8 11:12:12 | 显示全部楼层
bobzhang2004 发表于 2016-3-6 00:43
请问“find top K connected component.”是指与其他node链接最多的吗?"Simulate rain in 1 meter side wa ...

1. Connected component的size是它所含有的node的个数。要求是找最大的K个 Connected component
2.这个题论坛上有,看这里http://www.1point3acres.com/bbs/thread-176388-1-1.html
3.B组成的那个shape的周长,包括内围和外围。方法就是我上面写的,每个B的每个边要么和另外一个B连着,要么属于周长。BFS一下,顺便count属于周长的边就好了。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-8 11:43:15 | 显示全部楼层
rk_jh 发表于 2016-3-8 11:12
1. Connected component的size是它所含有的node的个数。要求是找最大的K个 Connected component
2.这个 ...

谢谢回复, 应该就是按照下面的代码求出component,然后用quick selection或者是heap求出top k吧
  1.     public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
  2.         List<List<Integer>> res = new ArrayList<List<Integer>>();
  3.         if (nodes == null || nodes.size() == 0) {
  4.             return res;
  5.         }
  6.         Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>();
  7.         for (UndirectedGraphNode v : nodes) {
  8.             if (!set.contains(v)) {. 1point 3acres 论坛
  9.                 bfs(v, res, set);
  10.             }
  11.         }
  12.         
  13.         return res;
  14.     }
  15.     .留学论坛-一亩-三分地
  16.     public void bfs(UndirectedGraphNode node, List<List<Integer>> res, Set<UndirectedGraphNode> set) {
  17.         List<Integer> row = new ArrayList<Integer>();
  18.         Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
  19.         queue.offer(node);. 围观我们@1point 3 acres
  20.         set.add(node);
  21.         while (!queue.isEmpty()) {
  22.             UndirectedGraphNode cur = queue.poll();
  23.             row.add(cur.label);
    . 1point 3acres 论坛
  24.             for (UndirectedGraphNode n : cur.neighbors) {
  25.                 if (!set.contains(n)) {
  26.                     set.add(n);
  27.                     queue.offer(n);
  28.                 }
  29.             }
  30.         }
  31.         Collections.sort(row);
  32.         res.add(row);
  33.     }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-8 12:51:12 | 显示全部楼层
rk_jh 发表于 2016-3-8 11:54
. From 1point 3acres bbs恩,是这样。但还可以优化。. Waral 博客有更多文章,
connected components 不需要存在res里边儿。可以弄个heap of size K,每次 ...
. From 1point 3acres bbs
应该是这样的
  1. public class TopKConnectedComponent {
  2. . from: 1point3acres
  3.         class UndirectedGraphNode {
  4.                 int label;
  5.                 ArrayList<UndirectedGraphNode> neighbors;. more info on 1point3acres
  6. . 留学申请论坛-一亩三分地
  7.                 UndirectedGraphNode(int x) {
  8.                         label = x;
  9.                         neighbors = new ArrayList<UndirectedGraphNode>();
  10.                 }. From 1point 3acres bbs
  11.         };.1point3acres网

  12.        
  13.         public List<List<Integer>> getTopConnectedComponet(ArrayList<UndirectedGraphNode> nodes, int k) {
  14.                 List<List<Integer>> res = new ArrayList<List<Integer>>();
  15.                 if (nodes == null || nodes.size() == 0) {
  16.                         return res;
  17.                 }. From 1point 3acres bbs
  18.                 Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>();
  19.                 PriorityQueue<List<Integer>> pq = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>>() {
  20.                         public int compare(List<Integer> l1, List<Integer> l2) {
  21.                                 return l1.size() - l2.size();
  22.                         }
  23.                 });
  24.                 for (UndirectedGraphNode v : nodes) {
  25.                         if (!set.contains(v)) {
  26.                                 List<Integer> candidate = bfs(v, set);
  27.                                 if (pq.size() < k || pq.peek().size() < candidate.size()) {. 围观我们@1point 3 acres
  28.                                         pq.poll();. 一亩-三分-地,独家发布
  29.                                         pq.offer(candidate);
  30.                                 }
  31.                         }
  32.                 }
  33.                 while (!pq.isEmpty()) {
  34.                         res.add(0, pq.poll());
  35.                 }. 1point 3acres 论坛
  36.                 return res;
  37.         }. 一亩-三分-地,独家发布

  38.         public List<Integer> bfs(UndirectedGraphNode node, . 牛人云集,一亩三分地
  39.                         Set<UndirectedGraphNode> set) {. 牛人云集,一亩三分地
  40.                 List<Integer> row = new ArrayList<Integer>();
  41.                 Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
  42.                 queue.offer(node);.本文原创自1point3acres论坛
  43.                 set.add(node);
  44.                 while (!queue.isEmpty()) {
  45.                         UndirectedGraphNode cur = queue.poll();
  46.                         row.add(cur.label);. from: 1point3acres
  47.                         for (UndirectedGraphNode n : cur.neighbors) {. 1point3acres
  48.                                 if (!set.contains(n)) {
  49.                                         set.add(n);. 留学申请论坛-一亩三分地
  50.                                         queue.offer(n);
  51.                                 }
  52.                         }
  53.                 }
  54.                 Collections.sort(row);
  55.                 return row;
  56.         }
  57. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| rk_jh 发表于 2016-3-8 13:40:59 | 显示全部楼层
来源一亩.三分地论坛.
Yep! seems good to me.
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-21 07:54:14 | 显示全部楼层
rk_jh 发表于 2016-3-8 11:12. more info on 1point3acres
1. Connected component的size是它所含有的node的个数。要求是找最大的K个 Connected component
2.这个 ...

楼主能介绍下第三轮的周长为什么是18吗?
回复 支持 反对

使用道具 举报

 楼主| rk_jh 发表于 2016-5-22 06:51:19 | 显示全部楼层
hidden_track 发表于 2016-5-21 07:54
楼主能介绍下第三轮的周长为什么是18吗?

内周外周都算,所以18
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-5-22 11:17:17 | 显示全部楼层
rk_jh 发表于 2016-5-22 06:51
内周外周都算,所以18

还是没懂18是怎么算出来的?题意到底是求什么= =,谢谢楼主
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 01:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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