一亩三分地论坛

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

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

Google Pittsburgh Onsite (两则-自己+同学)

[复制链接] |试试Instant~ |关注本帖
湿太大苞谷 发表于 2016-3-2 13:13:35 | 显示全部楼层 |阅读模式

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

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

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

x
发一下google pittsburgh onsite 的面经,先帮同学发一个他的,然后下面是我自己的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个是我同学的,他的具体思路我就不知道了,所以要讨论的话楼主本身就不太清楚了,要是后面楼主本身的题可以讨论。

第一轮:就是给你一个string 比如“11121315”这样的,里面有连续数字,只有一个漏了,找出漏掉的数字。
第二轮:server 问题,给每个用户一个每秒访问限制,写个方法,超过限制返回false,不超过返回true,空间复杂度要求(o1)。
第三轮:先是一道代码题 partition,等于target放后面 ,不等于的放前面。然后follow一个算法题不用写代码,就是leetcode shorted distance from buildings那道。
第四轮:给一个商品名字ABC (ABC是三个单词,然后一个商品描述XYZABC... 就是判断 描述是否存在子字符串是ABC的permutation 要求O(N).
. 1point3acres.com/bbs
然后是我自己的,说google面试对女生简单的出来我保证不打死你,我整个面试两轮一脸懵逼:
第一轮:上来直接做题,小哥说猜单词,两个人玩游戏,一个人心里想一个词,另一个人要猜,每一次猜一个词会去判断里面有几个字母是符合的,符合的话就有一分,每次会告诉你猜的这个单词得多少分,但是不告诉你哪些字母是对的,也不告诉你顺序,最后要求实现一个function猜出原本的那个词。这一轮我是没写完的,也不太知道要怎么做,最后写了一些伪码,估计这一轮是跪了。。。

第二轮:一开始是个略简单的,说给一个字符串数组,要写serialize和deserialize的方法,字符串里可能会出现任何可能的字符。所以这个题是不能随便给分隔符的,我最后是用长度+分割符来最serialize的,test case乱七八糟很多,每说一个说差不多了吧,小哥就会说what if。。。任何这个做完了做了另一个,就是之前有人遇到过的dp,给排硬币,每一堆有不同的金额,然后两个人玩,每次从左边或者右边拿,判断先拿的那个人会不会拿的金额总数更多。这是一个区间dp吧,勉勉强强把代码写完。

第三轮:这一轮应该算是最简单的,说给一个stream,这个stream有一个value和一个时间,然后给一个time window,在这个time window里,如果有重复的value就不print,如果不重复出现的就要print,对于已经出现过的value,如果超过了这个time window也要输出。这个我是用了一个hashmap去记了每个value的最后一次出现的时间,然后对于每个新来的stream,去判断有没有在map里和有没有超时来输出,这个是最初的解法。follow up是如果一个单词出现过之后就再也没有出现了会怎么样,然后我说浪费内存一直存在map里,然后他就说你要怎么办,然后就是用了一个heap,去从map不断删除超过一定阈值没有出现的单词。这一轮是唯一一轮比较顺畅的。

第四轮:这一轮又是一脸懵逼,说一群小伙伴出去旅游,A欠B的钱,B欠C的钱,C欠A的钱之类的,然后要找到最小的交易次数使得每个人的balance都能平衡,不在乎谁和谁交易,只要最后能平衡所有的钱。这个题一上来真的是完全不会,一直想用图去做,结果面试官说不用想那么复杂,最后几乎是她一步一步带着我做出来的,算是把代码写出来了吧,我觉得遇到这个题的还是跟面试官交流吧,直接写出解法稍微有点太过了,她会给很多提示的,但是这个面试官口音有点奇怪,虽然是白人,要很认真听才能听明白。。。

整体感觉就是真的不简单啊,虐到哭,还没有结果只能靠命了。。。


评分

2

查看全部评分

aiwojiujiu 发表于 2016-3-16 13:10:01 | 显示全部楼层
楼主可否详细说说第三题,stream里面每一个元素包含一个时间和一个value吗?
可否举个例子?
回复 支持 1 反对 0

使用道具 举报

lys0716 发表于 2016-3-2 13:17:02 | 显示全部楼层
楼主如果进了,明年求内推!
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-3-2 13:22:14 | 显示全部楼层
第四轮那个题在以前的面筋里见到过 不知道谁有比较好的solution

补充内容 (2016-3-2 14:58):
第四轮的题目: http://stackoverflow.com/questio ... required-to-get-the

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

kidzlike 发表于 2016-3-2 13:47:37 | 显示全部楼层
2.2要用dp+sg函数做,博弈题的标准套路。 第一轮我觉得应该是图的dfs+剪枝这样。。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-3-2 14:43:54 | 显示全部楼层
感觉楼主好倒霉 碰到的题目比同学的难那么多
回复 支持 反对

使用道具 举报

Jailf 发表于 2016-3-2 15:20:04 | 显示全部楼层
楼主总结的好详细,十分感谢!
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-2 16:11:57 | 显示全部楼层
猜单词不太明白。比如假如已经推测出来是3个字母ABC,我们如何知道到底是ABC还是BAC或其它排列呢?按照题目意思,猜ABC或者BAC都是得3分吧?是不是应该评分还有一条:位置也对得更多的分?
回复 支持 反对

使用道具 举报

 楼主| 湿太大苞谷 发表于 2016-3-3 02:02:41 | 显示全部楼层
kidzlike 发表于 2016-3-2 13:47
2.2要用dp+sg函数做,博弈题的标准套路。 第一轮我觉得应该是图的dfs+剪枝这样。。。

第一题不知道要怎么dfs,因为不知道顺序。。。
回复 支持 反对

使用道具 举报

 楼主| 湿太大苞谷 发表于 2016-3-3 02:17:21 | 显示全部楼层
wtcupup 发表于 2016-3-2 14:43
感觉楼主好倒霉 碰到的题目比同学的难那么多
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对啊,虐哭。。。
回复 支持 反对

使用道具 举报

 楼主| 湿太大苞谷 发表于 2016-3-3 02:18:08 | 显示全部楼层
googlerr 发表于 2016-3-2 16:11
猜单词不太明白。比如假如已经推测出来是3个字母ABC,我们如何知道到底是ABC还是BAC或其它排列呢?按照题目 ...
-google 1point3acres
对,就是只看字母是不是符合,不看顺序,完全不知道顺序,ABC和BAC都是3分,所以才觉得很难。。。最后是要把原词猜出来的。。。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-3 02:36:53 | 显示全部楼层
这样没法猜出原词吧。。。因为不同的猜ABC和猜BAC结果完全一样,程序如何能知道是哪一个呢?逻辑上讲不通,或者我理解错了
回复 支持 反对

使用道具 举报

 楼主| 湿太大苞谷 发表于 2016-3-3 02:56:54 | 显示全部楼层
googlerr 发表于 2016-3-3 02:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这样没法猜出原词吧。。。因为不同的猜ABC和猜BAC结果完全一样,程序如何能知道是哪一个呢?逻辑上讲不通, ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果猜到了原词会给你100分。。。所以就是要不停的去试。。。
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-3 03:46:48 | 显示全部楼层
湿太大苞谷 发表于 2016-3-3 02:56
如果猜到了原词会给你100分。。。所以就是要不停的去试。。。

是不是先要猜出所有可能的字母, 在就所有的排列挨个猜?
回复 支持 反对

使用道具 举报

 楼主| 湿太大苞谷 发表于 2016-3-3 04:22:15 | 显示全部楼层
kinggarden2001 发表于 2016-3-3 03:46
是不是先要猜出所有可能的字母, 在就所有的排列挨个猜?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我就是这样做的。。。。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-3 05:01:48 | 显示全部楼层
湿太大苞谷 发表于 2016-3-3 02:56
如果猜到了原词会给你100分。。。所以就是要不停的去试。。。

OK 这样就讲得通了。感觉只能try所有的combination,因为正确100分 所有不正确都是一样的分
回复 支持 反对

使用道具 举报

cascade15 发表于 2016-3-3 06:36:14 | 显示全部楼层
googlerr 发表于 2016-3-3 05:01. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
OK 这样就讲得通了。感觉只能try所有的combination,因为正确100分 所有不正确都是一样的分
. 1point 3acres 璁哄潧
不正确分也不同吧,所以还是有点hint,问题是有一个词是几个字母么?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-3 06:43:44 | 显示全部楼层
cascade15 发表于 2016-3-3 06:36
不正确分也不同吧,所以还是有点hint,问题是有一个词是几个字母么?

按照楼主这里说的“每一次猜一个词会去判断里面有几个字母是符合的,符合的话就有一分,每次会告诉你猜的这个单词得多少分,但是不告诉你哪些字母是对的,也不告诉你顺序”,比如正确答案是ABC,那么猜ABC是100分,猜BAC,BCA等顺序不对的应该都是3分吧。
回复 支持 反对

使用道具 举报

cascade15 发表于 2016-3-3 07:00:10 | 显示全部楼层
googlerr 发表于 2016-3-3 06:43
按照楼主这里说的“每一次猜一个词会去判断里面有几个字母是符合的,符合的话就有一分,每次会告诉你猜的 ...

对,如果已经到abc了那可以用permutation来做,可是如果正确答案是abcd 或者abcc这是基本猜不到的啊。
有一种是这个必须是valid word,那么字必须在字典里,如果字母对了那就没有那么多组合了,但是in any case,如果不告诉字符长度我觉得没法做啊
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-3 07:54:58 | 显示全部楼层
cascade15 发表于 2016-3-3 07:00
对,如果已经到abc了那可以用permutation来做,可是如果正确答案是abcd 或者abcc这是基本猜不到的啊。
...

嗯。不过不太明白为什么正确答案是abcd和abcc就猜不到呢?尤其是abcd?abcc这种有重复的情况,如果没有事先告诉单词长度或者像你说的给一个dictionary的话,确实是很崩溃。我能想到的只是一个brute force的方法:首先定位到三个字母a,b,c。如果试了所有的abc的permutation都不对,那么就说明有重复的字母,然后试长度为4的情况(即有一个字母重复,并尝试所有的重复情况),然后试长为5。。。。
回复 支持 反对

使用道具 举报

 楼主| 湿太大苞谷 发表于 2016-3-3 07:55:52 | 显示全部楼层
cascade15 发表于 2016-3-3 07:00
对,如果已经到abc了那可以用permutation来做,可是如果正确答案是abcd 或者abcc这是基本猜不到的啊。
...

有长度,说5个字符,但是单词里有重复的字母,所以我最后把possible character缩小到5个也是不能用permutation的,因为还是要考虑重复
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 13:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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