Lunatic Server Solutions Interview Report
- 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 May 27, 2012 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 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 - 0of 0 votes
AnswersIn this problem, you have to implement a variation of Insertion Sort as described below.
- dev May 27, 2012 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