一亩三分地论坛

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

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

Google onsite + SETI 面经

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

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

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

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

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

Onsite:. 1point 3acres 璁哄潧

第一题,给你一个license plate,上面有一串字母和数字,然后再给你一个alphbetacially sorted dictionary(List),让你找出所有包含这个Plate上面的字母重新组合之后的STRING中最短的那个。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

这题不难,只要把Plate上的字母拿出来,记下每个字母出现的频率,然后去dictionary里找所有Match的词就可以了。

follow-up:
能不能不走完整个list就得到结果。

如果事先按照word长度sort,那么找到的那个词一定是满足条件的词中最短的那个。

follow-follow-up:
能否O(1)得到结果。

license plate的长度最大为8,所有字母都是小写字母。事先用Hashmap把所有结果算一遍。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题, 给你2^N只篮球队,return一个代表brackets的String。

这绝壁是我遇到过最奇葩的题。题目本身很简单,但是面试官又不能把要求讲的太清楚(因为题目本身就是要求)。
面试官说尽量让排名靠前的队伍在最后相遇,前二名在决赛相遇,前四名在半决赛相遇。标准解法是先把1-2配对,再把1-4,2-3配对,以此类推。然而我却一直卡在1-3,2-4这对配对也满足要求上,无论面试官如何提示也想不出答案。耗完了45分钟连代码都没来得及写。

第三题,给你一个Matrix,当中有三种Input,Enemy,empty和wall. 你可以在空白处放炸弹,炸死同一column和row里的敌人。但是如果你的那条线上出现了一个wall,那么你就只能炸到这堵墙之前的敌人。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

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

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

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

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

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

第二轮:. 1point3acres.com/bbs
白人大叔。上来问了我一堆乱七八糟的project问题,之后问了一题。. from: 1point3acres.com/bbs
给你一个sorted integer array,找出所有popular number (出现频率大于N/4)。
这题我也答的不好。大叔给了我很多提示,最关键的部分是你只需要找4个array中的关键节点就能得到所有可能的candidate,(N/4,N/2-1,N/2+1,3N/4).我一开始没注意到这个array是sorted,想了半天。
.1point3acres缃
总结:
我之前看到论坛上有人说刷了leetcode5遍都没找到工作。我个人的感觉是Leetcode最多刷两遍,再多对于程序员的提升并没有什么帮助。找工作这种事情要趁早,本人花了美本四年时间想做金融,到头来再想转CS已经落后太多了。如果有正常的实习经验加上不错的基础知识,CS就业还是相对容易的。各位看这些面经也不要指望面试官每次都会考到原题,人家稍微变化一下条件这些题就完全不一样了。


. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴



评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
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-google 1point3acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧
  1. public class PlayerSituation {
  2.        
  3.         public static void main(String[] args) {
  4.                 match(8);
  5.         }
  6.        
  7.         public  static  String match(int n) {
  8.         List<String> mathces = new ArrayList<String>();
  9.         for(int i=1; i<= n; i++){. more info on 1point3acres.com
  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.         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.     public static void helpMatch(List<String> matches, String[] res){
  19.         if(matches.size() == 1) {
  20.             res[0] = matches.get(0);
  21.             return;
  22.         }
  23. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.         List<String> newMatches = new ArrayList<String>();
  25.         int len = matches.size();
  26.         for(int i=0; i< matches.size()/2; i++){
  27.             newMatches.add( "(" + matches.get(i) + "," +  matches.get(len-1-i) + ")");
  28.         }
  29.         helpMatch(newMatches, res);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.     }
  31. }
复制代码
回复 支持 反对

使用道具 举报

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
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
S S E W E
E E S E  S
S S S S S

你在(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解法。能不能直接把每个点的行列都算一遍?

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

使用道具 举报

北岸三叶草 发表于 2016-3-28 02:19:29 | 显示全部楼层
seekerwu 发表于 2016-3-28 01:08. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
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 | 显示全部楼层
所以楼主第三题到底要求什么呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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