## Lunatic Server Solutions Interview Question for Java Developers

- 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 May 27, 2012 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

**Country:**United States

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

- sercan November 24, 2014