软软 哦提爱思

MS HR 在linkedin上联系的我，本以为要元旦之后才能收到ots，没想到第二天就收到ots。担心event名额有限就赶紧准备了两天把ots做了。
好久没有刷题，准备的不充分啊。

60分钟三道题，

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

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

求 昂赛啊！！

potplus 发表于 2018-12-27 16:39
请问第二题sort以外还有什么更好的办法？

补充内容 (2018-12-27 16:40):

Two pointers can solve the problem in O(n) if the input is sorted. Here is the idea:
if A[i] + A[j] > target where i < j, we can say A[k] + A[j] > target where i <= k < j. Decrease j by 1.
If A[i] + A[j] <= target, increase i by 1.

All elements will be only touched once.

jackli31742 发表于 2019-1-21 01:19
这第一题怎么个分类法…第三题感觉像是博弈，之前见过类似的，但没啥思路，暴力破解？

BFS啊 给出了同类的pair  第三题题上必须说两个对手都足够聪明才行。
微软ots 是随机出来的题 后面的题库挺大的

第二题是排序过的

第二题是排序过的

请问楼主这是哪天event的欧体爱思呀~

祝楼主好运，昂塞特在路上了

请问第二题sort以外还有什么更好的办法？

补充内容 (2018-12-27 16:40):
nvm 理解错了 input是sort过的

补充内容 (2018-12-27 16:42):
是不是从每个开始binary search, nlogn?

Guasisi 发表于 2018-12-27 12:17
请问楼主这是哪天event的欧体爱思呀~

1 25 啊啊啊啊啊啊啊

dizhufengzhi 发表于 2018-12-27 13:42
祝楼主好运，昂塞特在路上了

谢谢！！ 同祝好运1~~

potplus 发表于 2018-12-27 16:39
请问第二题sort以外还有什么更好的办法？

补充内容 (2018-12-27 16:40):

应该是 我当时时间紧 就搞了个n方。。。