May 032017

The structure of Node of a Binary Tree and Doubly linked list are same.

struct Node
   int data;
   Node* left;
   Node* right; 

 Structure of Node of a Binary Tree    

struct Node
   int data;
   Node* previous;
   Node* next; 

  Structure of Node of a Doubly linked list

If we treat left pointer as previous and right pointer as next, we can use the Node of a Binary Tree to represent node of a Doubly linked list or vice-versa.

Given a binary tree, modify the pointers in each node of the tree so that they represent a Doubly linked. Order of the nodes in DLL should be same as that in the in-order traversal.

If the Input Binary tree is as below

Binary Search Tree

then the function should modify pointers in the nodes, as shown below and return the head pointer.

Doubly Linked List
Continue reading »

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 »