Archive for the ‘Amazon’ Category

Find Next Larger no. Using Same Digits

Posted: September 12, 2012 in Amazon

Q. The input of the problem is a number. (Say 43652). You have to compute a number using same digits such that new number is greater than original number and out of all such options, its should be closest to the original number. Answer for Example –  45236

A.

  • Examine digits starting from zeroth place and move towards higher order. Stop at the point where current digit is less than previous one. Say this location is j. In example 4365, the digit is ‘3’.
  • If no such element met and all digits occurred in ascending order, throw error saying that number is maximum possible with given digits.
  • The digits examined so far (from 0th position to j-1) are sorted. Do binary search on same window and spot the element just greater than digit at location j. In example, its ‘5’.
  • Swap these digits (Example: 45632)
  • Examined digits (from 0th position to j-1) is still sorted. Change the order by reversing the sequence. (Example: sorted 45 ‘236’)
  • The resulting number is the answer 🙂

Complexity O(n).

Spotting the element takes O(logn) as its binary search.

Sorting takes O(n) because we are just reversing the digits sequence.

Advertisements

Q. You have an array of integers. Device an algorithm that can return all possible pythagorean triplets within them.

Example, (a,b,c) is a valid answer if    ”  a sq  + b sq  = c sq ”

A. My answer takes O(n sq) time.

  • Square all elements and keep them in an array. Time taken – O(n).
  • Our problem is simplified get numbers (a,b,c) such that to a + b = c.
  • Sort the array. Time taken O(nlogn)
  • Keep a as first element and c as last element. Try to find last b where a+b <=c
  • Store the index of that last b. Because a+b will be > c for further elements.
  • Now, search for the sum a+b within [b+1, c]. Binary search can be used.
  • If no triplet is found, increment a to next location and repeat the process.
  • Time complexity O(n sq).

Since O(n sq) is the most dominating its the overall time taken in this process.

Interviewer was looking for a solution that takes O(nlogn) and I am still thinking about it. 🙂

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).

 

Q. There is a bi-dimensional array. All the rows and columns of this array are sorted in ascending order. Example –

3 32 34 39
4 35 38 40
6 56 57 77
45 78 88 90

Device an algorithm which can search an element in this array within O(n) time.

A. Start from top-right.

  • If search key is lesser than current element, move towards left.
  • If search key is greater, move towards down.
  • Keep doing the same thing until you reach the element.
  • If you reach first column/last row and couldn’t move further, we can conclude the search key is not present in the array.

In worst case, search key will be bottom-left element and will need 2n comparisons. Hence, overall complexity is O(n).

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. You have series of n numbers, (like 1 2 3 4). However they are shuffled and not in sorted form. One of these number is repeated and you have to find the same.

A.

  • Total numbers – n+1 (as there is one repeated element.)
  • Sum of all numbers – n(n+1)/2  + repeatedNumber.
  • Calculate the sum of all numbers and subtract n(n+1)/2 from it. Result will be the repeated number.

This problem can be extended by saying that a all elements of a subset series of length k are repeated which makes it even more interesting.

For that case, above operation gives the sum of all k elements in series. Getting the avg. of it will give us the middle element in the series and we can calculate other members of series.

 

 

Retrieval From Stack

Posted: February 12, 2011 in Algorithms, Amazon, data structures, inMobi

Q. From a given stream of numbers, I should be able to retrieve latest element. Also, you have to support reading the minimum of elements encountered so far.

A. For storing and retrieving the elements, stack is the best data structure enforcing LIFO traversal. For keeping the minimum value, we need to implement another stack in parallel.

  • The minimum element stack will keep the minimum element only for a particular node.
  • If new element, is lesser than current minimum, push the new number in the minimum stack.
  • If new element is greater than current minimum, push the old minimum again in the minimum stack.
  • While popping out any element from the main stack, pop out the respective node from the minimum stack as well.

Reading the minimum value will hence be a operation of complexity O(1).