Given two arrays
a[] = {1,3,2,4}
b[] = {4,2,3,1}
both will have the same numbers but in different order. We have to sort both of them. The condition is that you cannot compare elements within the same array.
-
Does this make sense to anyone?spender– spender2011-09-01 17:17:05 +00:00Commented Sep 1, 2011 at 17:17
-
I don't quite understand. Are you transforming b until it has the same order as a? In which case, aren't you always just returning a?Gian– Gian2011-09-01 17:17:26 +00:00Commented Sep 1, 2011 at 17:17
-
3If the interview questions were like this, I'd pass up the job. Really.spender– spender2011-09-01 17:20:23 +00:00Commented Sep 1, 2011 at 17:20
-
1Come on, this is not the weirdest interview questions at all. Just accept the reality.Mu Qiao– Mu Qiao2011-09-02 09:23:43 +00:00Commented Sep 2, 2011 at 9:23
-
@Mu Qiao - it was weird before it was fixed up by an editor prior to your viewing.hatchet - done with SOverflow– hatchet - done with SOverflow2011-09-02 12:57:50 +00:00Commented Sep 2, 2011 at 12:57
|
Show 2 more comments
2 Answers
I can give you an algorithm of O(N*log(N)) time complexity based on quick sort.
- Randomly select an element a1 in array A
- Use a1 to partition array B, note that you only have to compare every element in array B with a1
- Partitioning returns the position b1. Use b1 to partition array A (the same as step 2)
- Go to step 1 for the partitioned sub-arrays if their length are greater than 1.
Time complexity: T(N) = 2*T(N/2) + O(N). So the overall complexity is O(N*log(N)) according to master theorem.
Comments
Not sure I understood the question properly, but from my understanding the task is a follows:
Sort a given array
awithout comparing any two elements fromadirectly. However we are given a second arraybwhich is guaranteed to contain the same elements asabut in arbitrary order. You are not allowed to modifyb(otherwise just sortband return it...).
In case the elements in a are distinct this is easy: for every element in a count how many elements in b are smaller. This number gives us the (zero based) index in a sorted order.
The case where elements are not necessarily distinct is left to the reader :)
