Archive for the ‘HomeShop’ Category

Find The Average

Posted: February 12, 2011 in Algorithms, CA, data structures, HomeShop, Puzzles

Q. Given a set of n numbers (data type long). Write an algorithm to get the average.

  • It should work if one of the contributing number is the maximum possible number of type long.
  • Casting it to other data types is not allowed.

A. This question made me thing alot as we can’t use addition for getting the average. If we do, first constraint might not get incorporated. Finally, I came up with an equation.

Keep looping till you hit the last number. Counter is the index variable for the loop that increments by one at each iteration.

average = average + (nextNumber – average)/counter

We have to round of everytime we hit an uneven divide and there is a loss of precision.

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. Between 4 rooms of a house, there are certain connections between those rooms for electricity. A matrix is used for specifying the connection details between rooms and the details of connectivity is maintained in a matrix –

A B C D
A 0 3 0 23
B 45 0 32 3
C 5 5 0 3
D 45 3 0 0

Where the integers represent the connection wire length between those two rooms.

Write an algorithm to eliminate the redundant use of wires such that only minimum wire required is in use and all rooms are connected.

Its not necessary that rooms are connected directly. If A connects to B and B connects to C, we can say A,B,C are connected.

A. I related it as a minimum spanning tree problem.

  • Create a method which can tell you if all nodes are connected.
  • Store all values in descending order. Also, store the respective indices.
  • Start eliminating nodes with maximum values. Spare only if it breaks the connectivity. We can call function created in first step to check it.

Complexity of our algorithm –

  • Method to check if tree is still connected. This operation takes O(n) time.
  • Removing redundant connections (A to B, B to A). This operation takes O(n) time.
  • Sorting of all the elements. This operation takes O(nlogn) time.
  • Eliminating all nodes and checking the connectivity. O(n square) Since, at every node we have to call check connectivity.

Since, O(n square) dominates, its the overall complexity of this approach.

Implementing it in the code for this was very challenging.

Q. Given a number, you have to compute nearest palindrome number. This palindrome number should be greater than given number.

A. Calculate the number of digits and get the most significant half out of it. For example, most significant first half of 2345 will be 23. Most significant first half of 45436 will be 454.

  • If number of digits are even, flip the most significant first half towards lower significant half that makes the palindrome. If the palindrome is smaller than the original, add one to the most significant half and then flip it over. Example, number -2345, most significant half -23, first candidate palindrome – 2332. Since, this is less than 2345, we add 1 to most significant half which makes it 24. Our next candidate for palindrome becomes 2445.
  • If number of digits are odd, we should not flip the middle one. For example, 45436, most significant digits will be 454 and our candidate for palindrome will be 45454. Since, it is greater than original, we’ll keep this as answer.
  • In case, adding one adds another digit to the number, we have to switch the process as per new number of digits.