An interviewer asked me this question:
Given a function f(ar) where ar is an array of integers, this functions claims to sort ar and returns it's sorted version ars. Determine if this function works correctly.
I approached this question as:
- First check if the returned array ars is actually sorted in either non increasing or non decreasing order. This one is easy to check, ars should either follow the sequence ar[i + 1] >= ar[i] (for an array sorted in non decreasing order) or ar[i + 1] <= ar[i] (for an array sorted in non increasing order) for every i in the range [1, n], where n is the size of ars. The time complexity for this should be O(n).
- Then check if sizes of both the input array ar as well as the output array ars are same.
- Finally check if every element of ar is also present in ars. Since we have already examined at step 1 that ars is sorted and at step 2 that sizes of ar and ars are same we can use Binary Search algorithm to perform this action. The worst case time complexity for this should be O(n * log(n)).
If all the above 3 checks succeeds then the function is working fine else it is not. The overall time complexity of this algorithm should O(n * log(n))
But to my surprise the interviewer said that this solution is not correct and it's time complexity can be improved. I can not understand what actually is wrong with my solution, did I miss any corner case or the entire approach is wrong? Also what can be better approach to this(in terms of time complexity)?
PS: The interviewer mentioned no additional information or any additional constraint for this problem.