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

发一下google pittsburgh onsite 的面经，先帮同学发一个他的，然后下面是我自己的。

这个是我同学的，他的具体思路我就不知道了，所以要讨论的话楼主本身就不太清楚了，要是后面楼主本身的题可以讨论。

第一轮：就是给你一个string 比如“11121315”这样的，里面有连续数字，只有一个漏了，找出漏掉的数字。
第二轮：server 问题，给每个用户一个每秒访问限制，写个方法，超过限制返回false，不超过返回true，空间复杂度要求(o1)。
第三轮：先是一道代码题 partition，等于target放后面 ，不等于的放前面。然后follow一个算法题不用写代码，就是leetcode shorted distance from buildings那道。
第四轮：给一个商品名字ABC （ABC是三个单词，然后一个商品描述XYZABC... 就是判断 描述是否

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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

楼主可否详细说说第三题，stream里面每一个元素包含一个时间和一个value吗？
可否举个例子？

cascade15 发表于 2016-3-3 07:00
对，如果已经到abc了那可以用permutation来做，可是如果正确答案是abcd 或者abcc这是基本猜不到的啊。
...

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

googlerr 发表于 2016-3-3 06:43
按照楼主这里说的“每一次猜一个词会去判断里面有几个字母是符合的，符合的话就有一分，每次会告诉你猜的 ...

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

楼主如果进了，明年求内推！

第四轮那个题在以前的面筋里见到过 不知道谁有比较好的solution

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

2.2要用dp+sg函数做，博弈题的标准套路。 第一轮我觉得应该是图的dfs+剪枝这样。。。

感觉楼主好倒霉 碰到的题目比同学的难那么多

楼主总结的好详细，十分感谢！

猜单词不太明白。比如假如已经推测出来是3个字母ABC，我们如何知道到底是ABC还是BAC或其它排列呢？按照题目意思，猜ABC或者BAC都是得3分吧？是不是应该评分还有一条：位置也对得更多的分？

kidzlike 发表于 2016-3-2 13:47
2.2要用dp+sg函数做，博弈题的标准套路。 第一轮我觉得应该是图的dfs+剪枝这样。。。

第一题不知道要怎么dfs，因为不知道顺序。。。

wtcupup 发表于 2016-3-2 14:43
感觉楼主好倒霉 碰到的题目比同学的难那么多

对啊，虐哭。。。

googlerr 发表于 2016-3-2 16:11
猜单词不太明白。比如假如已经推测出来是3个字母ABC，我们如何知道到底是ABC还是BAC或其它排列呢？按照题目 ...

对，就是只看字母是不是符合，不看顺序，完全不知道顺序，ABC和BAC都是3分，所以才觉得很难。。。最后是要把原词猜出来的。。。