Directi Interview Question
Software Engineer / DevelopersHOW IN THE WORLD ONE CAN SOLVE THE ABOVE PROBLEM IN O(1) TIME? :P
the above one is the best solution . . ..
the above algorithm works because:
when freq=0, selected number and the other numbers (which may have the right numbers in it) are in equal number, so no harm in neglecting them (we are neglecting at max the number of neglected unwanted numbers), so start over from this point forgetting previous numbers.
if you proceed this way, at some point of time, you'll select right answer, and the other numbers cant outnumber it, because we've lost more of other numbers than the required number in the process above.
there is an alternate solution .
(1) Select pairs of elements i.e 1, 2; 3, 4; 5, 6; ....
(2) compare if elements of pair are equal. If equal keep one element. Else remove that pair. Do this recursively until there is one element left.
ex:
Given array ->
10, 20 , 10, 10, 20, 20, 10, 10
Step 1 : (10, 20) , (10, 10), (20, 20), (10, 10)
Step 2 : (), (10), (20), (10) => 10, 20, 10
Step 3 : (10, 20), 10
Step 4 : (), 10 => 10
Hence 10 is the number.
Let num=1st elt of array...freq=1...then for each elt e remaining if e==num increment freq else decrement..if freq becomes 0 then make num=e and freq as 1...at last num will hold de req number
The above given algorithm lies on the fact that, if a list contains an element that is repeated more than n/2 times in the list, then the required element will be present consecutively atleast once or the list will end with the required element.
Eg: Let's say size of the list is 10
1st possibility:
1,3,2,3,3,4,5,3,6,3 (3 repeated in location 3&4)
OR
1,3,2,3,4,3,5,3,6,3 (List ends with 3)
Super Cool Algorithm, I must say :-)
Let num=1st elt of array...freq=1...then for each elt e remaining if e==num increment freq else decrement..if freq becomes 0 then make num=e and freq as 1...at last num will hold de req number
- Sathya January 19, 2011