狗家onsite面经

没有店面，只有OS
1.  有一个数组，分成K部分，要求， min of subarray sum is maximized,   [1,2,4,3,3]  分成3部分，  你可以分成   1| 2,4|3,3  最小数组 是1,  但是你分成 1,2 |4|3,3 最小的数组sum就变成了3.  3是想要的答案。 这个我提出了DP和recursive, 面试官都不满意, 最后用的是二分查找.    比如说你给 一个数 N ,

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

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

数据结构 刷题网上有

5. 设计骨骼量级的  type ahead 和suggestion.






补充内容 (2019-2-2 05:53):
面试时间：2019/1/31
总体体验不错.

面试时间：2019/1/31
总体体验不错.

楼主麻烦能把第三题详细说一下吗？不太明白，input是什么形式的， 每个function signature又是怎样的呢？多谢！

lz，第一题是离扣四要领吗？

面试官要求真多啊，第一题DP就很好理解 还非得要binary search  不过binary search找答案的这些题已经成一个系列了= =...
O(1) random() 是自己设计一个产生random的函数？

mooc 发表于 2019-2-2 07:51
lz，第一题是离扣四要领吗？

是的~~~~~~~~~~~~~·

lz能不能再解释一下第一题二分搜索是怎么做的不那个N是指的什么？

mooc 发表于 2019-2-2 07:51
lz，第一题是离扣四要领吗？

是的, 机智

cheerier 发表于 2019-2-3 01:02
lz能不能再解释一下第一题二分搜索是怎么做的不那个N是指的什么？

LeetCode 看一下正确答案？  2分就是你看这个数组能不能被分成K个subarray,  每个大于M. （for loop一遍就知道了.）   如果不能, 你就把M 换成M/2, 如果可以你就把M换成2M.   然后不停的2分, 找到这个Integer

nesenese 发表于 2019-2-2 07:46
楼主麻烦能把第三题详细说一下吗？不太明白，input是什么形式的， 每个function signature又是怎样的呢？多 ...

就是你要设计两个api
start(String requestId)
end(String requestId)

给出一个api你可以直接call
emit()  // 当一个event完成的时候你可以call emit() 提交log.

log提交的顺序是  event 开始时间的顺序.
比如有:a->(3,7)  b->(4,6)
你的log里面 存的顺序应该是a->b

打个比方: 现在有一个event (3,4)  id 是a  start at 3, end at 4
在time 3的时候你需要call  start(a) 在time 4的时候你要call end(a){emit()}

这样在4完成的时候你就emit 这个event log.

但是如果有两个events:  a -> (3,8) b ->(4,7)
你要做的事情是 a开始的时候start(3), b开始的时候start(b)
然后时间来到7,  这个时候你要call end(a) 【但是这时候你不能emit log, 因为a还没结束, 你要等a结束先emit(),这样才能保证log的顺序】






补充内容 (2019-2-7 02:22):
但是如果有两个events:  a -> (3,8) b ->(4,7)
打错字。。你要做的事情是 a开始的时候start(a), b开始的时候start(b)
然后时间来到7,  这个时候你要call end(b) 【但是这时候你不能emit log, 因为a还没结....