四月狗家跪经

三月中旬的时候，我请朋友内推了我。 第二天，我就收到了狗家 recuriter的email 说可以跳过 phone interview 直接 onsite 面试。收到email 的时候还是有点惊讶的，因为本来以为流程是没有走的那么快的。 面试后，过了两天 HR 给我打电话说 我没过， 因为收到的feedback 不稳定。


下面的题都是纯白板


第一题：


题目given 两个 integer， 分别是 period 和 threshold。Assume there is a endless streaming events, each event occurs at timestamp "x".  The question want you to write an API that return true if number of the events are over the threshold within the period around timestamp "x" .   


Ex:
period = 3, threshold =2
getEvent(

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

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

align="left">Input: [1,1,1], target = 2

[-1,1,1]

[1,-1,1]

[1,1,-1]

return (3)

第一次发帖，求大米。 如果有解释不清楚的地方请大家见谅。 最后自己总结一下感受把，面试基本一上来就是丢你一脸题目，我觉得先跟面试官沟通清楚题意和 assumption，会非常有帮助。另外google 面试确实非常考验基本功，我觉得我的题比起地里其他面试确实不算是难， 所以这次也是自己没有准备好的原因。希望明年再战的时候可以更加扎实把。

最后希望接下来面试的同学，offer 多多，顺顺利利

补充内容 (2018-4-9 07:13):
第五题， target 应该是 1

补充内容 (2018-4-10 01:04):
第四题， 是两两对比小于range 就可以output

请问楼主，第一题第二问详细解题思路是啥？我也感觉不能村所有的数据，但是如果不存所有，那就没法查任意时间点，
关于第二题，是leetcode的原题，这道题超级难！leetcode 327

xietianyi 发表于 2018-4-9 10:37
求问楼主第五题有什么思路？ 我想到的是brute force，DFS扫一遍，到末尾等于target就count++，时间2^n;有其 ...

第五题是backpack变形。

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

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

第二题：
贴个链接，里面有mergesort的思路和treeset思路（楼主应该是c++，这个就算了）
http://www.zrzahid.com/contiguous-subarray-with-sum-in-a-range/

bs854 发表于 2018-4-9 07:10
第五题变成-1后加起来和不是1么。。

不好意思， 例子给错了。应该是 target 是 1

水浅王八多 发表于 2018-4-9 07:02
第二题：
贴个链接，里面有mergesort的思路和treeset思路（楼主应该是c++，这个就算了）
http://www.zrza ...

感谢提供连接

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

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

楼主求第四题思路
我只想到了brute force的思路。每次来了一个坐标，就和其他的点算距离，如果距离小于2，就存起来，如果正好有3个，那就变成一组candidate，看这三个是否相互之间都是距离为2。
有没有更高效的？

祝楼主offer多多。谢谢

第一题不太理解题意，楼主能说一下为什么那些example分别是false and true么？

frankhong10585 发表于 2018-4-9 07:50
我之前也没有练习过这种题， 希望大神们可以给些更好的解法思路

第一题，第一问我用 一个queue 然后 s ...

这个第四题是算三个之间总的距离小于3么？还是要求每两个之间都小于1？结果会不一样啊。