|
a linked list contains 2 19 _ _ 3 47 _ _ _ 2 20 _ _......
Microsoft Interview Questions and Answers
(Continued from previous question...)
29. a linked list contains 2 19 _ _ 3 47 _ _ _ 2 20 _ _......
Question:
a linked list contains
2 19 _ _ 3 47 _ _ _ 2 20 _ _ ..............and so on
I have to fill those empty nodes with numbers whose sum is equal to the numbers
occurring just before the gaps and the number of gaps is determined by the node
which is at 2 distance before the gaps with the limitation that there would be no
repetition in list only the nodes designating the number of gaps can be repeated
for example 2 20 should be broken in two parts like 19 1
3 47 should be broken in three parts like 42 2 3
and not in 44 1 2 because 1 already occurred in the list due previous partition
maybe an answer1:
it is better to start with the least number with fewest gaps. for example, 2 5_ _ and 2 10 _ _, start from 2 5 as 5 has only two combinations(e.g. 1, 4 and 2,3) wihle 10 has 5 combinations. For 3 47 _ _ _. it can be consider as one number and two gaps (e.g. 1 and gaps (2 46 _ _)).
maybe an answer2:
sum[i] // assume sum[i] is in increasing order
//assume positive number,
totalGap = sum of gap[i] {i=0,...n-1}
maxSum = maximum of sum[i]
find totalGap of different numbers between 1 and maxSum.
with the limitation that : gap[i] numbers with get sum[i]
we has a flag array hashTab[1..maxSum] to indicate whether the number is taken.
(Continued on next question...)
Other Interview Questions
| 