## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 7 vote

Built for zero based arrays but can be modified to one based values.
Can't explain why it works... :)

``````public int[] sort(int[] Xs, int[] As) {
for (int i = 0; i < Xs.length; i++) {
int a = As[i];
while(a < i) {
a = As[a];
}

// can be slightly optimized with if(a != i) ...
int x = Xs[i];
Xs[i] = Xs[a];
Xs[a] = x;
}

return Xs;
}
}``````

Comment hidden because of low score. Click to expand.
4

Well, as iroodaz commented (and for some reason deleted) I have implemented
X[i] = X[A[i]] while the question requests X[A[i]] = X[i]
so here is a correction (already written by others here) again for 0 based A's
All the is left, again, is to calculate the complexity :)

``````public static int[] sort2(int[] Xs, int[] As) {
for (int i = 0; i < Xs.length; i++) {
while(As[i] != i) {

int a = As[i];

// swap Xs
int x = Xs[a];
Xs[a] = Xs[i];
Xs[i] = x;

// swap As
As[i] = As[a];
As[a] = a;
}
}

return Xs;
}``````

Comment hidden because of low score. Click to expand.
0

Great job Levitan. I apologize for deleting the comment. I was constantly mixing things when trying test cases and finally got completely lost. After that, concluded that, I'd better not talk as I was starting to talk nonsense :-D
Nevertheless, we now have a superb algorithm for each of the two cases that you mentioned.
Thanks buddy!

Comment hidden because of low score. Click to expand.
0

It's a clever solution and performs at O(n) time complexity, better than the interviewer asks for. But, it wont work when asking to preserve the original permutation. The algorithm above this one can achieve the same performance O(n) without destructing the permutation.

Comment hidden because of low score. Click to expand.
0

It is O(n); however, we should first sort the array normally and then pass it to this method. So, overall, it is O(nlogn).

Comment hidden because of low score. Click to expand.
2

Nice solution. However, consider the worst case when the array, As, is reversed. Say, [100000,99999,....1]. In this case, it seems to me, the double loop of this algorithm degrades into O(n2).

Comment hidden because of low score. Click to expand.
1
of 1 vote

I believe the solution is based on the fact that in[] Xs is already sorted, right?

Comment hidden because of low score. Click to expand.
0

Hey guys, the correct solution is the original one, not the one in the comments and it is indeed O(n). I sincerely apologize to Levitan for posting a misleading comment under his original post. I screwed up terribly. :-( :-( Please please up-vote the original post so the solution gets to be seen. It is a super elegant algorithm and it does not even modify array A.

Thanks!

Comment hidden because of low score. Click to expand.
0

it works because you're first checking where 1 goes in the permutation. then you check where 2 goes. but you only go to an new index farther or equal to the current index. this makes sure you don't double swap. the reason why the while loop always ends is because the iteration a = As[a] will always and come back to i again (in n or less iterations). you're basically iterating through the different cycles in the cycle decomposition of the permutation

Comment hidden because of low score. Click to expand.
3
of 5 vote

There are two things not explained clearly in the problem:
1) Require stable sort or not?
2) Can overwrite the array A or not?

Assume stable sort not requried and A can be overwrote. The solution is:
Step 1: HeapSort(X); [Note: Use Maximum Heap]
Step 2: PermutationReorder(X,A);

Step 1:
HeapSort is satisfied in this problem.
1) Big-O: O(n*log(n)) even in the wrost case.
2) In-space: No extra space required.
3) But not stable. (Assume not required. if required, need to modify HeapSort)
[Note: it is time costly to code the HeapSort in a short time, so be careful]

Step 2:
PermutationReorder:
-------------------------
Step 2.1:
Loop A
A[i] = X[A[i]];

Step 2.2:
Loop X
X[i] = A[i];
------------------------
If A is not allowed to be overwrote. I do not have a solution. I see there are many talking about the "Swap Solution" proposed by Levitan. But I think that solution is wrong. The "Swap Solution" is basically "sorting A", which is not exactly what the problem want.

Comment hidden because of low score. Click to expand.
0

Cool.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

If you try it out, you will find out that the swap and sort solution works. You can think about it. For example the easiest case, we have x = 11, 24, 15, a = 2, 1, 3,
Then you swap a[0] with a[1], you get 24, 11, 15 which is exactly what you want. Certainly, this case is not convencing, but you can try other cases. It should work.

Comment hidden because of low score. Click to expand.
1
of 7 vote

Use quicksort on array a and swap elements of x as you are sorting a.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Quicksort is O(n2) in the worst case. Heapsort is an in-place O(n log n) sort. Maybe that would work.

Comment hidden because of low score. Click to expand.
1
of 5 vote

Can be done in O(n) by employing in-place marker to the index array. The test data with the code below is carefully chosen to cover all cases..

``````public class InPlaceRearrangeViaShadowIndex {

public static void doIt(int[] numbers, int[] index) {
if (numbers == null || index == null || numbers.length != index.length) {
return;
}

// Make index value > zero so we can use negative value to mark visited cells
for (int i = 0; i < index.length; i++) {
++index[i];
}

continue;
}

int goingTo = index[circleHead] - 1;
int temp = numbers[goingTo];
numbers[goingTo] = valueToMove;
valueToMove = temp;
temp = index[goingTo] - 1;
index[goingTo] = -index[goingTo];
goingTo = temp;
}
}

// Restore index array if disallowing the index array to be destructed
for (int i = 0; i < index.length; i++) {
index[i] = Math.abs(index[i]) - 1;
}

}

public static void main(String[] args) {
int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
int[] index = { 3, 6, 2, 9, 7, 1, 4, 8, 5, 0 };
System.out.println("Values: " + Arrays.toString(arr));
System.out.println(" Index: " + Arrays.toString(index));
doIt(arr, index);
System.out.println("Values: " + Arrays.toString(arr));
}
}``````

Result:
Values: [5, 12, 14, 27, 3, 2, 13, 17, 7, 21]
Index: [3, 6, 2, 9, 7, 1, 4, 8, 5, 0]
Values: [21, 2, 14, 5, 13, 7, 12, 3, 17, 27]

Comment hidden because of low score. Click to expand.
0

Correction: since the original question already states index are > 0, the above code should be modified as below:

``````public class InPlaceRearrangeViaShadowIndex {

public static void doIt(int[] numbers, int[] index) {
if (numbers == null || index == null || numbers.length != index.length) {
return;
}

continue;
}

int goingTo = index[circleHead] - 1;
int temp = numbers[goingTo];
numbers[goingTo] = valueToMove;
valueToMove = temp;
temp = index[goingTo] - 1;
index[goingTo] = -index[goingTo];
goingTo = temp;
}
}

// Restore index array if disallowing the index array to be destructed
for (int i = 0; i < index.length; i++) {
index[i] = Math.abs(index[i]);
}

}

public static void main(String[] args) {
int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
int[] index = { 4, 7, 3, 10, 8, 2, 5, 9, 6, 1 };
System.out.println("Values: " + Arrays.toString(arr));
System.out.println(" Index: " + Arrays.toString(index));
doIt(arr, index);
System.out.println("Values: " + Arrays.toString(arr));
}
}``````

Values: [5, 12, 14, 27, 3, 2, 13, 17, 7, 21]
Index: [4, 7, 3, 10, 8, 2, 5, 9, 6, 1]
Values: [21, 2, 14, 5, 13, 7, 12, 3, 17, 27]

Comment hidden because of low score. Click to expand.
0

The code is correct. How to prove that the complexity is o(nlgn)?

Comment hidden because of low score. Click to expand.
0

@chenw, actually the time complexity is not O(nlgn), but O(n) since at worst case (where no element happens to be in right place initially) , every element is relocated once.

Comment hidden because of low score. Click to expand.
0

I think the expected output for your test case is:
[7, 14, 5, 27, 17, 3, 12, 21, 13, 2]

Even if I sort your array before calling your function, I still get something that looks inverted.

Comment hidden because of low score. Click to expand.
0

@Anonymous, can you explain how you arrive your result? Using 7, the first element in your result, as example, it originally resides at cell 8 and is to be relocated to 5 (6 - 1). And, why you have to sort the array first?

Comment hidden because of low score. Click to expand.
0

Just wondering why a Google interviewer ask for O(nlogn) solution when there exists o(n) one.

Comment hidden because of low score. Click to expand.
0

If not forbidding destruction the permutation, this in-place marker solution can be further improved as below. Instead of using negative index value to mark a cell happening to be in the right location, mark a processed cell as such. It simplifies the logic and operation a bit, while still maintaining the O(n) performance.

``````public class InPlaceRearrangeViaShadowIndex {

public static void doIt(int[] numbers, int[] index) {
if (numbers == null || index == null || numbers.length != index.length) {
return;
}

// Check if it is already in right position
int goingTo = index[loopHead] - 1;
int temp = numbers[goingTo];
numbers[goingTo] = valueToMove;
valueToMove = temp;
temp = index[goingTo] - 1;
// Mark it as already in right position
index[goingTo] = goingTo + 1;
goingTo = temp;
}
}
}
}

public static void main(String[] args) {
int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
int[] index = { 4, 7, 3, 10, 8, 2, 5, 9, 6, 1 };
System.out.println("Values: " + Arrays.toString(arr));
System.out.println(" Index: " + Arrays.toString(index));
doIt(arr, index);
System.out.println("Values: " + Arrays.toString(arr));
}
}``````

Values: [5, 12, 14, 27, 3, 2, 13, 17, 7, 21]
Index: [4, 7, 3, 10, 8, 2, 5, 9, 6, 1]
Values: [21, 2, 14, 5, 13, 7, 12, 3, 17, 27]

Comment hidden because of low score. Click to expand.
4

Sorry but he's *NOT* solving the right problem. Values given in the index array is the order *after* sorted and not the order in the values array. Just think. If this was solvable in O(N), you would sort N elements in O(N) by passing index=[1,2,3,4...]... and might win a Fields medal !!

Comment hidden because of low score. Click to expand.
1
of 1 vote

To anyone who knows the exact specifications of the problem:
Are we allowed to modify contents of the array A?
Thanks :-)

Comment hidden because of low score. Click to expand.
2

That's what I thought at first, because the problem definition didn't mention it otherwise. However, if the content of array A is modifiable then there is a O(n) solution:

``````int* permutation_sort(int *X, int* A, size_t size) {
for (int i=0; i < size; i++) {
// Note that values in A have offset 1, not 0
int index = A[i] - 1;
A[i] = X[temp];
}

return A;
}``````

Comment hidden because of low score. Click to expand.
0

Exactly! However, do not forget O(nlogn) normal sorting that should be done before calling this function. By the way, could you please correct the part that says A[i] = X[temp]?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void alignArrays(ArrayList x, ArrayList p)
{
if (x.length != p.length)
return;
x.sort(); // log n
int end = p.length-1;
for(int i = 0; i < end; i++, end--) // n
{
int temp = x[p[i]];
x[p[i]] = x[p[end]];
x[p[end]] = temp;
}
}``````

Comment hidden because of low score. Click to expand.
0

this doesn't work. try:

``````int[] x = {10, 13, 1, 2};
int[] p = {2, 1, 3, 0};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in o(n). You just have to recursively put each number in its correct position.

Comment hidden because of low score. Click to expand.
0

How do you do this in place? Each time you 'put a number in its correct position' you are overwriting a number you will need later on.

Comment hidden because of low score. Click to expand.
0

My first instinct was recursive as well -
I just submitted a solution that works like this.
The key is to 'remember' the values you need before making the recursive call. That way you dont have to worry about the values changing later, and when the recursion bubbles back up, you just set the value you were remembering in to its correct location.. (assuming my code does in fact work ;) )

Comment hidden because of low score. Click to expand.
0
of 0 vote

quick sort..............................

Comment hidden because of low score. Click to expand.
0
of 0 vote

Treat the permutation array [a1~an] as as node index of min-heap, (and sequence array [x1~xn] are node value).

It was O(nlogn) to build such min-heap, and we can achieve that by "swap" elements in array, no extra array required.

Comment hidden because of low score. Click to expand.
0

If not forbidding destruction the permutation, this in-place marker solution can be further improved as below. Instead of using negative index value to mark a processed cell, mark a processed cell as such. It simplifies the logic and operation a bit, while still maintaining the O(n) performance.

public static void doIt(int[] numbers, int[] index) {
if (numbers == null || index == null || numbers.length != index.length) {
return;
}

// Check if it is already in right position
int goingTo = index[loopHead] - 1;
int temp = numbers[goingTo];
numbers[goingTo] = valueToMove;
valueToMove = temp;
temp = index[goingTo] - 1;
// Mark it as already in right position
index[goingTo] = goingTo + 1;
goingTo = temp;
}
}
}
}

public static void main(String[] args) {
int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
int[] index = { 4, 7, 3, 10, 8, 2, 5, 9, 6, 1 };
System.out.println("Values: " + Arrays.toString(arr));
System.out.println(" Index: " + Arrays.toString(index));
doIt(arr, index);
System.out.println("Values: " + Arrays.toString(arr));
}
}
Values: [5, 12, 14, 27, 3, 2, 13, 17, 7, 21]
Index: [4, 7, 3, 10, 8, 2, 5, 9, 6, 1]
Values: [21, 2, 14, 5, 13, 7, 12, 3, 17, 27]

Comment hidden because of low score. Click to expand.
0
of 0 vote

The basic idea is:
1. Sort X.
2. Assume we're going to make 1,2,3,4,......,n sequence become a[1], a[2].......a[n]. we swap x[] as we swap a[]. For example, if a[1] = 3, we swap 1 and 3 to make 3 at a[1]. At the same time, we swap x[1] with x[3] and so on.

``````void solve(int x[], int xlen, int a[], int alen){
if(xlen != alen || 0 == xlen){
return;
}
sort(x, xlen);

for(int i=1; i<alen; i++){
if(a[i] != i){
swap(x, a[i], i);
}
}
}

void swap(int array[], int a, int b)
{
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}

void sort(int array[], int arrayLength)
{
//some sort implementation
}``````

Comment hidden because of low score. Click to expand.
0

This would not work unfortunately. Consider the following test case:

A = {2, 1, 3}
X = {1, 2, 3}

sort(X) => X = {1, 2, 3}
first iteration of the for-loop: X = {2, 1, 3}
second iteration: X = {1, 2, 3}
third iteration: X = {1, 2, 3}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Thanks for checking out my code.
I didn't notice that I need to keep tracking the status of the index array.
Correct the previous solution as below:

``````void solve(int x[], int xlen, int a[], int alen){
if(xlen != alen || 0 == xlen){
return;
}
sort(x, xlen);

// Add an array b[1 ~ alen] which b[1] = 1, b[2] = 2, ......b[alen] = alen
int b[alen];
for(int i=0; i<alen; i++){
b[i] = i;
}

for(int i=1; i<alen; i++){
// use b array to track the index changing status
if(b[i] != a[i]){
swap(b, a[i], i);
swap(x, a[i], i);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Thanks for the new code. :-)

I believe this one is correct.

However, the algorithm should not use any additional arrays, so we should do something about array b. The good news is, we can do what the array b does using the original array a.

Cheers!

Comment hidden because of low score. Click to expand.
0

I can't figure out how to use the original array a to solve the problem.
Could you explain more?

Comment hidden because of low score. Click to expand.
1
of 1 vote

We can do something like what oOZz has done. Putting permuted X in array A and destroying A as we go forward. Also check Levitan's original code(not the one in comments) to see how he does not even modify A and solve this. It is super cool.

Comment hidden because of low score. Click to expand.
0
of 0 vote

C#, NUnit

``````// Algorithm:
// 1. Get item and check if it is in right position
// 2. If so move to next item
// 3. Else, start to swap items sequentially, until find item in the right position
// O(n)
public static void Permutation(int[] x, int[] a)
{
for (var i = 0; i < a.Length; i++)
{
var ind = a[i] - 1;
var val = x[i];
while (a[ind] - 1 != ind)
{
var tmpInd = a[ind] - 1;
var tmpVal = x[ind];
x[ind] = val;
a[ind] = ind + 1;
ind = tmpInd;
val = tmpVal;
}
}
}

[Test]
public static void PermutationTest()
{
var x = new[] {17, 5, 1, 9};
var a = new[] {3, 2, 4, 1};
Permutation(x, a);
Assert.AreEqual(new int[]{9, 5, 17, 1}, x);

x = new int[] { 10, 15, 20, 25, 30 };
a = new int[] { 1, 2, 3, 4, 5 };
Permutation(x, a);
Assert.AreEqual(new int[] { 10, 15, 20, 25, 30 }, x);

x = new int[] { 10, 15, 20, 25 };
a = new int[] { 4, 3, 2, 1 };
Permutation(x, a);
Assert.AreEqual(new int[] { 25, 20, 15, 10 }, x);

x = new int[] {10, 15, 20, 25, 30};
a = new int[] {5, 4, 3, 2, 1};
Permutation(x, a);
Assert.AreEqual(new int[] { 30, 25, 20, 15, 10 }, x);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach would be to use heapsort and mirror the changes. Heapsort is in-place and O(n log n).

``````public class HeapSorter2 extends Heapsorter {

protected int[] _mirrorArray

public HeapSorter2(int[] arr, int[] mirrorArray) {
_mirrorArray = mirrorArray;
super(arr);
}

@Override
protected void swap(int a, int b) {

// the regular swap (all changes to array made here)
int temp = _arr[a];
_arr[a] = _arr[b];
_arr[b] = temp;

// the mirror array swap (will mirror all array changes)
temp = _mirrorArray[a];
_mirrorArray[a] = _mirrorArray[b];
_mirrorArray[b] = temp;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

O(n) simple solution:

``````int count = 0;
int curr = a[0];
int previous = 0;

while(count != n){

temp = x[curr];
x[curr] = x[previous];
previous = curr;
curr = a[curr];
count++;
}``````

Comment hidden because of low score. Click to expand.
0

It doesn't work
for x = { 17, 5, 1, 9 }
and a = { 2, 1, 3, 0 }
it return {17, 5, 17, 17}, but must return { 9, 5, 17, 1 }

Comment hidden because of low score. Click to expand.
0
of 0 vote

first, use quick sort in place to sort the array, then do reorder according to the second sequence.

``````void swap2(int& a, int& b)
{
if (&a == &b)
return;
a ^= b;
b ^= a;
a ^= b;
}

void reorder(int* arr, int* order, int size)
{
for (int i = 0; i < size; ++i)
{
if (order[i] > i)
{
// swap arr[i] and arr[order[i]]
swap2((arr[i]), (arr[order[i]]));
continue;
}

if (order[i] == i)
continue;

int k = order[i];
while (k < i)
{
k = order[k];
}

swap2(arr[k], arr[i]);
}
}``````

You need to sort the array first.

Comment hidden because of low score. Click to expand.
0
of 0 vote

What do we need to change on @babula code if we do not want to use an additional memory?

Comment hidden because of low score. Click to expand.
0
of 0 vote

p = {x1,x2,...xn} ;
a = {a1,a2,...an};

sort(p); //O(nlogn)

// O(n)
for (int i = 0; i < p.size(); i++) {
a[i] = p[a[i]-1];
}
// O(n)
for(int i = 0; i < a.size(); i++) {
p[i] = a[i];
}

Comment hidden because of low score. Click to expand.
0

Clever. The problem is

``a[i] = p[a[i]-1];``

Which will over write values in 'a' that you'll need in subsequent iterations of that very loop.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use A={a1,a2,a3..} for comparison and swap X.

``````#include <iostream>
using namespace std;

int Partition(int* X, int* A,int start, int end) {
int pivot = A[end];
int pIndex = start;
for(int i = start; i < end; i++) {
if (A[i] <= pivot){
swap(A[i],A[pIndex]);
swap(X[i],X[pIndex]);
pIndex++;
}
}
swap(A[pIndex],A[end]);
swap(X[pIndex],X[end]);
return pIndex;
}

void QuickSort(int*X, int* A, int start, int end) {
if (start < end) {
int pIndex = Partition(X,A,start,end);
QuickSort(X,A,start,pIndex-1);
QuickSort(X,A,pIndex+1,end);
}
}
int main(int argc, char**argv){
int X[] = {17,5,1,9,8};
int A[] = {3,2,4,1,5};
QuickSort(X,A,0,4);
for(int i = 0; i < 5; i++) cout << X[i] << " ";
cout  << "\n";
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tricky swap, utilize A to preserve sorted X:

``````X = [17, 5, 1, 9]
A = [3, 2, 4, 1]

X.sort()

for i, j in enumerate(A):
if j < i:
x = A[j - 1]
else:
x = X[j - 1]
A[i], X[i] = X[i], x``````

Comment hidden because of low score. Click to expand.
0

Whoops... if j - 1 < i not if j < i:

``````X = [17, 5, 1, 9]
A = [3, 2, 4, 1]

X.sort()

for i, j in enumerate(A):
if j - 1 < i:
x = A[j - 1]
else:
x = X[j - 1]
A[i], X[i] = X[i], x``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// here's o(n log n) using heap sort.

public static void orderElements(int [] valueArray,int[] indexArray){
buildheap(valueArray,indexArray);
int n = indexArray.length-1;
for(int i= n ;i>0;i--){
swap(indexArray,0, i);
swap(valueArray,0, i);
n=n-1;
maxheap(valueArray, indexArray, 0,n);
}
}
private static void swap(int[] array, int i, int j) {
if (i == j)
return;
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}

public static void buildheap(int[] valueArray,int[] indexArray) {
int n = indexArray.length - 1;
for (int i = n / 2; i >= 0; i--) {
maxheap(valueArray,indexArray, i,n);
}
}

public static void maxheap(int[] valueArray,int []indexArray, int i, int n) {
int largest;
int left = 2 * i;
int right = 2 * i + 1;
if (left <= n && indexArray[left] > indexArray[i]) {
largest = left;
} else {
largest = i;
}

if (right <= n && indexArray[right] > indexArray[largest]) {
largest = right;
}
if (largest != i) {
swap(indexArray,i, largest);
swap(valueArray,i, largest);
maxheap(valueArray,indexArray, largest,n);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static inline void _swap(int A[], int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}

void solution(int X[], int A[], int N) {
for (int i = 0; i < N-1; ++i) {
while (i != A[i] - 1) {
_swap(X, i, A[i]-1);
_swap(A, i, A[i]-1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.google.practice;

public class SortOnPerm {
public static void main(String[] arg){
int[] x = {0,3,7,15,2,8};//{0,17,5,1,9};
int[] a = {0,4,2,3,1,5};//{0,3,2,4,1};

mergeSort(a,x,1,a.length-1);
for(int i=1;i<x.length;i++)
System.out.print(x[i]+" ");
}

public static void mergeSort(int[] a,int[] x,int low,int high){
if(low>=high)
return;
int mid = (low+high)/2;
mergeSort(a,x,low,mid);
mergeSort(a,x,mid+1,high);
merge(a,x,low,mid,high);
}

public static void merge(int[] a,int[] x,int low,int mid ,int high){
for(int i=low,j=mid+1;i<=high&&j<=high;j++){
if(i<=high && j<=high){
if(a[j]<a[i]){
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
tmp = a[i];
a[i] =a[j];
a[j] = tmp;
i++;j--;
}
}
}
}
}``````

Merge Sort, without helper array for merge. O(n log n)

Comment hidden because of low score. Click to expand.
0

This is not right by the input
int[] x = {0,3,5,1,4,2};
int[] a = {0,4,2,3,1,5};
it outputs 4 5 1 3 2,

Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap (int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

void change_seq (int a[], int b[], int size) {
for (int i=1 ;i<=size; ) {
int j = i;
while (b[j-1] != j) {
int temp = a[j-1];
swap(a[j-1], a[b[j-1]-1]);
swap(b[j-1], b[b[j-1]-1]);
}
i++;
}
}

int main() {
int a[] = {2,19, 99,88,0,6};
int b[] = {2,3, 4, 1,6,5};
change_seq(a, b, 6);
for (int i=0; i<6; i++)
cout << a[i] <<endl;
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution

``````void swap (int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

void change_seq (int a[], int b[], int size) {
for (int i=1 ;i<=size; ) {
int j = i;
while (b[j-1] != j) {
int temp = a[j-1];
swap(a[j-1], a[b[j-1]-1]);
swap(b[j-1], b[b[j-1]-1]);
}
i++;
}
}

int main() {
int a[] = {2,19, 99,88,0,6};
int b[] = {2,3,  4,  1,6,5};
change_seq(a, b, 6);
for (int i=0; i<6; i++)
cout << a[i] <<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

This looks like O(n2) when b[] is reversed (worst case).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void PermuteOrder(int *a, int *x, int len)
{
if (a == NULL || len == 0)
return;

for (int i = 0; i < len; ++i)
{
if (a[i] == -1 || a[i] - 1 == i)
continue;

int tempOld = x[i];
while (a[i] != -1)
{
int temp = x[a[i] - 1];
x[a[i] - 1] = tempOld;
tempOld = temp;
int oldI = i;
i = a[i] - 1;
a[oldI] = -1;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void PermuteOrder(int *a, int *x, int len)
{
if (a == NULL || len == 0)
return;

for (int i = 0; i < len; ++i)
{
if (a[i] == -1 || a[i] - 1 == i)
continue;

int tempOld = x[i];
while (a[i] != -1)
{
int temp = x[a[i] - 1];
x[a[i] - 1] = tempOld;
tempOld = temp;
int oldI = i;
i = a[i] - 1;
a[oldI] = -1;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

This solution is in Java and its time complexity is O(n).

package arrays;

public class arrangement {

public static void main(String[] args) {

int a_arr[] = {30,40,10,20,70,50,60,100,80,90};
int b_arr[] = {3,4,1,2,7,5,6,10,8,9};
int n = 0;
int curr = a_arr[0];
int loc = b_arr[0];
int temp_curr,temp_loc;
while(n < a_arr.length)
{ n++;
System.out.println("Iteration :" + n);
System.out.println("Curr :" + curr);
System.out.println("Location :" + loc);

temp_curr = a_arr[loc-1];
temp_loc = b_arr[loc-1];
if(temp_curr == curr && temp_loc == loc)
{
n--;
curr = a_arr[loc];
loc = b_arr[loc];
continue;
}
a_arr[loc-1] = curr;
b_arr[loc-1] = loc;
curr = temp_curr;
loc = temp_loc;

}

System.out.println("After completion");

for(int i = 0; i < a_arr.length;i++)
{
System.out.println("i : " + i);
System.out.println("a[i] : " + a_arr[i]);
System.out.println("b[i] : " + b_arr[i]);
}

}

}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
This solution complexity is O(n).

package arrays;

public class arrangement {

public static void main(String[] args) {

int a_arr[] = {30,40,10,20,70,50,60,100,80,90};
int b_arr[] = {3,4,1,2,7,5,6,10,8,9};
int n = 0;
int curr = a_arr[0];
int loc = b_arr[0];
int temp_curr,temp_loc;
while(n < a_arr.length)
{ n++;
System.out.println("Iteration :" + n);
System.out.println("Curr :" + curr);
System.out.println("Location :" + loc);

temp_curr = a_arr[loc-1];
temp_loc = b_arr[loc-1];
if(temp_curr == curr && temp_loc == loc)
{
n--;
curr = a_arr[loc];
loc = b_arr[loc];
continue;
}
a_arr[loc-1] = curr;
b_arr[loc-1] = loc;
curr = temp_curr;
loc = temp_loc;

}

System.out.println("After completion");

for(int i = 0; i < a_arr.length;i++)
{
System.out.println("i : " + i);
System.out.println("a[i] : " + a_arr[i]);
System.out.println("b[i] : " + b_arr[i]);
}

}

}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

for (int i=0; i<x.length; i++) {
x[i] = x[i] * / ( 10 ^ num of digits in x[i])
x[i] = x[i] + a[i]
}

Now use any O (n . log n) algorithm to sort the x

for (int i=0; i<x.length; i++) {
x[i] = x[i] - a[i]
x[i] = x[i] * ( 10 ^ num of digits in x[i] except zero)
}

we are done!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````for(int i=0; i < inp.length;i++)
{
if(ord[i] > 0 && ord[i]!=i)
{
int curr=inp[i],currOrd=ord[i]-1,currIndex=i;

while(currOrd>= 0)
{
int temp=inp[currOrd];
inp[currOrd]=curr;
curr=temp;
ord[currIndex]*=-1;
currIndex=currOrd;
currOrd=ord[currIndex]-1;

}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

With a little trick, this problem can be easily solved in O(n) time complexity. Below is the code:

``````int main()
{
int x[] = {17, 5, 1,9};
int a[] = {3, 2, 4, 1};
int n = sizeof(x)/sizeof(x[0]);
// output: x = {9, 5, 17, 1}

// first, find the maximum element of x
int maxX = x[0];
for(int i = 1; i < n; i++)
maxX = max(maxX, x[i]);

// C is a constant larger than all elements of x
int C = maxX+1;

// convert each element of x, x[dest] = x[dest] + x[i]*C
// where dest is the index where x[i] should be placed
// so for each index j, x[j]/C will give you new x[j]
// and x[j]%C will give you old x[j]
for(int i = 0; i < n; i++)
{
int dest = a[i]-1; // destination of x[i]
x[dest] += (x[i]%C)*C; // %C because x[i] may be modified already
}

// finally get all the new values
for(int i = 0; i < n; i++)
{
x[i] = x[i]/C;
printf("%d\t", x[i]);
}
printf("\n");

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Nice solution !! can you please explain why the modulo operator is needed?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
using namespace std;
struct node
{
int a;
int b;
};
bool check(struct node s1,struct node s2)
{

return (s1.b<=s2.b);

}
int main()
{
int n;
scanf("%d",&n);
struct node p[10000];

for(int i=0;i<n;i++)
cin>>p[i].a;
for(int i=0;i<n;i++)
cin>>p[i].b;

sort(p,p+n,check);

for(int i=0;i<n;i++)
cout<<p[i].a;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple O(n) solution:

``````static void SortArrayByLoc()
{
int[] array = new int[]{17, 5, 1, 9};
int[] locations = new int[] { 3, 1, 2, 4};

for (int i = 0; i < locations.Length; i++ )
{
int index = locations[i] - 1;

// Swapping the values
int temp = array[index];
array[index] = array[i];
array[i] = temp;

// Swapping the locations
temp = locations[index];
locations[index] = locations[i];
locations[i] = temp;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void arrangeArray()
{
int [] arr = {17, 5, 1,9};
int [] dup = {2, 1, 3, 0};
int n = dup.length;
for (int i =0;i<dup.length;i++) {
dup[i] += (dup[dup[i]]%n)*n;
}

for (int i =0;i<dup.length;i++) {
dup[i] = dup[i]/n;
}

for (int j=0;j<dup.length;j++) {
dup[j] = arr[dup[j]];
}

for (int j=0;j<dup.length;j++) {
arr[j] = dup[j];
}
for (int i =0;i<arr.length;i++) {
System.out.print(arr[i]+"");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void arrange()
{
int [] arr = {17, 5, 1,9};
int [] dup = {2, 1, 3, 0};
int n = dup.length;
for (int i =0;i<dup.length;i++) {
dup[i] += (dup[dup[i]]%n)*n;
}

for (int i =0;i<dup.length;i++) {
dup[i] = dup[i]/n;
}

for (int j=0;j<dup.length;j++) {
dup[j] = arr[dup[j]];
}

for (int j=0;j<dup.length;j++) {
arr[j] = dup[j];
}
for (int i =0;i<arr.length;i++) {
System.out.print(arr[i]+"");
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class ArrangeInCustomOrder {

/**
* target order provided in the form which indicates the index of sorted(a[i]) that occurs at a particular position
* would be nice if targetOrder[i] indicated where sorted(a)[i] should go to
*/
static void rearrange(int a[] , int targetOrder[]){
invertPermutation(targetOrder);
Arrays.sort(a);

for(int i = 0; i < a.length; i++){
if(targetOrder[i] > 0){
int targetLocation = targetOrder[i]-1;
// flip signs to track which positions are already processed
targetOrder[i] = 0-targetOrder[i];
if(targetLocation != i){
int temp = a[targetLocation];
int locationOfHole = i;
a[targetLocation] = a[i];

int j = targetLocation;
int elementAtJOriginal = temp;
//System.out.println((j+1) + "\t" + Arrays.toString(a) + "\t" + elementAtJOriginal);

boolean done = false;
while(!done){
int targetLocationPrev = targetLocation;
targetLocation = targetOrder[j]-1;
targetOrder[j] = 0-targetOrder[j];

if(targetLocationPrev == locationOfHole){
done = true;
} else{
int temp2 = a[targetLocation];
a[targetLocation] = elementAtJOriginal;

j = targetLocation;
elementAtJOriginal = temp2;

//System.out.println((j+1) + "\t" + Arrays.toString(a) + "\t" + elementAtJOriginal);
}
}
}
}
}

for(int i = 0; i < a.length; i++){
if(targetOrder[i] < 0)
targetOrder[i] = 0-targetOrder[i];
}

invertPermutation(targetOrder);
}

/**
* example input: 3 , 2 , 4 , 1
* output: 4 , 2 , 1 , 3
*/
static void invertPermutation(int ordering[]){
for(int i = 0; i < ordering.length; i++){
if(ordering[i] > 0){
int elementAtIOriginal = ordering[i]-1;
// flip signs to track which positions are already processed
ordering[i] = 0-ordering[i];
if(elementAtIOriginal != i){
int temp = ordering[elementAtIOriginal];
int locationOfHole = i;
ordering[elementAtIOriginal] = i+1;
int j = elementAtIOriginal;
int elementAtJOriginal = temp-1;
boolean done = false;

//System.out.println((j+1) + "\t" + Arrays.toString(ordering) + "\t" + (elementAtJOriginal+1));

while(!done){
ordering[elementAtIOriginal] = 0-ordering[elementAtIOriginal];

if(elementAtIOriginal == locationOfHole){
done = true;
} else{
int temp2 = ordering[elementAtJOriginal];
ordering[elementAtJOriginal] = j+1;

elementAtIOriginal = elementAtJOriginal;
elementAtJOriginal = temp2-1;
j = elementAtIOriginal;
//locationOfHole = elementAtIOriginal;
}

//System.out.println((j+1) + "\t" + Arrays.toString(ordering) + "\t" + (elementAtJOriginal+1));

}
}
}
}

for(int i = 0; i < ordering.length; i++){
if(ordering[i] < 0)
ordering[i] = 0-ordering[i];
}
}

public static void main(String[] args){
int customOrdering[] = { 3 , 2 , 4 , 1 };

System.out.println(Arrays.toString(customOrdering));
invertPermutation(customOrdering);
System.out.println(Arrays.toString(customOrdering));
invertPermutation(customOrdering);
System.out.println(Arrays.toString(customOrdering));

int a[] = { 17, 5 , 1 , 9};
System.out.println(Arrays.toString(a));
rearrange(a,customOrdering);
System.out.println(Arrays.toString(a));
}

}

// was not easily solvable in 45 minutes / 1 hour``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:

1)Assumption is a will contain the numbers less than length of array. So we can first do minus one from each element for ease of writing the algo.

2) change a[a[i]%n] = x[i]*n + a[a[i]%n]
3) Then x[i] = a[i]/n
4) Restore a, by a[i] = a[i]%n;

code:

``````public static void converArray(int[] x, int[] a)
{
int n = x.length;

for (int i = 0; i < n; i++)
{
System.out.println("i: "+(a[i] % n));
a[a[i] % n] = x[i]*n + a[a[i] % n];
}

for (int i = 0; i < n; i++)
{
x[i] = a[i] / n;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple recursive solution that does not modify the ordering array, and runs in O(n)
I borrowed some test case arrays from other answers, i hope that is ok:

``````import java.util.Arrays;

public class ImposedSort {

public static void main(String[] args) {

int[] input = {17,5,1,9};
int[] order = {3,2,4,1};
// int[] input = {30,40,10,20,70,50,60,100,80,90};
// int[] order = {3,4,1,2,7,5,6,10,8,9};
//int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
//int[] index = { 4, 7, 3, 10, 8, 2, 5, 9, 6, 1 };

System.out.println("Unsorted Input: "+ Arrays.toString(input));
System.out.println("Ordering:       "+ Arrays.toString(order));
recursiveImposedSort(input, order, 0);
System.out.println("Sorted Input:   "+ Arrays.toString(input));
System.out.println("Ordering:       "+ Arrays.toString(order));

}

static void recursiveImposedSort(int[] input, int[] order, int k){
if ( k==input.length){
return;
}
int orderK = order[k];
int inputK = input[k];

recursiveImposedSort(input, order, k + 1);

input[orderK-1]=inputK;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's an O(n.log(n)) solution. Sort x[] (which can be done in n.log(n)), then for each a[], do a binary search in x[] and swap (n * log(n)). I think this is what the interviewer wanted. Tho, there are better solutions to this like O(n) but that will require additional space complexity (e.g. by indexing a[] first then traversing and swapping elements in x[]).

``````public static void main(String[] args) {
int[] a = new int[] {5,4,3,2,1};
int[] x = new int[] {1,5,1,17,4};

putInOrder(a, x);
System.out.println(Arrays.toString(x));
}

static void putInOrder(int[] a, int[] b) {
// extreme value checks

Arrays.sort(b);

for (int i = 0; i < a.length; i++) {
int j = findPos(a[i], b);
// check if i is too big

if (j != -1 && i != j) {
int swap = b[i];
b[i] = b[j];
b[j] = swap;
}
}
}

private static int findPos(int num, int[] array) {
int low = 0, hi = array.length - 1;
while (low <= hi) {
int mid = (low + hi) / 2;
if (num == array[mid]) {
return mid;
} else if (array[mid] > num) {
hi = mid-1;
} else {
low = mid+1;
}
}

return -1;
}``````

Comment hidden because of low score. Click to expand.
0

Note: this handles duplicate integers in x[]. Also, the comments are todos for additional error checking

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Sort the number array - n log n
2. Do this:

``````for(int i=0; i < indexArr.length; i++) {
indexArr[i] = numberArray[indexArr[i]];
}
return indexArr;``````

So n log n + n = n log n if I am not wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution has a big O of (n*logn). Where Arrays.sort has a big O of n*logn and swapping the array values has a big O of (n). Since the solution is O( (n*logn) + n), it is reduce to (n*logn).

Note: Arrays.sort is java built in Merge sort.

``````import java.util.Arrays;
public static void rearrangeArray( int [] arrayA, int [] newIndexOrder){

Arrays.sort(arrayA ); //O (n*log n)

for (int i= 0; i < arrayA.length-1;i++ ){

int tempValue= arrayA[i];
arrayA[i]= arrayA [newIndexOrder[i]-1];
arrayA [newIndexOrder[i]-1]=tempValue;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This a O(n) C++ code with no extra space. The idea is to keep swapping both x & a based on the indices of a untill a is sorted. In the while loop we only visit each index once, hence is loops n times at the worst case.

void sort_with_aSeq(int a[], int x[], int n)
{
int ia = 0;
while(true){
int ai = a[ia];
swap(a[ai-1], a[ia]);
swap(x[ai-1], x[ia]);

while(a[ia] == ia+1)
ia++;
if(ia == n)
break;
}
}
void swap(int &a, int &b){
int tmp = a;
a = b;
b = tmp;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortAccordingToAnArray {
public static void main(String[] args) {
int[] arr = { 5, 12, 14, 27, 3, 2, 13, 17, 7, 21 };
int[] index = { 3, 6, 2, 9, 7, 1, 4, 8, 5, 10 };
System.out.println("Values: " + Arrays.toString(arr));
System.out.println(" Index: " + Arrays.toString(index));
putRightPosition(arr, index);
System.out.println("Values: " + Arrays.toString(arr));
}

public static void putRightPosition(int[] num, int[] seq){
for(int i=0;i
if(seq[i]<0){
continue;
}
int curr_value = num[i];
int next_pos = seq[i]-1;
seq[i] = -seq[i];
while(true){
int tmp = num[next_pos];
num[next_pos] = curr_value;
curr_value = tmp;
tmp = next_pos;
next_pos = seq[next_pos]-1;
if(next_pos<0){
break;
}
seq[tmp] = -seq[tmp];
}//while
}//for
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

magically in my program below i am observing with few examples that number of outer iterations are limited to just 2. :)

``````order(Arr[], Seq[])
{
for(int i=0;i<Arr.length;i++)
{
bool requireFurtherIterations = false;
for(int j=0;j<Arr.length;j++)
{
if(j!=Seq[j])
{
Swap(Arr, Seq, j)
requireFurtherIterations = true;
}
}
if(!requireFurtherIterations) break;
}
}

Swar(Arr[], Seq[] , j)
{
int newIndex = Seq[j]
int temp = Arr[j]
Arr[j] = Arr[newIndex]
Arr[newIndex] = temp

temp = Seq[j]
Seq[j] = Seq[newInndex]
Seq[newIndex] = temp
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

magically in my program below i am observing with few examples that number of outer iterations are limited to just 2. :)

``````order(Arr[], Seq[])
{
for(int i=0;i<Arr.length;i++)
{
bool requireFurtherIterations = false;
for(int j=0;j<Arr.length;j++)
{
if(j!=Seq[j])
{
Swap(Arr, Seq, j)
requireFurtherIterations = true;
}
}
if(!requireFurtherIterations) break;
}
}

Swar(Arr[], Seq[] , j)
{
int newIndex = Seq[j]
int temp = Arr[j]
Arr[j] = Arr[newIndex]
Arr[newIndex] = temp

temp = Seq[j]
Seq[j] = Seq[newInndex]
Seq[newIndex] = temp
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be easily solved in O(n) time using Augmented RB tree, where each node apart from storing left , right, and color, will also store size of node( no of nodes on left subtree + no of nodes on right subtree + 1(node itself). Check out the chapter on Augmented data structures in CLRS

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def reorder(array, permutation):
i = 0
while i < len(array):
while i != permutation[i]-1:
x = permutation[i] - 1
if 0 < x < len(array):
array[i], array[x] = array[x], array[i]
permutation[i], permutation[x] = permutation[x], permutation[i]
else:
raise ValueError('Invalid permutation')
i += 1

a1 = [17, 5, 1, 9]
a2 = [3, 2, 4, 1]
reorder(a1, a2)
print(a1)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

here is an O(n) simple solution:

``````static void sort(int[] a, int[] x) {
for (int i = 0; i < a.length; i++) {
while (a[i] - 1 != i)
doubleSwap(a, a[i] - 1, i, x);
}
}

static void doubleSwap(int[] a, int i, int j, int[] x) {
int aux = a[i];
a[i] = a[j];
a[j] = aux;
aux = x[i];
x[i] = x[j];
x[j] = aux;
}``````

Comment hidden because of low score. Click to expand.
0

This is the best solution: O(n) performance, simple logic, and the least code. The code could be even shorter: replace doubleSwap method with regular swap(int arr[], int i, int j), and then calling swap twice inside the the while loop.

Comment hidden because of low score. Click to expand.
0

This seems to be broken code, not sure why it would be O(n) until the array is sorted.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.