Archive for the ‘Java’ Category

Q. There are k sorted lists and we have to merge them to make a single sorted list in best time.

A. I used min heap of size k to contain one element of each list. Each node of heap also contains the id of the list it belongs to.

  • Pick out first element of each list and push it into heap.
  • Take the minimum element out of the heap. Record the list it belongs to say list j.
  • Push the next element from list j back into heap.
  • Repeat the operation till all elements are parsed.

If all lists are of length n, each element has to pushed into heap at some point.

Complexity for pushing the element is logk in heap.

Overall complexity will be O(nk logk).

Advertisements

Design LRU Cache

Posted: February 12, 2011 in Algorithms, CA, HomeShop, Java, Puzzles

Q.  You have to design a LRU cache such that all operations can be done in O(1) – read, write and insert.

  • In case, cache is full, you have to remove an element which was read/written last.
  • Each read should update the timestamp of these elements.
  • Read request of the element contains a key which is not the location of the element.

A.  Assuming hashmap has retrieval complexity of O(1), we can do this using a doubly link list and a Hashmap

  • Doubly link list will be used to store indexes sorted by date/timestamp information.
  • Keep track of first and last node.
  • No sorting effort is needed as each new node will have latest timestamp.
  • The Hashmap will retrieve the node searched by key. It will also contain pointer to its respective doubly link list node.

READ –

  • Search the node by key. Retrieve the node value and index for doubly linklist.
  • Delete the node from doubly linked list and add it with the updated date value at the starting of the list.
  • Complexity of deleting a node in doubly link list is O(1) as we can reach to it without traversing the list.

INSERT –

  • Add the new node in the hashmap and the doubly linked list.
  • If the cache is full, use the pointer to the last node in the doubly linked list and delete that node. Set the delete pointer appropriately.
  • Inserting at the start of linked list is operation with time O(1).

UPDATE –

  • Update operation will need similar operation as READ in terms of accessing the data structure. Hence, similar time complexities apply.

DELETE –

  • Deleting the node from the doubly-linked list and hashmap can be done in O(1).

 

I was asked to write the java code for implementing the same. It took a lot of effort.

Used multidimensional array for implementing the doubly-linked list and maintained the pointers for previous and next nodes.

Q. Tell a case when singleton class doesn’t return single object.

A. If the Singleton class is loaded by different class loaders, then the object created them are also taken as different.

If one has to make an absolute Singleton, Classloading should be taken into consideration and parent classloader should be used to initialize it.