Linkedlist keep track of min in constant time?

EDIT:

This isn't as trivial as you think. Consider the fact that each addition of a new number pushes out an old number from the linkedlist.

The solution doesn't seem to be as simple as keeping track of a min number with a variable. What if the minimum gets pushed out of the linkedlist? Then what? How do you know what the new min is?

I heard this interview question:

You have a fixed length linked list.

• At time t=0, the linkedlist is filled with ran开发者_Python百科dom numbers.

• At each increment in time, one new number is fed into the head of the linkedlist, and one number is pushed out from the tail.

• You are allowed only ONE traversal before the first time interval.

  • This means one traversal ever. Not once at every time t.

    .

• O(1) storage.

Your task is to be able to return the min of the linkedlist at every time interation.

What is an algorithm that would be able to do this?

Interesting note:

Since there's no information regarding time complexity, you are allowed to use sort operations. The only problem then is: sorting takes more than one iteration.

First,

O(1) storage is not the same as an a single register. It means constant space usage.

Second,

I am going to call your LL a constant size queue (CSQ).

When initializing your queue, also initialize a min-heap where all elements of the queue keep a reference (pointer) to the heap node corresponding to them.

1 op on CSQ

• Pop 1 element out in O(1) time of the CSQ.
• Remove corresponding node from the min-heap in O(lg n) time.
• Add corresponding element to the min-heap in O(lg n) time.
• Push 1 element into the CSQ in O(1) time and mark a reference to the heap node added above.

The above operations guarentee that the heap size will always remain in sync with the queue size --hence O(1). The heap can be constructed in a single travesal.

Finding min

Clearly O(1). Just return the head of the min heap.

First off, a LL is usually used for dynamic sizes. You would probably want a regular array for fixed-size since, once again usually, it will take up less memory.

Second, you seem to have more of a queue than a list, which means when you push an element in you pop one out. In that case, the minimum can be constantly changing. Naively you can search for the minimum in any 1D list in O(n) time.

Less naively, your LL could also be a pre-sorted (sort-on-insert) heap, in which case finding the minimum element can be O(1) (depending on the structure chosen). However, insert will take O(n) time.

I am aware this does not answer your question, but this really sounds like a homework question. Use this as a guide/reference/help for your problem. :)

Hope everything gets solved, and I hope I helped!

I'm surprised no one posted this (so it's probably wrong), but (pseudocode):

struct abc                                    // sorry for the name :)
{
    int pos
    int num
}
initialize
{
    struct abc min_array[linked_list_length];   // O(1) space

    fill(min_array, linked_list_elements);      // place every element in the array
    sort(min_array);                            // sort in ascending order, the sorting
                                                // compares num
}

insert_element
{
    linked_list.push(value);
    linked_list.pop();

    for each element in min_array {
        element.pos += 1

        if element.pos > linked_list.elementCount then   // this was popped out!
            element.pos = 1;
            element.num = value;
        end if
    }

    sort(min_array);        // as before, sorting compares only num
}

get_min_value
{
    return min_array[0];
}

The only possible solution I can have is through a technicality:

Since the size of the linkedlist is fixed at the time of WRITING, that means N is constant. In that case, we are technically allowed to store an auxiliary structure that is a direct copy of the linkedlist (perhaps in an array). This is O(1) storage since N is constant.

So, basically, this is a queue, implemented as a linked list (correct me if I am wrong). To solve this, I would just change the idea of the node. A typical node will have next pointer and a value. Change this to have three elements, nextPointer, value and minSoFar. If you don't like the idea of changing the queue design, still, read this algo and I have provided another idea at the end.

I think this can be done in O(1) The trick is while traversing the list, keep track of the smallest element encountered until that point in the list and store it in the current node. So, for example you have the following queue

Head at 5 and tail at 13

5 |7 |6 |9 |5 |13 |

My modified queue will contain the nodes like

{5,5}|{7,6}|{6,6}|{9,9}|{13,13}| ({nodeVal, minSoFar})

Now, consider an operation, adding 3 to the queue and removing 13, the queue becomes

{3,3}|{5,5}|{7,6}|{6,6}|{9,9}|

Since 3 is less than the current head element, the min so far for the head element is its value

Consider another case where you need to add 15 to the queue

{15,5}|{5,5}|{7,6}|{6,6}|{9,9}|

Since 15 is greater than the current head element, the current minimum value becomes 5.

So to find the minimum element in the queue/list, all you need to do is check the head element and your time complexity will be O(1)

If you don't want to modify the queue, maintain a parallel queue and keep the minValueSoFar in that queue and mirror the operations in that queue.

If node can be defined as follows, then solution is simple:

class Node {
    int data;
    Node next;
    Node prevMin;
}