WePay code challenge

一面已经挂了。
问题是implement 一个queue, LILO. 要实现3个功能，add, pop, pollmax.前两个不用说，后一个是要求把 queue里面最大的数提出来。

第一次遇到implement这种技术面试，有点发蒙。后面跟进要求pollmax快些，O(logN),提示可以用BST 和 LinkedNode 双重数据结构，光想着单向的linked node了，提示后用双向链表，时间不够了，就挂了。

祝好运

rpliu 发表于 2018-2-24 01:03
一面已经挂了。
问题是implement 一个queue, LILO. 要实现3个功能，add, pop, pollmax.前两个不用说，后一 ...

看起來跟Leetcode的MinStack有異曲同工之妙
每個ListNode加上一個currentMax應該就行了
每次add/pop更新index
這樣三個method的time complexity就都是O(1)
不管space complexity因為不管如何都是O(n)

不知道是不是如此

补充内容 (2018-2-24 02:53):
不過如果是要把整個max node從list內提出、刪除
我就會另外存一個sorted array
用binary search存節點reference
所以add/pop approach會變成O(log n)
但pollMax還是constant
每次pollMax就把該node的pre及next連起

补充内容 (2018-2-24 02:54):
然後更新array

OA 倒数第二个 test case居然没过，调了好久不知道什么原因。楼主你还记不记得有什么别的坑？

tumaolin94 发表于 2018-2-28 14:59
OA 倒数第二个 test case居然没过，调了好久不知道什么原因。楼主你还记不记得有什么别的坑？

我印象深刻的就是那两个了， 没有发现你的问题。没看到你的code，不了解情况。也许你的问题在于boundary 情况。
后面几个testcase是隐藏的。

tumaolin94 发表于 2018-2-28 14:59
OA 倒数第二个 test case居然没过，调了好久不知道什么原因。楼主你还记不记得有什么别的坑？

same.......do you know why?

T 发表于 2018-3-1 02:47
same.......do you know why?

我寫得時候全過
有用long嗎，估計int不夠
但我真的忘記我當時有處理哪些細節

请问code challenge是75分钟的还是90分钟的?

bisadog 发表于 2018-3-1 02:52
我寫得時候全過
有用long嗎，估計int不夠
但我真的忘記我當時有處理哪些細節

应该不是，后来基本上把所有能扩大的基本类型都扩大了

tumaolin94 发表于 2018-3-1 05:59
应该不是，后来基本上把所有能扩大的基本类型都扩大了

我也是倒数第二个没过，真的捣鼓了半小时都没看出来 =_=

rpliu 发表于 2018-2-12 14:25
差不多，我是先算出平均数的数组，假设原始数组size是M，窗口size是K，那么平均数数组size是M-K+1,把平均数 ...

请问下楼主，怎么确定每个数在几个window中出现呢？感觉要根据window size 和 nums.length 分类讨论?