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


一亩三分地论坛

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

Google onsite + SETI 面经

[复制链接] |试试Instant~ |关注本帖
seekerwu 发表于 2016-3-27 01:37:59 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Google - 网上海投 - 技术电面 Onsite |Failfresh grad应届毕业生

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

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

x
楼主UW-Madison的本科,前四年学了经济数学统计,但从去年开始想转CS,之前面了Amazon ONSITE跪了,无CS实习经历,Leetcode刷了一遍。
03/04的Google onsite,面完后一周HR打电话说结果不够好,但是SETI的TEAM还有空位,要求加面两轮。 03/23加了两轮电面,结果还是跪了。

Onsite:
-google 1point3acres
第一题,给你一个license plate,上面有一串字母和数字,然后再给你一个alphbetacially sorted dictionary(List),让你找出所有包含这个Plate上面的字母重新组合之后的STRING中最短的那个。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这题不难,只要把Plate上的字母拿出来,记下每个字母出现的频率,然后去dictionary里找所有Match的词就可以了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

follow-up:
能不能不走完整个list就得到结果。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果事先按照word长度sort,那么找到的那个词一定是满足条件的词中最短的那个。-google 1point3acres

follow-follow-up:
能否O(1)得到结果。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
license plate的长度最大为8,所有字母都是小写字母。事先用Hashmap把所有结果算一遍。. Waral 鍗氬鏈夋洿澶氭枃绔,

第二题, 给你2^N只篮球队,return一个代表brackets的String。

这绝壁是我遇到过最奇葩的题。题目本身很简单,但是面试官又不能把要求讲的太清楚(因为题目本身就是要求)。
面试官说尽量让排名靠前的队伍在最后相遇,前二名在决赛相遇,前四名在半决赛相遇。标准解法是先把1-2配对,再把1-4,2-3配对,以此类推。然而我却一直卡在1-3,2-4这对配对也满足要求上,无论面试官如何提示也想不出答案。耗完了45分钟连代码都没来得及写。
. from: 1point3acres.com/bbs
第三题,给你一个Matrix,当中有三种Input,Enemy,empty和wall. 你可以在空白处放炸弹,炸死同一column和row里的敌人。但是如果你的那条线上出现了一个wall,那么你就只能炸到这堵墙之前的敌人。. 1point3acres.com/bbs

这题是个华人大叔面的,全程用中文,还不断的提示我。虽然最后没有过但我还是很感激他。

正确答案用两遍dp,一遍从左上到右下,算出向上和向左能炸到的最多的敌人数量。第二遍从右下到左上,算出向下和向右能炸到的最多的敌人数量。在这个过程中就能算出最大的和,不用再走第三遍。

第四题,leetcode search in 2D matrix II.

一个三哥面的,最优解是Linear,可是我从头到尾也没想出来。最后只好把naive solution写了一遍。

现在回头看,有人说google的hiring bar降低了,我不完全同意。虽然说本人之前没有工作经验,但这些面试题对于算法的熟悉程序要求还是很高的。面试完一周HR来了BAD NEWS,要求加面。

SETI 电面:
第一轮:
(a): 给你一个array,return所有Non-zero的Index range
(b): 给你两个binary search tree,一大一小,问你大的有没有包括小的。
这两题连leetcode easy都不到,我就不Po解法了。面我的是个黑胖子,早上11点才来上班。当时我感觉就不好,结果果然跪了。值得一提的是SETI会专门问你写哪些test case的问题。

第二轮:
白人大叔。上来问了我一堆乱七八糟的project问题,之后问了一题。
给你一个sorted integer array,找出所有popular number (出现频率大于N/4)。
这题我也答的不好。大叔给了我很多提示,最关键的部分是你只需要找4个array中的关键节点就能得到所有可能的candidate,(N/4,N/2-1,N/2+1,3N/4).我一开始没注意到这个array是sorted,想了半天。

总结:
我之前看到论坛上有人说刷了leetcode5遍都没找到工作。我个人的感觉是Leetcode最多刷两遍,再多对于程序员的提升并没有什么帮助。找工作这种事情要趁早,本人花了美本四年时间想做金融,到头来再想转CS已经落后太多了。如果有正常的实习经验加上不错的基础知识,CS就业还是相对容易的。各位看这些面经也不要指望面试官每次都会考到原题,人家稍微变化一下条件这些题就完全不一样了。.鐣欏璁哄潧-涓浜-涓夊垎鍦


. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. visit 1point3acres.com for more.


评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 48
bobzhang2004 发表于 2016-3-27 14:12:50 | 显示全部楼层
请问“license plate的长度最大为8,所有字母都是小写字母。事先用Hashmap把所有结果算一遍。”是什么意思?最短string,不一定是这八个字母吧,可以更多吧,比如10个那么求8个字母的permutation没有用啊
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-27 14:25:18 | 显示全部楼层
第二轮其实是面经题吧
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=138158&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%255B3046%255D%255Bvalue%255D%3D1%26searchoption%255B3046%255D%255Btype%255D%3Dradio&page=1
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  1. public class PlayerSituation {
  2.         . 1point3acres.com/bbs
  3.         public static void main(String[] args) {
  4.                 match(8);
  5.         }. from: 1point3acres.com/bbs
  6.        
  7.         public  static  String match(int n) {
  8.         List<String> mathces = new ArrayList<String>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.         for(int i=1; i<= n; i++){
  10.             mathces.add(Integer.toString(i));
  11.         }
  12.         String[] res= new String[1];
  13.         helpMatch(mathces, res);
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.         System.out.println(res[0]); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         return res[0];
  16.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.         -google 1point3acres
  18.     public static void helpMatch(List<String> matches, String[] res){
  19.         if(matches.size() == 1) {.1point3acres缃
  20.             res[0] = matches.get(0);
  21.             return;. 1point 3acres 璁哄潧
  22.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  23.         List<String> newMatches = new ArrayList<String>();
  24.         int len = matches.size();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.         for(int i=0; i< matches.size()/2; i++){
  26.             newMatches.add( "(" + matches.get(i) + "," +  matches.get(len-1-i) + ")");
  27.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.         helpMatch(newMatches, res);
  29.     }
  30. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-27 14:27:07 | 显示全部楼层
还是没看懂楼主第三轮的意思。这个题就是flower and garden吧,从左向右算一遍,从上到下算一遍,时间复杂度O(n^2)
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-3-28 00:33:26 | 显示全部楼层
谷歌的题目好灵活
回复 支持 反对

使用道具 举报

 楼主| seekerwu 发表于 2016-3-28 00:43:18 | 显示全部楼层
bobzhang2004 发表于 2016-3-27 14:27
还是没看懂楼主第三轮的意思。这个题就是flower and garden吧,从左向右算一遍,从上到下算一遍,时间复杂 ...

比如下面这个matrix:

S = space, E = enemy, W = wall
. 1point3acres.com/bbs
S S E W E
E E S E  S
S S S S S . 鍥磋鎴戜滑@1point 3 acres
. From 1point 3acres bbs
你在(0,0)这个位置本来可以炸到(1,0),(0,2),(0,4)三个位置的敌人,但是因为(0,3)有堵墙,你现在在(0,0)放炸弹只能炸到两个敌人: (1,0),(0,2)。
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-3-28 00:43:26 | 显示全部楼层
感觉解题能力不等于刷题遍数。我之前刷了一遍leetcode面试照样面得不好。还是得把每题都融会贯通。LZ转CS的可以看看普林斯顿的算法书,讲得非常清楚。
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-3-28 00:48:19 | 显示全部楼层
我在想炸弹人那题貌似dp得走四遍吧。。
回复 支持 反对

使用道具 举报

 楼主| seekerwu 发表于 2016-3-28 01:06:37 | 显示全部楼层
chenyuhaohy 发表于 2016-3-28 00:48
我在想炸弹人那题貌似dp得走四遍吧。。

两遍就行,第一遍存下左上的值,第二遍算出右下的值的同时加上之前算出的左上的值
回复 支持 反对

使用道具 举报

 楼主| seekerwu 发表于 2016-3-28 01:08:15 | 显示全部楼层
bobzhang2004 发表于 2016-3-27 14:12
请问“license plate的长度最大为8,所有字母都是小写字母。事先用Hashmap把所有结果算一遍。”是什么意思 ...

dictionary是给定的,你可以把license plate的permutation都算一遍,把每个permutation对应的结果存到hashmap里
回复 支持 反对

使用道具 举报

chenyuhaohy 发表于 2016-3-28 01:55:41 | 显示全部楼层
还是不太理解dp解法。能不能直接把每个点的行列都算一遍?. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-3-28 02:47):
不过每个点算行列最坏复杂度有O(n^3)了,用DP从左上和右下的话,貌似遇到墙就得停下吧,不然就重复了。
回复 支持 反对

使用道具 举报

北岸三叶草 发表于 2016-3-28 02:19:29 | 显示全部楼层
seekerwu 发表于 2016-3-28 01:08. 1point 3acres 璁哄潧
dictionary是给定的,你可以把license plate的permutation都算一遍,把每个permutation对应的结果存到has ...

举个例子的话,如果license plate是"abc76543", dictionary list 是【"abdcz", "abzc", "abzcf"】,这样应该找到"abzc"?那样怎么才能O(1)。。。不太明白hashmap的key和value都存什么?
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-28 06:10:39 | 显示全部楼层
弱弱的问一句第一题license plate记下为什么要记下每个字母的频率啊?
回复 支持 反对

使用道具 举报

say543 发表于 2016-3-31 14:13:40 | 显示全部楼层
seekerwu 发表于 2016-3-28 01:08
dictionary是给定的,你可以把license plate的permutation都算一遍,把每个permutation对应的结果存到has ...

o(1)的solution 还是不懂 就算dict 给定 然后plate enumeration 仍然须要 一个一个word check hashmap怎么用呢? 感谢LZ
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-9 08:42:45 | 显示全部楼层
所以楼主第三题到底要求什么呢?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 06:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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