10/14 Google onsite 面经

onsite 4轮， 在google总部mountain view 面的
一轮：
tourament question:  input is players like（A,B,C,D）, print total rounds[[(A, B), (C, D)], [(A, C), (B, D)], [(A, D), (B, C)]]
recursion 做的
二轮：
tic－tac

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

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

值和最小值的差值最大，返回这个值。用heap或priority queue做dp。

求积分～～～～

kuyen 发表于 2014-10-22 01:22
可以说的再具体点吗？我在想这个方法可以处理重复数字吗？

http://leetcode.com/2011/01/sliding-window-maximum.html
重复是可以的吧。。感觉这个问题就是sliding window max的变型，不过是用两个分别记录最大最小。

kuyen 发表于 2014-10-21 12:50
我觉得楼主的方法可能已经是最好的了。你用deque的话，如果pop掉当前范围唯一的最小数的话，你怎么确定下 ...

我想的用是两个deque，一个存最大，一个存最小，每次求diff然后和max比较，应该是O(N)吧？

还来得及吗 发表于 2014-10-21 23:38
我想的用是两个deque，一个存最大，一个存最小，每次求diff然后和max比较，应该是O(N)吧？

赞，这确实是O(N)的方法
维护2个单调队列，每次尝试更新头尾，取出两个队列的头，相减后与max比较即可。

感谢分享，bless

Bless, 有结果了吗

ffcc 发表于 2014-10-18 00:53
感谢分享，bless

亲，14号面的～当然没有啦

嘿嘿 lz 我都感觉遇到的面试官都是一个 额 目测lz offer快得手了 强大bless！

lz面的是new grad吗？谢谢分享

楼主四轮那个k是什么意思？

bless, hi, 谢谢！四轮第一个：这个rectangular不一定是要“垂直摆放”的是吗，可能是斜的喽，请问下BFS的起点是哪儿？ 四轮第二个：k是个滑动的窗口长度是吗，能给下dp的公式吗，谢谢？

同求四轮第二题的解法~~~!!!