Linkedin电面+onsite

plp2016 发表于 2016-11-21 12:38
这道题最后没有说完
我是用一个priorityqueue记录最大值 我觉得他的意思应该是光popmax的那个操作要O(1) ...

应该是需要一个DoublyLinkedList + TreeSet，pq的话删除还是O(N)...这个需要实现normal的pop()么？

补充内容 (2016-11-22 00:04):
Sorry,漏看了你的描述。。看来需要实现Pop，那就是DoublyLinkedList + TreeSet?

plp2016 发表于 2016-11-21 12:38
这道题最后没有说完
我是用一个priorityqueue记录最大值 我觉得他的意思应该是光popmax的那个操作要O(1) ...

以及切pizza那个什么套路啊。。脑筋急转弯么？ 是一块块叠起来切？ n刀最多2^n块？

求问楼主 你用的是哪个pattern设计的呢 MVC么 还有class都有什么 你参考的哪个 求给个链接啊 设计class是只列出都有什么class就行  还是哪些方法放在哪些class里都要列出来 用画UML图么 网上各种版本都有啊。。。

小A要当码农 发表于 2016-11-22 00:03
应该是需要一个DoublyLinkedList + TreeSet，pq的话删除还是O(N)...这个需要实现normal的pop()么？

补充 ...

恩 我觉得doublylinkedlist肯定要的 需要实现normal的pop

小A要当码农 发表于 2016-11-22 00:08
以及切pizza那个什么套路啊。。脑筋急转弯么？ 是一块块叠起来切？ n刀最多2^n块？

不用叠起来 最后给他给表达式就行
2刀是4 3刀是7块 4刀是11块 我一开始用dp做的 他说让我直接给个表达式 就照着dp公式又推了个n的表达式

spiritrhy 发表于 2016-11-22 05:14
求问楼主 你用的是哪个pattern设计的呢 MVC么 还有class都有什么 你参考的哪个 求给个链接啊 设计class是只 ...

我没用mvc和pattern 感觉这好像不是他们要问的的重点 class大概就是列出都有什么变量和method就行 很简单 之后面试官会问一些比较基础的系统设计的东西 都不难 不用担心

plp2016 发表于 2016-11-21 12:38
这道题最后没有说完
我是用一个priorityqueue记录最大值 我觉得他的意思应该是光popmax的那个操作要O(1) ...

如果要popMax O(1) 的话 应该在push的时候动一些手脚 可以用linkedlist来实现stack  并维护一个sorted array 这样popMax就可以实现O(1) priority_queue 如果pop的话 感觉不是O(1)

popmax 那题用两个stack不就可以了吗，一个记录正常数值，一个记录到目前的max值，然后要那个就pop那个。  就非常非常简单啊 为什么会做不出来。还是我有什么地方理解不对吗

补充内容 (2016-11-26 12:35):
对不起是我理解错了。现在理解了

plp2016 发表于 2016-11-25 02:28
不用叠起来 最后给他给表达式就行
2刀是4 3刀是7块 4刀是11块 我一开始用dp做的 他说让我直接给个表达式 ...

求DP递推公式。。想不出来。。 以及popMax的那个题， 楼主你的意思是， pq不能用？