CareerCup

i was asked the following question and they need java solution for it.

Checkers is an ancient board game played by two players, traditionally called 'Black' and 'White'. It is played by turns on an 8x8 board, which has alternating black and white squares. All the pieces are placed on black squares only and move in a diagonal fashion, i.e., a piece cannot move vertically or horizontally, but only diagonally.
When it is a player's turn, he can either make a move or a sequence of jumps. A jump is defined as a diagonal move over exactly one piece of the opposing colour. The piece that has been jumped over is said to be captured, i.e., it is removed from the board. The players try to capture as many of the opponent's pieces as possible and the game ends when all the pieces of any one player are captured.

Checkers rule states that the white piece (A) has a choice of moving to his left, or jumping over the black piece. Since the intent of the game is to capture as many of the opponent's pieces as possible, White should choose 'A' to jump over the black piece. After jumping, 'A' reaches a square from which he can jump further, either left or right. The jump to the left is better because it allows White to make one more jump, unlike the jump to the right, which leads to no more jumps. The white piece (, in the figure, can only move and not jump. Thus, according to the figure, White can jump thrice in one turn, using 'A' or alternatively can move once using 'B'. Obviously, the better choice is jumping with A.
You have to write a program which, given a board configuration, calculates the maximum number of jumps possible in one turn, by any White piece. Given the board above, the program would output '3'.
Notes:
It is illegal to jump over a piece of your own colour.
A player's turn is complete when he makes either a move or a sequence of jumps.
A jump can land only on an empty square.
Input specification:
The input will consist of eight (8) lines of eight (8) characters each. The characters will be one of the set {B, W, ~, #}.
� B => Black piece
� W => White piece
� ~ => An empty black square
� # => White square. Note that a piece can never land on a white square
Output specification:
Your program has to output the maximum number of jumps that can be made by any of the white pieces. If white cannot make any jump at all, then your program must print the integer '0' (zero)

Sample Input and Output:

Input:
#B#~#B#~
B#B#B#B#
#~#~#~#~
~#B#~#~#
#~#W#~#~
~#~#~#~#
#W#W#W#~
W#W#W#W#

Output:
4


Input:
~#~#~#~#
#B#B#B#B
~#~#~#~#
#B#B#~#~
~#~#~#~#
#~#B#~#~
~#W#W#W#
#W#W#W#W

Output:
5

Consider a university having a very big campus spread in acres of land. The university is undergoing computerization. All the departments (at-most 50) are to be connected to form the intranet of the university. You have to write a program, implementing Prims algorithm, which will suggest the network topology and also minimise the total length of cable for connecting all the departments. Input to the program will be names of all the departments and straight line distances between the departments (Only those pairs of departments between which cable can be laid will be given). Output of the program should be the minimum length of the cable required.

Input specifications
The first line will contain 2 natural numbers, N and M, separated by a blank space. N indicated the number of departments in the university and M indicates the number of pairs of departments where the cables can be laid. The following M lines will specify the distances between M pairs of departments as dept1 dept2 distance Where dept1 and dept2 are names of the departments (maximum 20 characters) and distance is a positive integer (>0). Assume that the given distances between each pairs of departments will be unique and these M lines will contain atleast one pair for each department.

Output specifications
The first line of the output will be names of the departments as they are included in the solution separated by blank space. If two or more departments are included at a time then their names should be printed in the alphabetic order. The next line will be the minimum length of cable required to form the intranet, terminated with a new line character.

Sample Input/Output
input
7 10
physics chemistry 8
biology physics 9
biology office 15
chemistry office 4
chemistry sanskrit 5
sanskrit office 7
english office 16
english sanskrit 19
english cs 12
sanskrit cs 6
output
chemistry office sanskrit cs
physics biology english
44

In this problem, you have to implement a variation of Insertion Sort as described below.
Suppose X is an array of N positive integers to be sorted. In this scheme, another array Y is used to store the
sorted integers. This array is to be viewed as a circular array, ie. index (N-1)+1 = index 0 and index 0-1 =
index N-1. The sorted integers get stored in a circular manner in Y, ie, it is possible that the index of the
smallest integer may be greater than the index of the largest integer.
Eg. 6 8 _ _ _ 1 2 4 5 is a view of the array Y sometime into the algorithm. ’_’ indicates unused locations of
the array. Smallest integer 1 is at index 5, largest integer 8 is at index 1. So the sorted array in Y is to be
generated by printing the contents from index 5 to 1, assuming the array wraps around at the end, ie. after
index 8, the next index is 0.
Assume that h holds the index of the smallest integer in Y and t holds the index of the largest integer in Y.
Initially,
1. h = t = 0
2. Y[0] = X[0] ie. the first integer in X[] is copied as the first integer in Y[].
3. All other elements in Y[] are initialised to a dummy value -1.
The rest of the integers in X[] are now inserted one by one into Y[] such that Y[] always contains a sorted
list of integers, with the smallest integer at index h and the largest at index t. This is done in the following
manner:
Let I be the next integer from X[] to be inserted into Y[]. Scan the array Y downwards from index h (with
wrap-around at the end) till index t and find out the place in Y[] where I has to fit in. If I fits in at either end
of the list, then insert it at the appropriate place in Y[]. Modify either t or h as appropriate to indicate the new
array structure; ie. either t is incremented or h is decremented (with wrap-around).
If I fits in somewhere in the middle of the list, then I should be inserted by shifting all the S smaller integers
one place to the left or by shifting all the L larger integers one place to the right, depending on the number of
integers to be shifted. That is, if S < L, the smaller integers should be shifted one place to the left and if S >=
L, the larger integers should be shifted one place to the right. Again either h or t should be modified
appropriately.
Example
Integers to be sorted X[]: 25 57 37 48 12 92 86 33
Contents of Y[] after inserting each integer from X[]:
Initially (t=0, h=0)
25 –1 –1 –1 –1 –1 –1 –1
57 fits in at end (t=1)
25 57 –1 –1 –1 –1 –1 –1
37 fits in middle, S=1, L=1, so shift 57 right. (t=2)
25 37 57 –1 –1 –1 –1 –1
48 fist in middle, S=2, L=1, So shift 57 right. (t=3)
25 37 48 57 –1 –1 –1 –1
12 fits in at beginning, circular property, (h=8, t=3)
25 37 48 57 –1 –1 –1 12
92 fits in at end (t=4).
25 37 48 57 92 –1 –1 12
86 fits in middle, S=5, L=1, so shift 92 right, (t=5).
25 37 48 57 86 92 –1 12
33 fits in middle, S=2, L=5, so shift 12, 25 left (h=7, t=5).
33 37 48 57 86 92 12 25
Input Specification
The input will consist of a single line containing an integer N followed by the N integers to be sorted. All
integers are positive and are separated by a single space. There will be no duplicates among the N integers.
Output Specification
The output should consist of N lines, each line containing N integers. The N integers are the contents of Y[]
(ie. Y[0] to Y[N-1]) after the insertion of each integer from X[]. All integers on a line should be separated by
a single space. N will be less than 50.
Sample Input/Output
Input
8 25 57 37 48 12 92 86 33
Output
25 -1 -1 -1 -1 -1 -1 -1
25 57 -1 -1 -1 -1 -1 -1
25 37 57 -1 -1 -1 -1 -1
25 37 48 57 -1 -1 -1 -1
25 37 48 57 -1 -1 -1 12
25 37 48 57 92 -1 -1 12
25 37 48 57 86 92 -1 12
33 37 48 57 86 92 12 25

Rain strikes and the roads are flooded, Mr X has to get home from work. Your task is to make sure he
returns home in the shortest time.
Consider the roads as a graph with crossings as nodes, and the path between two nodes as an edge. Assume
the graph is undirected and the nodes are numbered, 1 to V (V <= 50).
The input consists of :
1. An integer H on a line, this is the height of Mr X.
2. Two integers N and M on the next line, where, N is the number of edges in the graph. M is the
number of nodes in the graph.
3. A sequence of N lines each having 4 integers : C1 C2 T D where, C1, C2 are the nodes (or
crossings), T is the time it takes to go from C1 to C2. D is the water depth along the edge(or road)
from C1 to C2.
Note: The depth D has to be less than the height of Mr X for him to be able to take the road.
4. Two integers S and E indicating the node at which Mr X starts and where he is expected to go to,
respectively.
As output you have to give the shortest path starting at S, listing each vertex in the order and ending with E
that Mr X can take. Assume that there will be at least one way to reach the destination and that the shortest
path is unique.
Sample Input/Output
Input
5
10 7
1 2 10 4
1 4 6 3
1 5 8 2
2 3 2 1
3 7 1 2
2 6 1 3
4 6 4 4
6 7 2 5
5 4 2 6
5 7 6 1
1 7
Output
1 2 3 7

Consider a hash table of size N, numbered 0 to N-1. You have to insert integers into this table using the
hashing technique given below:
Let i be the integer to be inserted. Compute the index j of the location where the insertion is to be made as j
= i mod N. If this location is empty then put the element at this position else recompute the next location as
follows:
Remove the right most digit of i. Using the new value of i, recompute j = i mod N.
If the digit removed was odd, then move j locations forward from the current location else move j locations
backward from the current location (assume 0 as even). Note that this move will wrap around both the edges
of the table.
Keep doing this till you either find a free location or all the digits of i have been removed. When i comes to
only one digit, and its rightmost digit is removed, the number remaining is zero - therefore, this will lead to a
zero-step move.
If all digits of i have been removed and yet unable to find a free location, from the last location tried, start
moving in the direction corresponding to the last digit removed. Keep moving till you detect a free location.
Assume that the number of integers inserted is not more than the table size.
Input Specification
The first line will contain just one integer. This will give the table size, N. On the next line will be the list of
positive integers that need to be inserted into the table. The integers will be separated by a space each, and
the last integer will be -1 indicating end of input. (-1 is not to be inserted into the table).
Output Specification
The output should contain, for each integer, the locations that were checked while inserting that integer
(including the location in which the integer was finally inserted). The locations checked for each of the
integers should be output on a line by itself, separated by one space each, each line being terminated by a
new line.
Sample Input/Output
Input
7
38 52 145 16 179 4 -1
Output
3
3 5
5 5 4
2
4 0
4 4 3 2 1

hi to all tech brains.
we made an interview round and ask this problem.
problem needs complete solution in java.
Any one of you who can solve it may appreciate and will get some benefits.
In this problem, you have to implement a sorting algorithm called Tournament sort, which uses a complete
binary tree.
The depth D of the tree will be given as input. Also, N positive integers will be given, where N is the Dth
power of 2 (ie, 2 ** D).
Construct a complete binary tree of depth D and fill in the leaf nodes with the N given integers in the order
given ie. the first integer should be at the leftmost leaf and the last integer should be at the rightmost leaf.
Next, update all the non-leaf nodes in the tree such that each nonleaf node contains the maximum of the
values in its children. Thus, the root will contain the maximum of all the N integers.
Implement a procedure ’maxdelete’ which essentially removes the maximum value from the tree and updates
the tree as follows:
1. traverse the tree from the root
2. find the leaf with the maximum value ie. the value at the root. (note that in this tree, if the value at a
non-leaf node is T, either its left child or its right child will have value T).
3. replace the value at that leaf node with -1 and
4. update the rest of the non-leaf nodes such that each non-leaf node contains the maximum of the
values in its children.
Perform the ’maxdelete’ operation 3 times on the tree and print out the INORDER traversal of the tree after
each operation.
Example
Given depth = 2
Given integers: 25 57 37 48
Constructed and updated tree:
57
/ \
57 48
/ \ / \
25 57 37 48

after first 'maxdelete'
48
/ \
25 48
/ \ / \
25 -1 37 48

after second 'maxdelete'
37
/ \
25 37
/ \ / \
25 -1 37 -1

after third 'maxdelete'
25
/ \
25 -1
/ \ / \
25 -1 -1 -1

Input Specification
The input will consist of a positive integer D followed by a positive integer N (where N is the Dth power of
2) followed by N positive integers. All the integers are separated by a single space and will be on a single
line. There will be no duplicates among the N integers. D will be greater than 1 and less than 9.
Output Specification
The output should consist of 3 lines. Each line should contain the INORDER traversal of the tree after a
’maxdelete’ operation. All the integers on a line should be separated by a single space.
Sample Input/Output
Input
2 4 25 57 37 48
Output
25 25 -1 48 37 48 48
25 25 -1 37 37 37 -1
25 25 -1 25 -1 -1 -1

Dr. Alberquert invented the following three devices to set up a simple communication network:
Synthesizer (S), which produces signals continuously and transmits (propagates / passes on) them to neighbouring cells but cannot receive signals.
Receiver (R), which can receive signals from neighbouring signal sources but cannot produce or propagate signal.
Transmitter (T), which is capable of both receiving signal from and transmitting signals to neighbouring cells. Transmitters also are NOT capable of producing signals.
These devices are laid in a matrix formation. Signals are propagated at the rate of one cell per time unit. The absorption rate of a receiver is unlimited and so also the transmission and absorption rate of a transmitter unlimited. For simplicity we shall ignore the exact nature of signals being produced and consider them uniform across sources. Devices on the extreme right side can also communicate with the extreme left hand side device present in the same row (see fig 2). Similarly a device on the extreme top can also communicate with a device at the extreme bottom if they are present in the same column.
Please Note:
Neighbourhood is a four cell neighbourhood, i.e, the neighbourhood of a cell is defined by cells to its NORTH, SOUTH, EAST and WEST (see fig 1).
All Synthesizers will start to produce signals as soon as the simulation begins.
There could be multiple Synthesizers in a matrix arrangement.



Your task is to write a program that would take a matrix containing devices and output the time at which each receiver/transmitter receives its first signal.
Input specification:
The first line has two integers M and N indicating the number of rows and columns of the matrix. 0 < M, N <= 20
M lines follow the first line. Each of these M lines contains N characters and a terminating new line. Each character is one of S, T or R.
Output specification:
The output should be a matrix of M rows with each row containing N integers separated by spaces indicating the minimum time required for the signal to reach the corresponding device. The output for cells containing Synthesizers is 0. For devices that never receive any signal, print -1.
Sample Input and Output:

Input:
3 4
SRTR
TTTT
TTTS


Output:
0 1 3 1
1 2 2 1
1 2 1 0



Input:
2 3
RTT
TTR


Output:
-1 -1 -1
-1 -1 -1

Given a matrix of order M x N containing 1.s and 0's, you have to find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately. Unit squares (length of side = 1) should be also counted.
Note that squares are filled, i.e. they cannot contain 0.s.

Number of maximal square: 6
Input specification:
The first line consists of integers M and N, the number of rows and columns of the matrix.
0 < M and N <=40
Next M lines contain N characters from the set {0, 1}.
Output specification:
An integer representing the number of maximal squares that can be formed followed by a newline.
Sample Input and Output:

Input:
4 5
11001
11110
11011
11001


Output:
9



Input:
2 2
10
11


Output:
3

KingKong, the largest living ape, escaped from Xanadu lab into a forest. The forest is filled with dangerous animals, which will attack and kill human beings that venture too close to them. You are required to help the scientists find a way to get to KingKong safely. The table below gives the minimum distance one must keep from each species for safety.
Animal Name
Code
Safety distance (unit cell)
Lion L 1

Panther P 2

Both, the animals as well as the scientists can move only in horizontal or vertical directions. So, in the figure, the cells shaded gray are the cells into which the scientists must NOT venture, in order to be safe. The arrow shows that the panther is one vertical and one horizontal (a total of two) cell away from it.

A snapshot of the forest is obtained from a satellite picture in terms of an MxN matrix, which is the input to your program. This snapshot gives the location of various animals in the forest. Some cells might contain trees, which merely block the path of the scientists. The cells within the snapshot are marked by:
Animal code indicating the animal present in the cell
'T' in case of a tree present in the cell
'S', which indicates the start position of the scientists
'K', KingKong's location
'#', All other cells, which are empty
The output of your program should be the number of steps in the path that the scientists should take.
Notes:
There will be a unique path, if one exists.
The entire path including the starting position of the scientist as well as KingKong's location must be safe.
Input specification:
The first line contains two integers M and N the number of rows and columns. The next M lines contain N characters from the set {'L', 'P', 'T', 'S', 'K', '#'} as explained above
Output specification:
An integer specifying the length of the path, from the starting position of the scientist, to KingKong's position both inclusive. If KingKong is not reachable safely, then output the integer '-1'.
Sample Input and Output:

Input:
7 6
TLT#PP
LL####
LL#K##
TT##TT
TT#TTT
T###TT
TTTSTT

Output:
7


Input:
11 9
LL#######
L##TTTTT#
LKTTTTTT#
####P#TT#
###PP#TT#
####P#TT#
######TT#
L##T##T##
T##T####S
T####T###
TTTTTTLL#

Output:
-1