Interview Question for Software Engineer / Developers
- 1of 1 vote
You are given an unsorted integer array of size N. This array contains integer from range 0 - N (not necessarily distinct and same integer can appear multiple time in an array).- Rajat January 30, 2013 in India
You need to find pair of all the elements in array which sum up to N.
First i gave a solution using an extra array of size N to keep count of each integer in original array and was able to give solution in O(n) Time complexity and O(n) space complexity.
Then interviewer asked me to decrease space complexity, for which i gave solution as sorting the given array (in nlogn time) and then find the pairs in O(n) time, and hence total time complexity was O(nlogn) and space complexity as O(1).
But interviewer kept pressing for a better time complexity (than O(nlogn)) with O(1) space complexity.
How is it possible, i could not think of any way.
| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Arrays
Interview Type: Phone Interview