CODEWITHSUNDEEP
algorithmrandomdata-structuresqueuedeque
lightning_missile
lightning_missile

Reputation: 2992

Randomised Queue implementation - ideas for randomness

I am taking the Algorithms course in coursera. One of the assignments is the following:

Randomized queue. A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in the data structure.

I am trying to find a way to implement dequeue (randomly removing an item) in a constant amount of time. I have thought of an idea to do this recquiring a deque (which supports removing and adding an item from the front and back in constant time). My idea is as follows:

The reason why the randomness happens in enqueue rather than in dequeue is because I find it to be not exactly random (E.G. n calls to enqueue will have dequeue only return either the first or nth item). So to be sure the items are being removed randomly, I decided to enqueue them randomly.

This idea seems good to me because I cannot find holes in it, but the problem is I cannot prove that my idea would really work. I don't know much about randomness. In fact, this is only the 5th time I am working with random data structures.

Is my idea correct? Will it generate a data structure that removes items at random?

Upvotes: 2

Views: 1155

Answers (2)

Nelfeal
Nelfeal

Reputation: 13269

Enqueueing only at the ends does not produce a uniformly random sequence. The last item to be enqueued is necessarily at either ends, and the first item to be enqueued is more likely to be somewhere in the middle than at either ends after enqueueing other items.

To illustrate, take the set of three items {1, 2, 3}, the smallest set that does not result in a uniform distribution. Enqueueing them in that order gives the following possible results (in parenthesis is where to enqueue the next item).

[1] -> (front) -> [1, 2] -> (front) -> [1, 2, 3]
[1] -> (front) -> [1, 2] -> (back) -> [3, 1, 2]
[1] -> (back) -> [2, 1] -> (front) -> [2, 1, 3]
[1] -> (back) -> [2, 1] -> (back) -> [3, 2, 1]

These four results are the only possibilities and are all equally likely. And as you can see, the last item is never in the middle while both the first and second items are in the middle twice.

What you want is to dequeue at a random place. But you don't need to preserve the order of other items, since they are uniformly distributed. That means you can just swap the last item with a random one, and then dequeue that one (which became the last item).

Upvotes: 2

pjs
pjs

Reputation: 19855

I don't think your proposed approach will work because of the uniformity requirement. Uniformity means that every item in the queue has an equal likelihood of being dequeued. Your proposal always adds elements to one of the ends, and dequeues from one end or the other. Consequently, on any given dequeue request the non-end elements have zero probability of being selected.

An alternative might be to use an array-based stack. Add elements at the end of the stack, but for dequeueing choose an element at random, swap it with the last element, and then pop it. That will have uniformity of selection, and all of the component operations are constant time.

Upvotes: 1

Related Questions