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
- sercan November 24, 2014