Airbnb 新鲜follow up 面经

OA 还是 OA2 那道 Display Page 的题目。
遇到了国人面试官。 一开始就简单讲了自己的思路～ 后面开始问复杂度。  因为我是用python写的没有自带的 linkedlist QAQ 所以每次remove都在call  list 的remove （which is O(n)）， 所以worst case 应该有 O(n^3)..  (一开始还讲错成 O(n^2) 了)。
讲完之后开始问怎么优化 ，我说了以下两种
1.自己用python写一个linked li

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

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

可是自己还没理清楚思路面试官看时间差不多到了，就把他的思路跟我讲了一遍。  又问了我还有什么问题么 0-0  大概就这样结束了  

难过 sigh， 果然还是要默默提高码力和对代码的理解啊 0-0 Anyway 不管怎么样也算面过女神家了 ！

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

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

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

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

jinnyatw34 发表于 2017-11-3 07:55
每个host 有一个单独的sorted linkedlist。 每次往一个page里面加东西的时候，从每个host的linkedlist 里 ...

好的，谢谢楼主！bless

求问面试官的思路是啥啊？想不到python还能怎么优化

楼主面试的时候看得到自己的OA写的代码吗？

Hanslen 发表于 2017-11-3 08:02
楼主面试的时候看得到自己的OA写的代码吗？

可以的。 面试之前会给你一个coderpad 的link， 然后面试官会把代码paste过来～～

楼主这样用maxHeap的时间复杂度应该是在O(nlogk)吧？

Roy7wt 发表于 2017-11-3 11:59
楼主这样用maxHeap的时间复杂度应该是在O(nlogk)吧？

对的

用Linkedlist的话worst case time complexity也只是O(pageNumber * n) 而已吧？

已挂 0-0 祝大家好运