Apr 232017

Given a character matrix in which some of the cells have alphabets written on them while other cells are empty (empty cells contains character ‘-‘ in them). For example consider the below matrix:

A - -
- B -
- - C

All characters are unique. Set character on all empty cells in such a way that if we draw border around all cells of same characters, we get a rectangle. One of the solution for the above matrix is:

There can be multiple solutions possible for a given input matrix. Write code to print one of the possible solutions. Continue reading »

Apr 142017

Given a matrix of integers of order M*N and coordinates of a rectangular region in the matrix, write code to find the sum of all the elements in that rectangular region.

For example, if the input matrix is

And co-ordinated given are (3,4) and (6, 8), then they represent the below rectangular region whose Sum is 70.

Hence the output should be 70. How will your logic change if we need to compute sum of rectangular region many times for the same given matrix. Continue reading »

Feb 022013

You are given the Ancestor matrix of a Binary tree, write an Algorithm to construct the corresponding tree.

For example, the below tree:

Will have the following ancestor Matrix

The order of rows in the above matrix is not defined. I have kept it in the ascending order because the data in our nodes is numeric and can be ordered.

Essentially, in the ancestor matrix, each node has a row and a column (may not be the same). The value at a[i][j] will be 1 iff node of Node representing jth column is the ancestor of node representing the i‘th row.

Write an algorithm that can construct the binary tree from a given Ancestor matrix.

Jan 312013

Each element in the array is connected to eight other elements (toward top, down, left and right). For example, the zero below is connected to all the ones

1 1 1 
1 0 1
1 1 1

Given a two-dimensional array of 0’s and 1’s. Find the number of islands where an island is a group of connected 1’s. For example: The below array has 4 islands (shown in different colours)

1  1  0  0  0 
0  1  0  0  1
1  0  0  1  1
0  0  0  0  0
1  1  1  0  1

Write code which will accept this 2-dim array and return the number of islands.
Continue reading »

Jan 292013

wine glassGlasses are arranged in the form of triangle (on top of each other) as shown below:

       2     3
    4     5     6
  7    8     9    10

Liquid is poured into 1st glass (Glass no. 1). When it is full, then extra liquid will flow into the glasses 2 and 3 in equal quantities. When glass 2 and 3 are full, liquid will flow into glasses 4, 5 and 6.

From Glass-2 it will flow equally into 4 and 5 and from glass 3 it will flow equally into glass 5 and 6. Hence Glass-5 will get more liquid (from both Glass-2 & Glass-3) as shown in the image on the right.

If capacity of each glass is C and you pour N liters of liquid in Glass-1, then how much liquid will be there in each glass?
Continue reading »