《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4404|回复: 13
收起左侧

Google HR, phone and onsite

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

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

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

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

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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.鏈枃鍘熷垱鑷1point3acres璁哄潧

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




下面是题:
phone: Given a list of graph nodes, find top K connected component.. visit 1point3acres.com for more.
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逻辑花了点时间才里清楚。
Follow up: How to optimise? 答:memorization
又问: good direction, can you do better?于是想出来几点提高cache utilization的方法。
想到简化input,面试官提示后想到把string简化成tulpe。


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,讨论了一下就完了。
这轮和面试官的交流比较差,他话很少,表情也比较冷。我也没表达清楚自己。讨论复杂度的时候,
我说是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.

. 1point 3acres 璁哄潧
比如,给这个矩阵和(1,1) Blue
W W W W W W
W B  B  B  W W.鐣欏璁哄潧-涓浜-涓夊垎鍦
W B  W B  B  W. 1point3acres.com/bbs
W B  B  B  W W
周长包括中间的那块而内围,再加外围,答案是18。. 1point 3acres 璁哄潧


I had a good insite, that for any side of a B, it either connects with another B, or counts in the perimeter..鏈枃鍘熷垱鑷1point3acres璁哄潧
想到这个就很好做了. more info on 1point3acres.com

. From 1point 3acres bbs


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,说这个也刚刚前几天做过,于是他没有题了,然后我们就聊了简历。.1point3acres缃
实习的时候做过一个解决logging system unreliability的模块儿,重点讨论了一下那个。
. Waral 鍗氬鏈夋洿澶氭枃绔,




. 鍥磋鎴戜滑@1point 3 acres
面完后回酒店又做了一下,发现第一题做的有点问题。逻辑关系没想清楚。。。

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

. more info on 1point3acres.com
地里面经做了很多,收获很多。希望我的面经也能帮上大家 :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存左边和右边?. 鍥磋鎴戜滑@1point 3 acres
“find out the perimeter of the shape consists of all connected same color cells as the given one.”是数B外面的那一层W吗?数的方法是什么呢?
回复 支持 反对

使用道具 举报

 楼主| 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属于周长的边就好了。
回复 支持 反对

使用道具 举报

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>>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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)) {
  9.                 bfs(v, res, set);
  10.             }
  11.         }
  12.         
  13.         return res;
  14.     }
  15.     -google 1point3acres
  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);
  20.         set.add(node);
    . 1point3acres.com/bbs
  21.         while (!queue.isEmpty()) {
  22.             UndirectedGraphNode cur = queue.poll();
  23.             row.add(cur.label);
  24.             for (UndirectedGraphNode n : cur.neighbors) {. 1point3acres.com/bbs
  25.                 if (!set.contains(n)) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.                     set.add(n);
  27.                     queue.offer(n);
  28.                 }
  29.             }
  30.         }. 1point3acres.com/bbs
  31.         Collections.sort(row);
  32.         res.add(row);
  33.     }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-8 12:51:12 | 显示全部楼层
rk_jh 发表于 2016-3-8 11:54
恩,是这样。但还可以优化。
connected components 不需要存在res里边儿。可以弄个heap of size K,每次 ...

应该是这样的
  1. public class TopKConnectedComponent {

  2.         class UndirectedGraphNode {
  3.                 int label;
  4.                 ArrayList<UndirectedGraphNode> neighbors;
  5. . Waral 鍗氬鏈夋洿澶氭枃绔,
  6.                 UndirectedGraphNode(int x) {
  7.                         label = x;
  8.                         neighbors = new ArrayList<UndirectedGraphNode>();
  9.                 }
  10.         };. 1point3acres.com/bbs

  11.        
  12.         public List<List<Integer>> getTopConnectedComponet(ArrayList<UndirectedGraphNode> nodes, int k) {
  13.                 List<List<Integer>> res = new ArrayList<List<Integer>>();
  14.                 if (nodes == null || nodes.size() == 0) {
  15.                         return res;
  16.                 }
  17.                 Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>();
  18.                 PriorityQueue<List<Integer>> pq = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>>() {
  19.                         public int compare(List<Integer> l1, List<Integer> l2) {
  20.                                 return l1.size() - l2.size();
  21.                         }. 鍥磋鎴戜滑@1point 3 acres
  22.                 });
  23.                 for (UndirectedGraphNode v : nodes) {
  24.                         if (!set.contains(v)) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25.                                 List<Integer> candidate = bfs(v, set);
  26.                                 if (pq.size() < k || pq.peek().size() < candidate.size()) {
  27.                                         pq.poll();
  28.                                         pq.offer(candidate);
  29.                                 }
  30.                         }
  31.                 }
  32.                 while (!pq.isEmpty()) {
  33.                         res.add(0, pq.poll());
  34.                 }
  35.                 return res;
  36.         }
  37. . 1point3acres.com/bbs
  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);
  43.                 set.add(node);
  44.                 while (!queue.isEmpty()) {
  45.                         UndirectedGraphNode cur = queue.poll();
  46.                         row.add(cur.label);
  47.                         for (UndirectedGraphNode n : cur.neighbors) {
  48.                                 if (!set.contains(n)) {
  49.                                         set.add(n);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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
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吗?
. 1point3acres.com/bbs
内周外周都算,所以18
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 22:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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