Archive for the ‘CA’ Category

Q. Given a number n, find a set such that –

  • Sum of all the elements should result into n.
  • Multiplication of all the elements should be greater than any other similar set (whose elements result n when summed up).

A. This is a very interesting problem as we have to go through every combination and calculate and compare the multiplication. Since, there is no restriction on the length of the subset, it makes problem much more interesting.

I propose use of dynamic programming here. We will start computing the f(n) from 1

At every stage, we have to compute all combinations of f(1).. f(n-1)

f(n) = max {

f(1) * f(n-1)

f(2) * f(n-2)

….. }

 

To avoid repeated operations, we can store start computing f(1).. f(n-1)  one by one and do the book keeping of the result.

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.

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. Write an algorithm to fill a magic square of size 3.  You are given a position to start with (location of 1 on any edge).

Magic square has following properties –

  • No number is repeated.
  • All rows, columns and diagonals give equal sum.
8 1 6
3 5 7
4 9 2

A. The best method to approach this problem is called Siamese method.

  • Iterate from 1 to 9. We are already given the location of 1.
  • Keep circular shifting in consideration. Means if you are at the top row and want to go up, you are moving to last row by circular shift.
  • Post the next element up and right of current location
  • If that location is already occupied, post it on a location just below the current pointer.
  • Move to next element until the square is complete.

Complexity of pushing n elements is O(n).

 

Find The Door

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

Q. You are standing in front of a wall and finding a door to cross it. Some constraints –

  • You don’t know the length of the wall
  • You can view only in front of you. At a particular location, you can check if there is a door in front of you. No peeking on left or right side.
  • You don’t know if door is on left or right side.

A. Since, we don’t know the direction, we need to oscillate between left and right side and keep increasing the oscillation range periodically.

  • Move two steps left, if door was not in way, move 4 steps right to check the opposite direction.
  • If still didn’t get the door, increase the range and move 8 steps and so on till we get the door..
  • The range should exponentially increase with the number of steps. Eg. If you are moving 4 steps on right, the oscillation range should be increased by 4 steps.

The complexity of this operation will be O(n square).

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.

Q. There is a indefinite stream of numbers coming and you have to write a alog which return the kth minimum element in the end.

A. Keep a max heap of size K.

  • The max element will always be on the top.
  • Compare each incoming element with it.
  • In case, the new number is lesser than max, extract max from heap and insert the new number.
  • At any instance, you are keeping K minimum element.

Total complexity – n log k (where n is the number of elements parsed)