Lunatic Server Solutions Interview Question for Java Developers
- 0of 0 votes
Consider 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
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
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.
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).
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
38 52 145 16 179 4 -1
5 5 4
4 4 3 2 1
| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Java Developer Hash Table