Linkedin 被双打的tech二面

angerhang 发表于 2016-12-14 16:19
LoloL
现在我在独守空城

你的HR起码还回你邮件，我中途换了HR之后就再没有人和我联系过了。

这个max heap感觉上镜率很高啊。但是不是很明白什么是pop max logn 时间。能讲讲么。

hakusama1024 发表于 2017-5-30 08:17
这个max heap感觉上镜率很高啊。但是不是很明白什么是pop max logn 时间。能讲讲么。

感觉如果用的double linked list操作POP 是O（1），但因为要同时删除掉Heap里面的Max ，这个操作是logn的／ Heap里存的应该<Integer, ListNode>这种pair的格式吧

Caroline123 发表于 2017-5-30 13:20
感觉如果用的double linked list操作POP 是O（1），但因为要同时删除掉Heap里面的Max ，这个操作是logn的 ...

从dll pop出来最后一个当作是stack pop。 但是返回来要在heap里面删掉这个node就得一个一个找了吧。heap里面又没有序列。

hakusama1024 发表于 2017-6-4 10:58
从dll pop出来最后一个当作是stack pop。 但是返回来要在heap里面删掉这个node就得一个一个找了吧。heap ...

Heap 里面每次POP出去一个元素，内部都要调整结构，重新给一个堆顶元素的，这个就是logn的时间

Caroline123 发表于 2017-6-5 07:54
Heap 里面每次POP出去一个元素，内部都要调整结构，重新给一个堆顶元素的，这个就是logn的时间

不是这个意思：P。这个题不是说还要保持stack基本的方法么。如果你stack现在顶（或者说dll尾）的元素并不是heap max的那个。你从dll里面pop出来用O（1）， 但是这个元素在heap是未知的啊。那不得一个一个去找么。

hakusama1024 发表于 2017-6-5 09:54
不是这个意思：P。这个题不是说还要保持stack基本的方法么。如果你stack现在顶（或者说dll尾）的元素并不 ...

heap 存的就是当前这个stack size时的最大值。 然后你在heap拿到最大值（值，和在DDL里的地址），去DDL里删除。 你查找顺序是不是搞反了

补充内容 (2017-6-6 03:12):
我觉得max stack不是说栈顶就是最大值，而是说能logn拿出这个栈里的最大值

Caroline123 发表于 2017-6-6 03:08
heap 存的就是当前这个stack size时的最大值。 然后你在heap拿到最大值（值，和在DDL里的地址），去DDL里 ...

等等。。咱们从新开始。。
deisng a max stack that supports all regular stack operations
这个意思是不是你设计的结构要首先support regular的push pop。
你用一个dll来表达stack这个我没问题。push就append到dll尾。pop也从尾。
然后用heap来快速查找max对吧。比如你pop max时候先从heap里拿出来max然后到dll里删除这个node。
然后你的heap需要heapify一下所以log的popmax是没错的。
但是要支持regular的stack pop。你从dll尾巴pop出来的值不得需要从heap也删除么。
但是heap里面是无规律的啊。你不是得n时间走一遍然后删除么。。
以上。。

hakusama1024 发表于 2017-6-6 04:25
等等。。咱们从新开始。。
deisng a max stack that supports all regular stack operations
这个意思 ...

哦 我懂你的意思了 我在想用类似 sliding window Max的lazy deletion方法，讲Max值和当时stack的size存在一一起，如果POP出去的值小于heap Max就不用管，如果大于， 就一直heap POP直到size和当前stack size 符合，但这个操作是nlogn的时间。

这个题要求regular stack operation也是O(lgn) time么？ 如果是的话可以用doubly linkedlist加TreeMap来做

Caroline123 发表于 2017-6-6 09:07
哦 我懂你的意思了 我在想用类似 sliding window Max的lazy deletion方法，讲Max值和当时stack的size存在 ...

不懂了。。只能求大神指点。