## dev

BAN USER- 0of 0 votes

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

- dev in India

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| Report Duplicate | Flag | PURGE

CDAC-ACTS Computer Scientist Java - 0of 0 votes

AnswersConsider 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.

- dev in United States

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| Report Duplicate | Flag | PURGE

Lunatic Server Solutions Software Engineer / Developer - 0of 0 votes

AnswersIn this problem, you have to implement a variation of Insertion Sort as described below.

- dev in United States

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| Report Duplicate | Flag | PURGE

Lunatic Server Solutions Java Developer Data Structures Sorting - 0of 0 votes

AnswersRain strikes and the roads are flooded, Mr X has to get home from work. Your task is to make sure he

- dev in United States

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| Report Duplicate | Flag | PURGE

Lunatic Server Solutions Java Developer Data Structures - 0of 0 votes

AnswerConsider a hash table of size N, numbered 0 to N-1. You have to insert integers into this table using the

- dev in United States

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| Report Duplicate | Flag | PURGE

Lunatic Server Solutions Java Developer Hash Table - 0of 0 votes

Answershi to all tech brains.

- dev in United States

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| Report Duplicate | Flag | PURGE

Lunatic Server Solutions Java Developer Data Structures - 0of 0 votes

AnswerDr. Alberquert invented the following three devices to set up a simple communication network:

- dev in United States

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| Report Duplicate | Flag | PURGE

Java - 0of 0 votes

AnswersGiven 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.

- dev in United States

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| Report Duplicate | Flag | PURGE

Java - 0of 0 votes

AnswerKingKong, 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.

- dev in United States

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| Report Duplicate | Flag | PURGE

Java

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

here t = tail and h= head,

- dev May 27, 2012please read the problem carefull and try to solve it on the paper,

you will get the answer.

it's a quite easy but logical ds problem.

read it carefully.