5.3 Amazon OA

今天把 Amazon 的 OA 做了，照惯例分享在地里。
整个 OA 共 3 个部分

• 第一部分是两个 technical questions 90 mins
• 第二
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  
  试，但实际上会有 10 - 30 个黑盒测试
• 刷题时记得把 time complexity 也捋清楚，第二题做 sort 不是一目了然的复杂度
  

想问问LZ大佬第二题时间复杂度怎么分析的

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

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

谢谢分享！

bearcat001 发表于 2020-5-4 11:20
我没来得及详细推倒，第二部分是15分钟，我的答案是

n: length of lines

我的分析是：merge sort比较次数是nlogn，每次比较需要O(m)，总共O(mnlogn)。我也不知道对不对

O(nlog(mn))吧
做n次排序但是每次排序需要logmn的时间

我感觉跟each content length m 没有关系，因为实际并没有sort content.只是用于比较而已。所以最后的还是NlogN, where N is number of log entries.