typedeftemplate's blog

How can I solve this Google Interview Question?
By typedeftemplate, history, 5 years ago, In English

Given an array A = [a1, a2, ..., an] and another array B, where B is some permutation of the numbers 1, 2, ... n, how can I order the elements of A according to the permutation B in-place (so you cannot make an extra array)?

For example, if A = [27, 15, 11, 19] and B = [3, 2, 4, 1], then we would have to modify A to get [19, 15, 27, 1].

This problem seems really easy at first, but I thought it was quite difficult with the memory constraint. I wasn't able to solve this problem, but I was wondering whether someone else would be able to show me how to solve it.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think we can sort array B and apply same operations on A as applied on B while sorting. resulting array A might give you result!!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You need ~4 temporary variables and O(n) time complexity. Read about https://en.wikipedia.org/wiki/Permutation#Cycle_notation

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think qwertyy123321 was onto something, but they didn't fully complete the solution.

The main idea is to sort $$$B$$$ and mirror every operation on $$$A$$$ that we do on $$$B$$$, as itachi0012 said.

One easy way to do this is to use something like std::sort and define our comparator to be based on the elements of $$$B$$$. This is equivalent to assigning pairs of $$$(B_i, A_i)$$$ and calling std::sort on that, which will clearly work. This is $$$O(nlogn)$$$ with $$$O(1)$$$ space because the three algorithms (quicksort, heapsort, and insertion sort) of std::sort, which is introsort under the hood, are all in-place sorting algorithms and use $$$O(1)$$$ memory.

Another way is to factor in the link that bruno.iljazovic posted, which shows that a permutation can be decomposed into a bunch of cycles. A cycle for a permutation $$$P$$$ is essentially starting from any $$$i$$$ and moving to the index $$$P_i$$$ until you eventually return to $$$i$$$, which will happen. We'll treat each cycle separately, and use the following algorithm ($$$1$$$-indexed):

for i = 1 to n:
  while b[i] != i:
    swap(a[i], a[b[i])
    swap(b[i], b[b[i])

This will sort any cycle going through $$$i$$$, because it will essentially traverse the cycle starting at the position right after $$$i$$$ and correct each element one by one until $$$i$$$ is corrected, which will be the last element to be corrected (because $$$i$$$ is the last element in the cycle, according to where we start each time). Since each element gets at most $$$1$$$ correction and we look at each index $$$1$$$ time, the overall complexity is $$$O(n)$$$, with no additional space.

I also quickly wrote a bash to try to verify this solution by checking if it sorted every permutation of $$$0..9$$$ ($$$0$$$-indexed), and it was successful.

→ Reply