May 012017
 

String matching is a big research area and there are many data structure (eg. B-Tree, HashMap, Set) that help indexing of strings. There are also many algorithms used for string matching (like KMP, etc.)

The major application of Trie data structure is in storing a dictionary (Collection of strings) such the searching for a word in dictionary become O(k) time operation where k is the number of characters in the word. Continue reading »

Apr 262017
 

Given a Binary tree, write code to find the length of longest path such that value of node in that path are consecutive and in decreasing order. For example is the tree is

Then output should be: 3 because path (5, 4, 3) has all nodes in consecutively decreasing order.

Note that Path <5, 6, 7> are also consecutive, but they are not in decreasing order, hence not considered. Continue reading »

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 »

Apr 132017
 

Given a row (linear), two blocks are placed at each end and there are n empty positions between then. If ‘B’ represent block and n = 9 then the row looks like below:

 B _ _ _ _ _ _ _ _ _ B

One blocks can be placed on each empty position. k blocks need to be placed one at a time. When i’th block is being placed, we place it such that it is at farthest distance from both sides.

For example, in the above array the first block will be placed at the centre position

 B _ _ _ _ B _ _ _ _ B

The second block can be placed either on left side of right side (because both will result block being placed such that distance from both side will be same). Either way, will result in placing a block that has one empty block on one side and 2 on the other side (see below 4 arrangements).

B _ B _ _ B _ _ _ _ B
B _ _ B _ B _ _ _ _ B
B _ _ _ _ B _ B _ _ B
B _ _ _ _ B _ _ B _ B

Write code that places k blocks one by one and when the k’th block is placed, let us say it has x empty blocks on the left side and y empty blocks on the right side. Print the larger of the two values (x , y). In our case, if N=9 and K = 2, then output should be 2. Because the second block has two empty positions one of the two sides. Continue reading »

Apr 102017
 

Given a number N given in the form of array, with each index storing one digit of the number. Write code to change the number to the greatest number less than N, such that digits of that number are in non-decreasing order.

For example:

INPUT ARRAY: {1, 4, 3} (representing number 143)
OUTPUT : 139

INPUT ARRAY: {2, 2, 2, 1} (representing number 2221)
OUTPUT : 1999

Continue reading »

Apr 092017
 

This problem is to place 8 queens on the chess board so that they do not check each other. It can be asked in two ways:

  1. Find one of the possible solutions to place 8-queens, so that no queen can attack any other.
  2. How many different ways are possible to place 8 queens such that no one attack the other.

Continue reading »

Apr 092017
 

Given a string of bits and a number k. In one flip, you can toggle k consecutive characters, how many flips are required to change the entire string to all ones. For example

Input String: 0000110000 
k: 3
OUTPUT: 4

Following are the four flips:

FLIP-1: 1110110000
FLIP-2: 1110110111
FLIP-3: 1111000111
FLIP-4: 1111111111

If it is not possible to set all bits in the string then return -1. For example:

Input String: 01010101 
k: 3
OUTPUT: -1

Continue reading »

Jan 312017
 

Given a Binary Tree and a Node, Write a function that return the vertical distance of that node from root of the tree. The vertical distance of a node is computed as below:

  • Then the vertical distance of root is 0.
  • The vertical distance of right node is distance of root+1.
  • The vertical distance of left node is distance of root-1.

For example, if the binary tree is as given below:

Then vertical distance of Node-B from root is -1. E is at a vertical distance 0 from the root (we move one step left and then one step right, hence the net vertical distance from root is zero). Continue reading »