Google Pittsburgh Onsite 面经

今天去Google Pittsburgh Onsite，貌似CMU的学生都是直接拿Pittsburgh的Onsite不用电面。一进门先看到两个同班同学，都是来onsite的，真是醉了。
一共四轮，每轮45分钟，中午吃饭。过程很简单，每一轮都是随便聊聊天然后直接上白板写题。所有的面试官都是白人，交流非常通畅。
第一轮 three sum的变种，给一个array，找出所有 three tuple 组合的数量， 使得三个数加起来小于等于某个target。我用了two pointer. n^2复杂度做完。由于我们并不用返回所有的tuple，只要数量，所以又用了binary Search优化。

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

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

的区间，再看如何把区间映射到一个值。我用了hashMap+array才把时间降到O(n),然后又用了Binary Search优化。一天写两个Binary Search，写得晕晕乎乎。。。。不知道对不对。


总之感觉Google Pittsburgh还是挺简单的。除了算法题也不问其他问题了。祝找工的小伙伴们Good Luck！

第一轮的这个triplets，用二分是O(n*n*logn)，不用二分是O(n^3)。因为要枚举第一个数和第二个数，这已经是O(n^2)了，最后一个数用二分logn就能找到。这跟leetcode上的3sum不同，因为第二个数的位置中第一个确定的情况下也是可以有多个值的。

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

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

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

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

请问LZ第一轮的three sum为什么返回数量就可以用binary search优化？

谢楼主分享，请问楼主第一题的3sum怎么用binary search优化？是可以assume这个array里不含重复的数字么？

楼主， 最后权重那道能不能说下？ 祝您拿到big offer

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

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

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

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

好赞，祝楼主offer多多～

楼主，你们是招聘会去的么，还是？

swing 发表于 2015-9-5 23:05
楼主，你们是招聘会去的么，还是？

我是内推的。