刚面玩linkedIn求人品

pandakuo 发表于 2014-10-16 04:46
因為我是寫這樣 所以他問我的時候 我就想說應該不太做事情 可是他又一直問 我就說只好說寫如果是要write ...

对因为你没有用lazy initialization...所以就什么也不用做

lunaughty 发表于 2014-10-16 04:11
这个感觉可以用一个链表和一个堆，链表当作栈使用，插入删除的时候同时操作那个堆就行了。

好主意，但是其实和两个堆复杂是一样的(只是少了一个堆变成1/2)

billupus 发表于 2014-10-18 04:14
好主意，但是其实和两个堆复杂是一样的(只是少了一个堆变成1/2)

nod~祝LZ早日offer哈

billupus 发表于 2014-10-15 12:10
popMax是pop出最接近栈顶的max值，其他值都不变。当然可以就一直pop到这个max值再push回去，我一开始也是 ...

什么叫最接近栈顶的max值？这跟整个栈的最大值有什么区别？如果没区别，那就维护一个最大堆不就可以了。。？

举个例子有这么个栈:
| 1 2 3 4 5 3 3 3 4
那么最接近栈顶的max值是5。popMax完以后是
| 1 2 3 4 3 3 3 4
其实是没区别的。最naive的做法就是直接pop到5， 然后再把之前的都push回去。但是这个办法最差是O(n)，他问有没有办法优化

问下楼主这个栈要不要求实现普通的LIFO的pop呢。。要是要求的话感觉时间复杂度就是O(n)了。
用heap的话每次pop后都要到heap里找到pop掉的元素然后删除。。

补充内容 (2014-10-20 05:24):
binary heap search要O(n) delete要O(logn)

您好！
本帖隐藏的内容需要积分高于 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

traceroute_su 发表于 2014-10-22 05:01
follow up 一般还会问这样会有什么问题，然后改成double checking lock就问题不是很大了。

会的。其他人也碰到过不止一次了

billupus 发表于 2014-10-18 04:56
举个例子有这么个栈:
| 1 2 3 4 5 3 3 3 4
那么最接近栈顶的max值是5。popMax完以后是

楼主抱歉问一个 如果这样做的话 那个目前的MAX是不是也要重新算了呀？