Fog Creek Software
Discussion Board




Find a  deque length

A deque (double-ended queue) has unknown number of integer elements.
Memory is limited, so it is not possible to pop all the elements and count them.
It is possible to allocate some memory for few elements, although.

Is there a way to find the length of the queue with 100% probability?

(The deque has methods to push and pop elements to/ from the tail and the head.)

Tim Isaev
Monday, April 05, 2004

Does the queue have identical integers in it?

If all integers in the queue are unique, then

length = 0
if queue is nonempty
{
    startItem = dequeue item from the head
    enqueue startItem to tail
    do
    {
          x = dequeue item from the head
          enqueue x to tail
          increase length by one
    }
    while (x != startItem)
}

At the end length is the number of items in the queue and the queue is not changed.

JHY
Monday, April 05, 2004

Allocate a new deque, and pop elements from the old deque onto the new deque one by one, counting as you go.

Ham Fisted
Monday, April 05, 2004

It would work if it is a queue with dynamic memory allocation.

For some reason I assumed the queue is represented using a fixed size array and the physical size could not be expanded and shrinked as you push and pop.

JHY
Monday, April 05, 2004

Push some number X, which is not equal to either the head or tail of the queue, onto the tail of the queue. Pop the head onto the tail some N times, until you find X at the head of the queue. Now you have a guess at the length of the queue.

But if the number X was already present somewhere else in the deque, the guess will be wrong. To check, rewind to the beginning by popping tail onto head N times. Then remove the original number X you added. Wind forward again N times, and check that the second X has been removed.

If X is gone, the length of the queue is N. If the second X is still there, rewind to the beginning again, and start over with a different choice of X.

Ham Fisted
Tuesday, April 06, 2004

Honestly, I don't know the right answer.
But I like the slick idea with the dynamic deque.

I was thinking about pushing in some distinctive elements (a marker) and looping through the deque (e.g. pophead - pushtail) until these elements are found.

Of course, the probability of success depends on uniqueness of the marker. (GUID should work really well.)

Tim Isaev
Tuesday, April 06, 2004

Addendum to HamFisted's solution:

You don't need to select a new value of X once you determine that X is one of the elements.  Just add 2 Xs at the head of the queue and loop head to tail, skipping over single X values until you find 2 Xas, which you remove and rewind as before.

la vache
Wednesday, April 07, 2004

And what if there is another '2 X' consecutive pair located in the que?

I've come up with a few solutions, but can't seem to find one that 100% guarantees the length (and finishes in finite amount of time).

Manish Joshi
Friday, April 09, 2004

"what if there is another '2 X' consecutive pair located in the que?"

If there is another '2 X' consecutive pair located in the queue, I suppose then you try 3 X's.

This is what to do (copy, pasted, and modified from la vache's post):
"Just add 3 Xs at the head of the queue and loop head to tail, skipping over single X values and 2 X's until you find 3 X's, which you remove and rewind as before."

If there is another 3 consecutive X sequence in the queue, then try 4 X's, and so forth.

However, this method fails when the queue contains only X's, because when you check the elements in the deque, it just keeps on looping and you will always get X, so you will be able to get any number of X's this way, thus if you add k X's to the deque, you could also find k (not necessarily distinct) X's in the deque after you delete the k X's that you added.  Therefore, this method does not work 100%.

JHY
Friday, April 09, 2004

"Therefore, this method does not work 100%"

Just like many, many other algorithms that use some kind of marker. The problem is that the algorithms make probablistic assumptions on the items in the que.

Anyone have a pull-proof algorithm? Is it possible?

Manish Joshi
Saturday, April 10, 2004

Push a random marker entry onto the tail. Cycle through the deque until you find that entry. Then back out, push in a different marker, and advance the same number of positions. Check that you find the new marker.

If you didn't find the new marker continue to advance until you do. Then back out again, insert another  changed marker and check that you find it in the new position. Repeat this until you find the changed marker.

David Clayworth
Tuesday, April 13, 2004

All of these solutions do, in fact, work 100% of the time because the length of the array is finite.

The worst-case time complexity is O(N^2) rather than O(N), but the question doesn't call for O(N) in all cases.

Ham Fisted
Tuesday, April 13, 2004

JHY's solution fails for a deque that is all Xs, no matter what the length (e.g. 1). I think some of the others will give you trouble unless you know a top limit of the queue (not the same as knowing it is finite). I believe mine works for any length deque.

David Clayworth
Friday, April 16, 2004

*  Recent Topics

*  Fog Creek Home