面试题：GetNumber and ReleaseNumber - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试题：GetNumber and ReleaseNumber

面试题：GetNumber and ReleaseNumber# JobHunting - 待字闺中

c*e2011-09-27 07:09

1 楼

The best data structure in terms of big O?
At the begging, the system has a pool of positive integers,
1. int GetNumber(): return the smallest available number in the pool
2. ReleaseNum(int i): release that the number back into the pool.
What is the good data structure for the pool, describe the big O.

h*n2011-09-27 07:09

2 楼

heap, extract_min and insert.

【在 c********e 的大作中提到】

: The best data structure in terms of big O?
: At the begging, the system has a pool of positive integers,
: 1. int GetNumber(): return the smallest available number in the pool
: 2. ReleaseNum(int i): release that the number back into the pool.
: What is the good data structure for the pool, describe the big O.

f*t2011-09-27 07:09

3 楼

min_heap
build from array O(n)
get O(1)
release O(lg n)

c*e2011-09-27 07:09

4 楼

get should be O(lg n) not O(1).
I answered heap, but I were asked whether there is a better data structure.

j*x2011-09-27 07:09

5 楼

看看Fibonacci heap

【在 c********e 的大作中提到】

: get should be O(lg n) not O(1).
: I answered heap, but I were asked whether there is a better data structure.

j*x2011-09-27 07:09

6 楼

Effect of different data structures
The designer of the priority queue should take into account what sort of
access pattern the priority queue will be subject to, and what computational
resources are most important to the designer. The designer can then use
various specialized types of heaps:
There are a number of specialized heap data structures that either supply
additional operations or outperform the above approaches. The binary heap
uses O(log n) time for both operations, but allows peeking at the element of
highest priority without removing it in constant time. Binomial heaps add
several more operations, but require O(log n) time for peeking. Fibonacci
heaps can insert elements, peek at the highest priority element, and
increase an element's priority in amortized constant time[citation needed] (
deletions are still O(log n)).
While relying on a heap is a common way to implement priority queues, for
integer data faster implementations exist (this can even apply to datatypes
that have finite range, such as floats):
When the set of keys is {1, 2, ..., C}, a van Emde Boas tree supports the
minimum, maximum, insert, delete, search, extract-min, extract-max,
predecessor and successor operations in O(log log C) time, but has a space
cost for small queues of about O(2m/2), where m is the number of bits in the
priority value.[1]
The Fusion tree algorithm by Fredman and Willard implements the minimum
operation in O(1) time and insert and extract-min operations in time.[2]
For applications that do many "peek" operations for every "extract-min"
operation, the time complexity for peek can be reduced to O(1) in all tree
and heap implementations by caching the highest priority element after every
insertion and removal. (For insertion this adds at most constant cost,
since the newly inserted element need only be compared to the previously
cached minimum element. For deletion, this at most adds an additional "peek"
cost, which is nearly always cheaper than the deletion cost, so overall
time complexity is not affected by this change).

【在 c********e 的大作中提到】