Google Intern 电面 1.10 惨跪面经

刚刚结束两轮背靠背的google 电面，体验一轮天堂一轮地狱。
第一轮是一个国人小哥，题目是给一个int array, 和int target。 array里每个int 表示该idx的box里有这么多pens，如果一个subarray的pens总和正好等于target，那么这个subarray是valid，要找到两个不重叠的valid subarray，使二者长度之和最小。
比如
[1, 2, 2, 1, 1, 1] target = 3

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

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

着头皮写，谨记前辈教诲，一边写一边嘀咕思路，但得到的都是打字声和嗯哼...最后再怀疑自我中dfs也没写完，问了下怎么优化也没答上来，就结束了。

总结下虽然面试体验差很多，但是归根到底还是自己太菜了，第一轮虽然过程很开心但是没有提示的话还是写不出最优解，第二轮可能才是适合我姿势水平的面试反馈。前两天亚麻也没收到waitlist，目测已跪，看来是和大厂无缘了。

您好！
本帖隐藏的内容需要积分高于 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

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

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

请问第二题能不能说具体些呢,给个例子是最好啦？ 第一题两轮dp复杂度是多少呢，虽说比前面快很多，但真要写复杂度感觉还是O(n^2)?

第2题就是原题三菱二啊  楼主面完就知道结果了？

第一题input保证了是非负数？所以才能用sliding window？

IHsin94 发表于 2020-1-11 14:37
第一题input保证了是非负数？所以才能用sliding window？

对的，题目中有说input表示的是pens的数量，所以一定非负

Unous 发表于 2020-1-11 10:46
请问第二题能不能说具体些呢,给个例子是最好啦？ 第一题两轮dp复杂度是多少呢，虽说比前面快很多，但真要写 ...

例子面试官当时也没给...所以才会花很久时间确认题目。不过大体上就是楼下的那题，只不过把输出改成了阴影边界。

apple2 发表于 2020-1-11 12:30
第2题就是原题三菱二啊  楼主面完就知道结果了？

感谢，确实和这题差不多。看来思路没有大问题，最优解打死我现场也想不出，没啥遗憾了哈哈。  结果还没出，不过google不是那种水到题没做完都能给过的公司吧

umusa2012 发表于 2020-1-17 01:21
这个的时间复杂度依然是O(n^2), 因为 sliding window 的长度取决于 target number.

O(n)吧，sliding window的right和left都只往右移，不会有某个元素被right/left访问两遍的