Fed May Buy $300 Billion in Treasuries After QE2 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

Fed May Buy $300 Billion in Treasuries After QE2

Fed May Buy $300 Billion in Treasuries After QE2# Living

B*12011-06-27 07:06

1 楼

Ask longtime ago on this board. But did not get a good answer.
http://www.careercup.com/question?id=9786128
Implement a stack that pops out the most frequently added item. Stack
supports 3 functions - push, pop,and top. Give complexity of each functions
in your implementation.

b*d2011-06-27 07:06

2 楼

http://finance.yahoo.com/news/Fed-May-Buy-300-Billion-in-bloomb
Fed看来还是要坚持买国债.

a*62011-06-27 07:06

3 楼

push and pop can be implemented as the insert and delete in a hash table
(or a BST) in O(1) (or O(logn)) time, with the frequency associated
Also maintain a two-level linked list of all the elements (grouping
elements with the same frequency together)... when the frequency of an
element +1 or -1 (push or pop), move this element to the next or the
previous group or create a new group, in O(1) time...

functions

【在 B*******1 的大作中提到】

: Ask longtime ago on this board. But did not get a good answer.
: http://www.careercup.com/question?id=9786128
: Implement a stack that pops out the most frequently added item. Stack
: supports 3 functions - push, pop,and top. Give complexity of each functions
: in your implementation.

z*u2011-06-27 07:06

4 楼

感觉和 LRU 很像，不过 LRU 是记录每个元素出现的先后，这个是元素出现的次数
用 hash + heap
hash 用来 O(1) access 对应的地址；按照出现次数来维护 heap。
每次 push 和 pop 的时候需要对他在 heap 中的 node 做up-heapify 或 down-
heapify，心元素的话就是 heap 的 insert，最坏情况都是 O(lgn)
top 是 O(1)

functions

【在 B*******1 的大作中提到】

s*n2011-06-27 07:06

5 楼

heapify的时候不光是这个node，其他node的index也变了，还得改hashtable，平均插
入一个node要log(n)次查询hashtable。

【在 z****u 的大作中提到】

: 感觉和 LRU 很像，不过 LRU 是记录每个元素出现的先后，这个是元素出现的次数
: 用 hash + heap
: hash 用来 O(1) access 对应的地址；按照出现次数来维护 heap。
: 每次 push 和 pop 的时候需要对他在 heap 中的 node 做up-heapify 或 down-
: heapify，心元素的话就是 heap 的 insert，最坏情况都是 O(lgn)
: top 是 O(1)
:
: functions

z*u2011-06-27 07:06

6 楼

不用 array 做 heap，用 double linked list 可行么？
heap 的结构更复杂了，不过不存在其它node更改index 和更改 hashtable 的问题

【在 s******n 的大作中提到】

: heapify的时候不光是这个node，其他node的index也变了，还得改hashtable，平均插
: 入一个node要log(n)次查询hashtable。