|
Microsoft Interview Question about Algorithm
Microsoft Interview Questions and Answers
(Continued from previous question...)
7. Microsoft Interview Question about Algorithm
Question:
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
2
maybe an answer:
The idea is if the numbers of a subarray can be arranged in consecutive way that their sum can be evaluated as follows:
max*(max+1)/2 - min*(min-1)/2
where 'max' and 'min' are the maximal and minimal numbers in a subarray.
So the algorithm is go through the array updating 'max' and 'min', as well as the current sum.
In each step we check if computed sum equals to the value returned by the formula above.
If so, we have found a subarray with the given properties.
We keep the longest one seen so far.
Since we have to consider all possible array suffixes, the complexity is O(n^2)
(Continued on next question...)
Other Interview Questions
| 