3

This question was asked in the interview:

Propose and implement a data structure that works with integer data from final and continuous ranges of integers. The data structure should support O(1) insert and remove operations as well findOldest (the oldest value inserted to the data structure).

No duplication is allowed (i.e. if some value already inside - it should not be added once more)

Also, if needed, the some init might be used for initialization.

I proposed a solution to use an array (size as range size) of 1/0 indicating the value is inside. It solves insert/remove and requires O(range size) initialization.

But I have no idea how to implement findOldest with the given constraints.

Any ideas?

P.S. No dynamic allocation is allowed.

4

1 回答 1

3

I apologize if I've misinterpreted your question, but the sense I get is that

  • You have a fixed range of values you're considering (say, [0, N))
  • You need to support insertions and deletions without duplicates.
  • You need to support findOldest.

One option would be to build an array of length N, where each entry stores a boolean "is active" flag as well as a pointer. Additionally, each entry has a doubly-linked list cell in it. Intuitively, you're building a bitvector with a linked list threaded through it storing the insertion order.

Initially, all bits are set to false and the pointers are all NULL. When you do an insertion, set the bit on the appropriate cell to true (returning immediately if it's already set), then update the doubly-linked list of elements by appending this new cell to it. This takes time O(1). To do a findOldest step, just query the pointer to the oldest element. Finally, to do a removal step, clear the bit on the element in question and remove it from the doubly-linked list, updating the head and tail pointer if necessary.

All in all, all operations take time O(1) and no dynamic allocations are performed because the linked list cells are preallocated as part of the array.

Hope this helps!

于 2013-11-05T21:44:35.013 回答