May 022017
 

Given an array of numbers find the maximum XOR value of two numbers in the array.

Input Array = {12, 15, 5, 1, 7, 9, 8, 6, 10, 13};
Output = 15 (XOR of 5 and 10)

  5 = 0101
 10 = 1010
 ---------
XOR = 1111

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
 

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 »

Apr 262016
 

Given a string, print the variation of string as shown below

Input String: ‘hat’

  • Replace one character with numeric one(‘1’): ‘1at‘, ‘h1t‘, ‘ha1
  • Replace two characters with ‘1’ each: ‘11t‘, ‘h11‘, ‘1a1
  • Replace three characters with ‘1’ each: ‘111

In all the strings above, wherever the numeric characters are consecutive, add them. So ’11t’ will become ‘2t’, Similarly ‘111’ will become ‘3’. So the final output will be

hat ha1 h1t h2 1at 1a1 2t 3

Continue reading »

Oct 152013
 

Given an array containing both positive and negative integers, write code to rearrange the elements so that positive and negative numbers comes alternately. If positive (or negative) integers is not equal in number then extra positive (or negative) numbers should come at the end of array. For example:

Input : {1, 2, -2, -5, 6, 7, -8}
Output: {1, -2, 2, -5, 6, -8, 7}

Input : {-1, 2, 3, -5, -6, -7, -8}
Output: {-1, 2, -5, 3, -6, -7, -8}

Continue reading »

Jul 262013
 

A better implementation of Stack is usually using linked list unless you are sure of the number of elements in array. But if you are just starting with data structures and are not familiar with linked list, you can try implementing stack in an array.

While using array to implement stack is easy, it has limitation that the stack cannot grow beyond a fixed size (of array).  Continue reading »