|
Google Technical Interviews in Management round: You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).
Manager Round interview Questions and Answers
(Continued from previous question...)
Google Technical Interviews in Management round:
You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).
Solution:
All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent.
(Continued on next question...)
Other Interview Questions
| 