None.. All questions were simple. Reverse a linked list, find a duplicate node in the linked list, etc

Question

neakor · Accepted Answer

ummm it's much simpler than that Mike.

Reverse the list:

public void reverse(final List list) {
    Node prev = null;
    Node next = list.head;
    Node n = list.head;
    while(next != null) {
        next = n.next;
        n.next = prev;
        prev = n;
        n = next;
    }
}

as you can see, you don't need a second list. this will run in O(n) time.

Also for finding the duplicate. Just use a hash map. on average you get O(1) for insertion into the map and you don't even need to go through the entire list as the question only asks to find "a" duplicate node. so something like this.

public Node findDuplicate(final List list) {
    final Map map = new HashMap();
    for(final Node n : list) {
        if(map.contains(n)) return n;
        else map.put(n, n);
    }
}

Worst case run the loop n times each contains check worst case O(n) but average should be O(1). So your best case runtime for the whole thing should be O(n), and worst case O(n^2).

Sigiloso · Answer

For Reversing the LinkedList: Push the link list on a stack and pop the stack to create a new linked list

Sigiloso · Answer

How do you find duplicate? Using bitmaps or hash right?

Mike · Answer

reversing a linked list is O(n) if you are allowed to keep a second linked list with the opposite data. Finding a duplicate node in a linked list can be done using a Hash, yes, or bitmaps (a little more work). But ideally, I think I would iterate the tree and store them into a heap of some sort and then pop the top of the heap and have the answer. This is O(n) to iterate and O(log n) to insert into the heap. If you were to use a Hash you would have to populate the hash, and then iterate over the hash to find the largest key->value pair (and iteration of a Hash is O(n)).

Thus,
Time to iterate linked list = T_LL = O(n)
Time to iterate hash = T_H = O(n)
Time to insert to heap = T_Heap = O(log n)
and Time to access root node (max occurrences in Heap) = T_H_Access = O(1)

Clearly T_LL + T_H > T_Heap + T_H_Access

I am sure more ways exist! This just illustrates the work for 2 ways.

Yahoo

Pergunta de entrevista da empresa Yahoo

Respostas da entrevista

Empresas seguidas

Buscas de vagas