l***e
发帖数: 108 | 1 假设有一个stream of numbers （譬如stock prices)。 在每个时刻，需要你能给出
the minimum number among the last k numbers. 有什么比较好的办法吗？
我给出的答案是用一个heap (priority queue)。但是面试官说这答案虽然可以接受，
但是有更好的。 |
j*****8
发帖数: 3635 | 2 Sliding window
[在 lurie (lurie) 的大作中提到：]
：假设有一个stream of numbers （譬如stock prices)。 在每个时刻，需要你能给出
：the minimum number among the last k numbers. 有什么比较好的办法吗？
：........... |
y*******i
发帖数: 361 | 3 is it sorted list?
【在 l***e 的大作中提到】
: 假设有一个stream of numbers （譬如stock prices)。 在每个时刻，需要你能给出
: the minimum number among the last k numbers. 有什么比较好的办法吗？
: 我给出的答案是用一个heap (priority queue)。但是面试官说这答案虽然可以接受，
: 但是有更好的。
|
l***e
发帖数: 108 | 4 surely not...
具体情形就比如现实的stock prices，你知道所有的历史价格，要求过去几小时（或者
几天）的最低价格。
【在 y*******i 的大作中提到】
: is it sorted list?
|
l***e
发帖数: 108 | 5 多谢。Now I get it
【在 j*****8 的大作中提到】
: Sliding window
: [在 lurie (lurie) 的大作中提到：]
: ：假设有一个stream of numbers （譬如stock prices)。 在每个时刻，需要你能给出
: ：the minimum number among the last k numbers. 有什么比较好的办法吗？
: ：...........
|
g*******d
发帖数: 495 | |
l***e
发帖数: 108 | 7 不是，是投行quant。根本没想到会问算法，我从来没准备过。。。 我就只能想出heap
的算法。幸好他也没指望我能想出最优解法
【在 g*******d 的大作中提到】
: bloomberg?
|
S********t
发帖数: 3431 | 8 deque 存non decreasing sequence
【在 l***e 的大作中提到】
: 假设有一个stream of numbers （譬如stock prices)。 在每个时刻，需要你能给出
: the minimum number among the last k numbers. 有什么比较好的办法吗？
: 我给出的答案是用一个heap (priority queue)。但是面试官说这答案虽然可以接受，
: 但是有更好的。
|
f*******r
发帖数: 976 | 9 您说的是non－increasing deque吧
【在 S********t 的大作中提到】
: deque 存non decreasing sequence
|
S********t
发帖数: 3431 | 10 no, I meant what I said
【在 f*******r 的大作中提到】
: 您说的是non－increasing deque吧
|
|
|
f*******r
发帖数: 976 | |
w*x
发帖数: 3456 | 12 应该是decreasing，我敢觉思路和min stack有点像
【在 f*******r 的大作中提到】
: 您说的是non－increasing deque吧
|
S********t
发帖数: 3431 | 13 从进queue的顺序上看，queue里的元素是非递减的。
按照stackoverflow上的答案，里面假想元素是从左边入queue从右边出，所以从左
到右的顺序是非递增。
不过我鼓励尽量独立想问题，少看答案，实在想看，最好是看提示。
【在 f*******r 的大作中提到】
: 具体算法在：http://stackoverflow.com/questions/29969345/find-the-lowest-number-from-last-k-elements-in-an-infinite-set-of-numbers
|
k****r
发帖数: 807 | |
f*******r
发帖数: 976 | 15 这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
均时间少，最坏时间比较差。
heap保证最坏时间都只是lg k。
【在 S********t 的大作中提到】
: 从进queue的顺序上看，queue里的元素是非递减的。
: 按照stackoverflow上的答案，里面假想元素是从左边入queue从右边出，所以从左
: 到右的顺序是非递增。
: 不过我鼓励尽量独立想问题，少看答案，实在想看，最好是看提示。
|
x*****z
发帖数: 15 | 16
这个是平均O(1)的，因为每个元素最多add一次remove一次。用heap的话不止O(logn),
因为按顺序remove的时候需要O(n)。
【在 f*******r 的大作中提到】
: 这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
: 均时间少，最坏时间比较差。
: heap保证最坏时间都只是lg k。
|
s**x
发帖数: 7506 | 17
Quick sort worst case O(n^2) heap sort worst nlogn.
但实际上sort 都是用Quicksort 做的。
【在 f*******r 的大作中提到】
: 这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
: 均时间少，最坏时间比较差。
: heap保证最坏时间都只是lg k。
|
m***y
发帖数: 14763 | 18 这主要是硬件原因。Qsort的内循环很容易在硬件上实现，软硬的速度之差就是天壤之
别了。
就事论事，这道题，老汉能找到的标准答案都是deque，不是说它明显比用别的数据结
构好很多，而是deque在很多平台上要不有专门硬件实现，你可以调asm或者native
function,要不有专门的优化过的库。
就stackoverflow的那个链结，下面有人讨论如何用banker's queue,就是用两个stack
来模拟deque。看起来绕圈子，但是在只提供stack的硬件上，这样还是比咱自己写的软
件deque快的多。
【在 s**x 的大作中提到】
:
: Quick sort worst case O(n^2) heap sort worst nlogn.
: 但实际上sort 都是用Quicksort 做的。
|
s**x
发帖数: 7506 | 19
stack
关键是 heap is not the right data structure for this. yeah, you can insert
in logN and find min in O(1), but it is tricky to remove one element out of
the window. you have to have some sort of index to the position in the
heap from the position in the sliding window. far worse than a queue, or
circular buffer, or even stack etc.
【在 m***y 的大作中提到】
: 这主要是硬件原因。Qsort的内循环很容易在硬件上实现，软硬的速度之差就是天壤之
: 别了。
: 就事论事，这道题，老汉能找到的标准答案都是deque，不是说它明显比用别的数据结
: 构好很多，而是deque在很多平台上要不有专门硬件实现，你可以调asm或者native
: function,要不有专门的优化过的库。
: 就stackoverflow的那个链结，下面有人讨论如何用banker's queue,就是用两个stack
: 来模拟deque。看起来绕圈子，但是在只提供stack的硬件上，这样还是比咱自己写的软
: 件deque快的多。
|
w*****1
发帖数: 6807 | 20 确实啊，这题可以叫min queue，基本是一个思想
【在 w*x 的大作中提到】
: 应该是decreasing，我敢觉思路和min stack有点像
|
