CareerCup

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;
    }
}

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.

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

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];
		}

		for (int circleHead = 0; circleHead < index.length; circleHead++) {
			if (index[circleHead] < 0) {
				continue;
			}

			int goingTo = index[circleHead] - 1;
			int valueToMove = numbers[circleHead];
			while (circleHead != goingTo) {
				int temp = numbers[goingTo];
				numbers[goingTo] = valueToMove;
				valueToMove = temp;
				temp = index[goingTo] - 1;
				index[goingTo] = -index[goingTo];
				goingTo = temp;
			}
			numbers[circleHead] = valueToMove;
		}

		// 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]

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

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;
    }
}

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

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

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.

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
}

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);
}

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;
    }
}

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++;
}

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.

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

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];
}

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;
}

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

// 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);
		}
	}

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);
                }
        }
}

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)

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;
}

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;
}

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;
		}
	}
}

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;
		}
	}
}

{{

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]);
}

}

}






}}

{{
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]);
}

}

}




}}

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!

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;
					
				}
			}
		}

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;
}

#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;
}

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;
            } 
        }
}

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]+"");
		}
	}

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]+"");
}
}

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

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;
		}


	}

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;
    }
}

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;
	}

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.

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;		
		}

}

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;
}

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
    }
}

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
}

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
}

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

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)

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;
	}