[求大米]新鲜亚麻OA

两道题，感觉这次的比较简单。

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

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

woridage1 发表于 2019-7-6 21:21
大概看了一下第二个，求教一下，是不是存俩map，遍历第一个，用upper_bound搜第二个，然后进行组合，存diff ...

在第二个map里从upper bound搜到0么  那样岂不是
N^2的复杂度
还是说我没有理解。。。。

方便大家在坛子里搜索，加上一些注释：
第一题是Amazon Music pair songs 选合适的音乐 (two sum)
第二题是Amazon foreground background pair 前后台进程 (Two Sum Closest)

xbw 发表于 2019-7-13 10:24
在第二个map里从upper bound搜到0么  那样岂不是
N^2的复杂度
还是说我没有理解。。。。

upper_bound 的复杂度应该是logn，不是n

谢谢分享！

请问楼主OA了多久收到面试通知？ 谢谢

小元宝 发表于 2019-7-3 03:18
请问楼主OA了多久收到面试通知？ 谢谢

OA之后一天收到面试通知。

大概看了一下第二个，求教一下，是不是存俩map，遍历第一个，用upper_bound搜第二个，然后进行组合，存diff值，diff值变小的话跟新结果数组

如果有多个optimal pair 的话要全部return吗

谢谢楼主分享