Amazon

Q1. There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered. ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Solution:

Here, we have two lists:

• A list of n distances
• A list of n bunks

Lets, use arrays to save the list data.

                int distance[n] = {d1, d2, d3, ......., dn}

                int petrol[n] = {P1, P2, P3, ........, Pn}

The main idea is that at any point of time the cumulative sum of petrol capacities, from starting bunk till current bunk, should be more than the cumulative sum of distances from the starting bunk till the next bunk from the current bunk.

Example:

                petrol[5] = {2, 5, 3, 4, 1}

                distance[5] = {4, 2, 2, 3, 4}

If our starting point is 1st bunk, the cumulative sum arrays of petrol and distance are:
                CumulativePetrol[]     -> 2, 7, 10, 14, 15
                CumulativeDistance[] -> 4, 6,  8,  11, 15
we see that, distance > Petrol at the 1st index itself. So, 1st bunk cannot be the starting point.

So, we move to the next bunk i.e., lets start our journey at Bunk2.
Then, the cumulative arrays are:
                CumulativePetrol[]     -> {5, 8, 12, 13, 15}
                CumulativeDistance[] -> {2, 4,  7,  11, 15}
In this case, at all the indices CumulativePetrol[i] >= CumulativeDistance[i]

Hence, Bunk2 can be a starting point, in order to travel all the Bunks.



Q2. You have to find p,q of matrix p*q such that it fills n elements(n given) Such that
a) matrix should be nearest to a square matrix and
b) 0<=((p*q)-n)<=2

Solution:
Example:
n = 15
Then, p = 4, q=4;
matrix M = 4x4 matrix
        |  1   2   3   4  |
M = |  5   6   7   8  | = p*q
        |  9  10  11 12|
        |  13 14 15  0 |
p = 4x1 column vector
   = Transpose[1, 5, 9, 13 ]
q = 1x4 row vector
   = [1, 2, ..... ]

static void getMatrix(int n, int[] p, int[] q)
{
}


Q3. Given a Binary Tree. Assuming each node denotes some x,y coordinate. root node denotes (0,0). Write a code to display coordinate of all nodes.

                  o(0,0)
               /            \
     o(-1,-1)            o(1,-1)
    /              \           /         \
o(-2,-2)  o(-1,-2)   o(0,-2)  o(1,-2)


Q4. Given a list of words. Print all anagrams together.