Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
37
of 39 vote

void relocate(int *arr,int size) {
	for(int i=0;i<size;i++) {
		arr[i] += (arr[arr[i]]%size)*size;
	}
	for(int i=0;i<size;i++) {
		arr[i] /= size;
	}
}

- Ganesh Ram Sundaram March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,

Can you tell me how this works?

Thanks

- / March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

Do we really need (arr[arr[i]] % size) why cant we directly put the arr[arr[i]] which i guess will yield the same result.since the values of array cannot be more than the size...

- Royal March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@/

I think what he's doing is effectively magnifying the final result so that the current value doesn't matter anymore.
When he multiplies the arr[arr[i]] by size and add the current value to it, you get a new value. This new value can use division to get the final result or modulo to obtain the current value.
When he does the division, the current value(remainder) just falls off and you get the final value.

- zelox991 March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@ Royal

I think you need the %size because you can potentially retrieve the new final value from arr[arr[i]]. And that would mess up the calculation. You can try it with the input from the question:
{2,3,1,0} will become:
{1,0,3,6}

Btw, Ganesh Ram Sundaram, this solution is ingenious.

- zelox991 March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
8
of 8 votes

It is simple maths:

(x + y*z)/z = y    provided x and y is less than z.
(x + y*z)%z = x    provided x and y is less than z.
This is the concept used here.
Example:
(3 + 4*5)/5 = 4
(3 + 4*5)%5 = 3

arr[i] = arr[i] + arr[arr[i]]*size
so arr[i]/size = arr[arr[i]]

In the code you see the author has used % below; this is done just to make sure arr[i] and arr[arr[i]] is less than size as explained earlier.
arr[i] += (arr[arr[i]]%size)*size;

Good solution.

- aka March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Thanks for all your comments! The logic I used is exactly as pointed out by aka.
In the first loop, I add (size * "OLD arr[arr[i]]") to arr[i] so that, when doing integer division by size, I get old arr[arr[i]], when doing %size, I get old arr[i]. However I add arr[arr[i]]%size to get old arr[arr[i]], in case it was already modified in the loop. The second loop simply replaces each arr[i] with old arr[arr[i]], as mentioned above.

- Ganesh Ram Sundaram March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Very nice idea. I just wanted to point out one bug (one modulo operator is missing). Here's the correction I made:

//  set A'[i] = A[i] + N * A[A[i]]
    for(int i = 0; i < N; i++)
        A[i] += (A[A[i] % N] % N) * N;

    for(int i = 0; i < N; i++)  
        A[i] /= N;

One problem of this approach is that when size of the array is big (N >= 2^31) there will be overflow.

My approach in another solves this problem.

- Westlake March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't get it - if you are modifying elemants as per @zelox991 example, why not just:

a[i]=i

- CT March 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for size greater than long long int ?

- kkr.ashish March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good idea. It's a mix and filter solution. Same algo in scala:

def relocate(arr:Array[Int]) = {
	  val n = arr.length
	  arr.map(r=>r+(arr(r)%n)*n).map(_/n).toArray
	}

- sabz August 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If I were right, the question is to modify matrix so that for any 0 <= i < n, i=a[a[i]]. Why the proposed algorithm is correct? Suppose we change the matrix to {2,0,1,3}, then the output will be {1,2,0,3}, am I right? Several observations are, 1) after modification is applied, if a[i] = j, then a[j] = i; 2) it is impossible that a[i] = j and a[i'] = j (i != i'). If such case exists, then what's the value for a[j]? If we assume that for all a[i] = j, 0 <= j < n (no value goes out of the range 0 ~ n-1), then for any i, we could pick i' (i' != i || i' == i), let a[i] = i' and a[i'] = i.

- victor October 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The solution is really brilliant! But if size of array is very big, like 2147483647, this solution can break because of int over flow.

I use -a[i]-1 instead of division so over flow can be avoided. The sub loop is used to go through the "cycle" in which values are replaced by successors.
worst case time 2n, so O(n). c++ code:

#include<iostream>
using namespace std;

void wap(int A[], int n){
	if(n <= 1) return;
	int i, tmpV, ind, tmp;
	for(i = 0; i < n; ++i){
		if(A[i] >= 0 && A[i] != i){
			tmpV = A[i];
			ind = i;
			while(A[ind] != i){
				tmp = A[ind];
				A[ind] = (-A[A[ind]] - 1);
				ind = tmp;
			}
			A[ind] = (-tmpV - 1);
		}
	}
	for(i = 0; i < n; A[i] = -(A[i]+1), ++i);
}

int main(){
	int A[] = {2, 4, 3, 0, 1};
	wap(A, sizeof(A)/sizeof(int));
	for(int i = 0; i < sizeof(A)/sizeof(int); ++i)
		cout << A[i] << ' ';
	cout << endl;

	return 0;
}

- evi January 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I used remaining bits of the given numbers to store the next value of a[i] i.e. a[a[i]]. Here is the code -

public static void relocate(int a[], int n) {
        int size = n;
        int bits = 0;
        // calculate no. of bits
        while(size > 0) {
            bits += 1;
            size >>= 1;
        }

        // generate a mask of all 1s of bits size from least significant bit
        int mask = 0;
        for(int i=0; i<bits; i++) {
            mask <<= 1;
            mask |= 1;
        }

        // store the number to be replaced in the same number but different in the remaining unused bits
        // i.e. if a number has only 3 bits set, it will look like ..00000xxx (so we can use other bits to store the new value in it)
        // first left shift the a[a[i]] to bit size so result will be ..00yyy000 and then take OR with a[i]
        // it becomes ..00yyyxxx where yyy is a[a[i]], and xxx is the a[i]
        // one thing to remember is that, we need to normalize a[a[i]] before shifting left. i.e. instead of considering ..00yyyxxx and shift it
        // we need to shift only ..00000xxx so I created a mask to do that, a[a[i]] & mask i.e. (..00yyyxxx|..00000111) and then shift left
        for(int i=0; i<n; i++) {
            a[i] = ((a[a[i]]&mask) << bits) | (a[i]);
        }

        // finally to get the new value for each a[i] (which is of form ..00yyyxxx right now) we need to shift it by "bits" size
        // so a[i] >> bits should do the trick!
        for(int i=0; i<n; i++) {
            a[i] = a[i] >> bits;
        }
    }

- HauntedGhost September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

Deducing from the example, I think what we really want here is I = arr[arr[I]], which can be done in many ways while one of them is simply let arr[k] = k.

- uuuouou February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No look at the example properly. Its not moving the indices , its moving the value present at the indices.
One information I missed in the question is , the array contains 0 to n-1 integers.

- praveen February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Your example doesn't make sense.
The condition is 'arr[I] = arr[arr[I]]'. In your example for l = 0
arr[0] = 1
arr[1] = 0
so arr[I] != arr[arr[I]]

- Anonymous February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree the question is i = arr[arr[i]] and the solution proposed arr[k] = k is correct. But as mentioned there are other solutions also and I could not think of any way to do it. Is it NP complete?

- kr.neerav March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, this question is pretty poorly worded. I interpreted it the same way as you.

For those that were wondering what "WAP" means, I think it's short for "Write A Program". Why the poster felt the need to abbreviate that is beyond me.

I think the problem could be better stated as:

Given an unsorted array of n integers from 0 to n-1 (int[] input), return an output array (int[] output) such that

for all 0 <= i < n: 
output[i] == input[input[i]]

This should be done with O(n) time complexity and O(1) space complexity (so it needs to be done "in-place" in the input array).

- michaelbarlow7 March 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 7 vote

public static void modIndex(int[] array){
int pre = array[0];
int idx = 0;
array[0] = -array[pre];
while (true){
int i = 0;
for(; i < array.length;i++){
if(array[i] == idx)
break;
}
if(i == array.length) break;
int t = array[i];
array[i] = - pre;
pre = t;
idx = i;

}

for(int i = 0 ; i < array.length; i++)
array[i] *= -1;
}

- ykcland72 February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if(i == array.length) break;

:_(

- S O U N D W A V E March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@BigKdotAtTdot

if(i == array.length)

indicates that all elements are relocated. Then it can jump out of the loop.

- ykcland72 March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,
What is point of making the array elements into negative.

- brahmasani99 March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Please can you explain your algorithm?
Or comment your code? Or both :)

- / March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class InPlaceRelocation {

	public static void relocate(int[] arr) {
		if (arr == null || arr.length == 1) {
			return;
		}

		int len = arr.length;
		int shift = (int) Math.ceil(Math.log10(len) / Math.log10(2));
		int mask = (int) Math.pow(2.0, shift) - 1;
		for (int i = 0; i < len; ++i) {
			arr[i] += (arr[arr[i] & mask] & mask) << shift;
		}
		for (int i = 0; i < len; ++i) {
			arr[i] >>= shift;
		}
	}

	public static void main(String[] args) {
		int[] arr = { 2, 3, 1, 0 };
		relocate(arr);
		System.out.println(Arrays.toString(arr));

		int[] arr2 = { 5, 7, 2, 8, 3, 6, 4, 1, 0 };
		relocate(arr2);
		System.out.println(Arrays.toString(arr2));

	}
}

- Anonymous February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can u plz explain ur logic ?

- praveen February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. Number up to n can be held in log(n) ceiling bits, say m.
2. The first loop puts target value into the bits offset by m bit from right, so the right most m bits still hold the original value.
3. The second loop purges the original value, which is index to the cell holding target value, and move the m bits holding the target value, to right most positions.

It is possible to use to implement a similar solution using mod division and multiplication, instead of using bit wise operations.

- Anonymous February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Ok this works for smaller numbers may be, how about larger numbers.
Lets say we want to do this using 'byte' data type and there are numbers from 0 to 127. Would this still work ? nevertheless a vry nice approach.

- praveen February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method assuming the length is smaller enough to put into integer (8/16/32 bits?) right?

- Daniel.Softnado March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in line : arr[i] += (arr[arr[i] & mask] & mask) << shift;
can't it just be arr[i] += arr[arr[i]]<<shift; as integers are guaranteed to be between 0 and n-1. What is the point in masking anyways.

- coder March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@coder, the mask is used to clear set bits beyond the m right most bits. When an element points back to an element with smaller index, the targeted value is no longer the original value.

- Anonymous March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually using mod division and multiplication results shorter, and easy to understood code:

public static void relocate(int[] arr) {
		if (arr == null || arr.length == 1) {
			return;
		}

		int len = arr.length;
		for (int i = 0; i < len; ++i) {
			arr[i] += arr[arr[i] % len] % len * len;
		}
		for (int i = 0; i < len; ++i) {
			arr[i] /= len;
		}
	}

- Anonymous March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def f(a,n,i):
	if i < n: 
		a_a_i = a[a[i]]
		f(a,n,i+1)
		a[i] = a_a_i

- Anonymous February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need to do it without using additional memory, your solution implicitly uses stack for recursion.

- praveen February 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void wapMod(int[] array) {
	int first = array[0], i = 0;
	while(array[i] != 0) {
		int tmp = array[i];
		array[i] = array[array[i]];
		i = tmp;
	}
	array[i] = first;
}

- usunyu March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this only works if 0 is the last element

- jeff March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, you are right, thanks for pointing that, and I modify code based on my previous thought.

public static void flip(int[] array) {
		for(int i = 0; i < array.length; i++) {
			array[i] = -array[i];
		}
	}
	
	public static int firstIndex(int[] array) {
		int index = -1;
		for(int i = 0; i < array.length; i++) {
			if(array[i] < 0) {
				index = i;
				break;
			}
		}
		return index;
	}

	public static void wapMod(int[] array) {
		// mark unfinish
		flip(array);
		int index;
		// if all number is positive, we finish
		while((index = firstIndex(array)) != -1) {
			// find first index if we haven't finish
			int first = Math.abs(array[index]), i = index;
			while(Math.abs(array[i]) != index) {	// haven't go back to first
				int nextIndex = Math.abs(array[i]);
				array[i] = Math.abs(array[nextIndex]);
				i = nextIndex;
			}
			array[i] = first;
		}
	}

- usunyu March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here we have a loop. a[0] becomes a[2] and a[2] becomes a[1]... a[0]->a[2]->a[1]->a[3]->a[0]. If we change any one value we will break the cycle. So, until we change all the values, we need to retain both the old and new values. Normally we could save them in a temporary vector b. But here we are not allowed to do that. But the hint is that the number are between 0...n-1. So, assuming n^2 < max(int) we can keep the old and the new values simultaneously with just a single number. Here is what we can do:

First change each of a[i] to n*(newval+1)+oldval. Given a[i], we can get its old value by a[i]%n and get the new value by (a[i]/n -1). Here is my code:

#include <iostream>

int main(){
	int a[] = {2,3,1,0};
	int n = 4;
	for(int i=0;i<n;++i){
		if(a[a[i]]<n){
			a[i] = a[i]+n*(a[a[i]]+1);
		}else{
			a[i] = a[i]+n*(a[a[i]]%n+1);
		}
	}
	for(int i=0;i<n;++i){
		a[i]=a[i]/n -1;
	}
	for(int i=0;i<n;++i){
		std::cout<<a[i]<<",";
	}
	return 0;
}

- Naresh Vankayalapati March 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

it won't work with {4,3,1,2} where you should get {0,2,3,1} as output

- Janki March 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is working for {0,3,1,2}(assuming you typed 4 for 0 by error). I get {0,2,3,1}.

- Naresh Vankayalapati March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
    int A[] = {2, 3, 1, 0, 5, 6, 4};
    const int N = sizeof (A) / sizeof (A[0]);

    for (int i = 0; i < N; i++) {
        if (A[i] < 0)   // already processed
            continue;
    
        if (A[i] == i) {
            A[i] = -A[i] - 1;   // reverse it to mark it processed
            continue;
        }
    
        int t = A[i];
        int j = i;
    
        do {
            int k = A[j];
            A[j] = - A[k] - 1; // use negative value to to mark it processed
            j = k;
        } while (i != A[j]);
        A[j] = -t - 1;
    }

    for(int i = 0; i< N; i++) {
        A[i] = -A[i] - 1;       // restore the value
        cout << A[i] << " ";
    }
    cout << endl;

}

- Westlake March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution:

import java.io.*;
import java.util.*;

public class Question1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; ++i) {
            A[i] = Integer.parseInt(st.nextToken())+1;
        }

        for (int i = 0; i < N; ++i) {
            if (A[i] > 0) {
                int initialVal = A[i];
                int j = i;
                while (A[j]-1 > 0){
                    int temp = A[j]-1;
                    A[j] = -A[temp];
                    j = temp;
                };

                A[j] = -initialVal;
            }
        }
                
        for (int i = 0; i < N; ++i) {
            A[i] = -A[i]-1; 
        }

        out.println(Arrays.toString(A));

        out.flush();
        out.close();

        System.exit(0);
    }
}

- srikantaggarwal March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int *res_arr;
  for(i=0; i<arr_len; i++) {
    res_arr=(arr+arr[i]);
    res_arr+=i;
  }

/*reset res_arr and print *res_arr; res_arr++*/

- asdf March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] IndexSwap(int[] values) {
        int n = values.length;
        if (n*n >= Integer.MAX_VALUE)
            throw new IllegalArgumentException("Size of array is too large: "+n);
        for (int i=0; i < n; i++) {
            if (values[values[i]] <= n)
                values[i] = values[i]*n+values[values[i]];
            else {
                int value = values[values[i]] / n;
                values[i] = values[i]*n+value;
            }
        }
        for (int i=0; i < n; i++) {
            values[i] = values[i] % n;
        }
        return values;
    }

- Store the new values outside of n-1 March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void relocate(int[] arr,int size)
{
	int multiplier=Math.pow(10,Math.ceil(Math.log10(size)));
	for(int i=0;i<size;i++)	
	{
		arr[i]=arr[arr[i]]+arr[i]*multiplier;
		arr[arr[i]/multiplier]=arr[i]/multiplier;
		arr[i]=arr[i]%multiplier;	
	}
}

- vilhkn March 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ public class InPlaceRelocation { public static void relocate(int[] arr) { for (int i = 0; i < arr.length; ++i) { if (arr[i] >= 0) { int headPos = i; int headValue = arr[i]; int currPos = headPos; while (true) { if (arr[currPos] == headPos) { arr[currPos] = -(headValue + 1); // mark visited cell negative break; } int temp = arr[currPos]; arr[currPos] = -(arr[arr[currPos]] + 1); currPos = temp; } } } for (int i = 0; i < arr.length; i++) { arr[i] = -arr[i] - 1; } } public static void main(String[] args) { int[] arr = { 2, 3, 1, 0 }; relocate(arr); System.out.println(Arrays.toString(arr)); int[] arr2 = { 5, 7, 2, 8, 3, 6, 4, 1, 0 }; relocate(arr2); System.out.println(Arrays.toString(arr2)); } } - Anonymous March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class InPlaceRelocation {

	public static void relocate(int[] arr) {
		for (int i = 0; i < arr.length; ++i) {
			if (arr[i] >= 0) {
				int headPos = i;
				int headValue = arr[i];
				int currPos = headPos;
				while (true) {
					if (arr[currPos] == headPos) {
						arr[currPos] = -(headValue + 1); // mark visited cell negative
						break; 
					}
					int temp = arr[currPos];
					arr[currPos] = -(arr[arr[currPos]] + 1);
					currPos = temp;
				}
			}
		}

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

	public static void main(String[] args) {
		int[] arr = { 2, 3, 1, 0 };
		relocate(arr);
		System.out.println(Arrays.toString(arr));

		int[] arr2 = { 5, 7, 2, 8, 3, 6, 4, 1, 0 };
		relocate(arr2);
		System.out.println(Arrays.toString(arr2));
	}
}

- Anonymous March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can even do number splitting based on bits, given all the integer, you can store arr[arr[i]] on other half (16 bits) and arr[i] on first 16 bits.

int[] arr = new int[] {2, 3, 0, 1}
for(int i : new int[] {1, 2, 3, 4})
{
   arr[i] |= ((arr[arr[i]] & 0x0000EEEE) << 16));
}

for(int i : new int[] {1, 2, 3, 4})
{
   arr[i] = arr[i] >> 16;
}

- shivamk March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good answer, just iterate with

for(int i = 1; i <= arr.length; i++) {...}

- Marboni July 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would like to correct my previously posted algorithm, here is the one that compiles, written in Java:

import java.util.Arrays;

public class test {

	public static void main(String[] args) 
	{
		int[] arr = new int[] {2, 3, 2, 1};
		for(int i : new int[] {0, 1, 2, 3})
		{
		   arr[i] |= ((arr[arr[i]] & 0x0000FFFF) << 16);
		}

		for(int i : new int[] {0, 1, 2, 3})
		{
		   arr[i] = arr[i] >> 16;
		}
		
		System.out.println(Arrays.toString(arr));
	}

}

- shivamk March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could we keep rotating the array say i times and check if the terminating condition for all elements in the array. a[i] == a[a[i]] . The rotating process could be done by log(n) and the worst case would be n log(n)

- Anonymous March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution inspired by cycle leader iteration algorithm

def f(i,t):
	if not t:
		b = a[i]
		c=a[a[i]]
		t = (b==0)
		f(b,t)
		a[i]=c

- aaadith March 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

call using f(0, False)

- Anonymous March 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each element, trace it down until a loop is formed.

e.g. [2, 3, 1, 0]

1. all add one ==> [3, 4, 2, 1]
2. at position 0
arr[0] = arr[arr[0] - 1] = arr[3 - 1] = arr[2]

so, we swap position 0 and 2, and maintain a integer "value" to remember what arr[2] is originally
Here we get:
- new arr: [-2, 4, 3, 1] (-2 is to mark it's in right place)
- value: 2 (what arr[2] is originally)

then we at the position 2,
arr[2] = arr[arr[2] - 1] = arr[value - 1] = arr[1]
then we swap position 2 and 1, and update "value" to arr[1]
new arr: [-2, 3, -4, 1]
value: 4

then we at position 1
as before, we get
new arr: [-2, -1, -4, 3]
value: 1

then we at position 3
arr[3] = arr[arr[3] - 1] = arr[value - 1] = arr[0]
since arr[0] now is negative, we've finished this loop, set current position to its opposite and move to next position.
Now arr = [-2, -1, -4, -3]

3. since all values are negative, they're in right places. Restore value, we get:
[-2, -1, -4, -3] ==> [2, 1, 4, 3] ==> [1, 0, 3, 2]

4. done

void relocate(int arr[], int n)
{
	if (arr == NULL || n <= 0) return;

	for (int i = 0; i < n; i++)
	{
		arr[i] += 1;
	}

	for (int i = 0; i < n; i++)
	{
		if (arr[i] < 0) continue;	// negative means it's in right place

		if (arr[i] == i + 1)	// alreay in right place
		{
			arr[i] = 0 - arr[i];
			continue;
		}

		int index = i;	// the position to be modify
		int value = arr[index];	// value of arr[index] (originally)

		while (arr[value - 1] > 0)
		{
			int tmpValue = value;
			value = arr[tmpValue - 1];
			arr[tmpValue - 1] = arr[index];
			arr[index] = 0 - value;
			index = tmpValue - 1;
		}
		arr[index] = 0 - arr[index];
	}

	for (int i = 0; i < n; i++)
	{
		arr[i] = 0 - arr[i] - 1;
	}
}

- wangchi1989 March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

onestopinterviewprep.blogspot.com/2014/03/arri-arrarri-in-place.html

- wELLWISHER March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n*log(n))

public void arraySwap(int[] a, int size) {
	int currentIndex = 0, replacementIndex;
	int replacementValue = a[a[0]], currentValue;

	for (int i = 0; i < size; i++) {
		currentValue = a[currentIndex];
		a[currentIndex] = replacementValue;
		replacementValue = currentValue;

		for (int j = 0; j < size; j++) {
			if ( a[j] = currentIndex) {
				replacementIndex = j;
				break;
			}
		}

		currentIndex = replacementIndex;
	}
}

- Greg April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution is very simple. It sounded like they were looking for something along those lines. I can paste the code I wrote whn on my laptop. Typing on the phone is too much hassle.

- bduhbya April 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

curious!

would [0, 1, 2, 3] be considered as a valid answer?

- blackoil May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The largest value is n-1, if this value can fit into the lower 16 bits of the integer, we can use the higher 16 bits as a buffer to swap numbers in place. So if n <= 2^17, we can shift the lower 16 bits to higher 16 bits for A[i], making spaces for A[A[i]], then add the original A[A[i]] back (now it's shifted left 16 bits, so shift it back before adding it to A[i]), finally clear out the higher 16 bits.

SwapInPlace(int[] A){
  if (A.size() > Math.power(2, 17)){
    System.out.println("Can't do it");
    return;
  }
  
  for( int i=0; i< A.size(); i++)
    A[i]<<16;
  
  for( int i=0; i< A.size(); i++)
    A[i] = (A[i] + A[A[i]]>>16)&(~(1<<16));
}

- Avaln May 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure why there is ; appended to the end of shift operator, but anyway, you got the idea.

- Avaln May 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction: to get the original value, do not shift the current value back because its lower 16 bits might already been set, so shift to right to get the original value will lose the lower 16 bits. So we write another function that returns a value copy of the higher 16 bits of a number to get its original value.

SwapInPlace(int[] A){
  if (A.size() > Math.power(2, 17)){
    System.out.println("Can't do it");
    return;
  }
  
  for( int i=0; i< A.size(); i++)
    A[i]<<16;
  
  for( int i=0; i< A.size(); i++)
    A[i] = (A[i] + TakeHigherBits(A[A[i]))&(~(1<<16));
}

TakeHigherBits(int a){
  return A[A[i]] >> 16;
}

- Avan May 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can anyone just explain me the question..how is the modification working..?

- sumedha May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- (int )modifyArray:(int *)array :(int )index :(int )value :(int )size
{
    if(index != size)
        array[index] = [self modifyArray:array :index+1 : array[array[index]] :size];
    return value;
}
// Input:
NSLog(@"\nmodifyArray");
    int arr1[] = {2,3,1,0};
    //int arr1[] = {3,2,0,1};
    [self modifyArray:arr1 :0 :arr1[arr1[0]] :4];
    for(int i=0;i<4;i++)
    {
        NSLog(@"%d",arr1[i]);
    }
// Output:
/*
1,0,3,2
*/

- tarunkhurana1982 September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved this with recursion and looking up the index from the last in the array and then go from there.

1. check wether this is the first round and store the first item (temp)
2. put new item=a into first item
3. lookup (index of a) - in the array
4. now put temp in the found place
and so on

list123 = [2,3,1,0]
def trans(temp,index,firsttemp):
    lastround=False
    i=0
    
    if(temp == None):
        firsttemp=list123[0]
        temp=list123[0]
        firsttemp=list123[temp]
        list123[0]=list123[list123[0]]
        
        
   
    if(index == firsttemp):
        i=1
        lastround=True 
        
    while i <= len(list123)-1:
        if(list123[i] == index):
            list123[i] = temp
            if(lastround == False): return trans(index,i,firsttemp)
        else: i+=1
    return

- ghirlwhocodes October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You just need to store the next index before it is overwritten. I am doing this using the nextIndex variable. Java code:

void solution(int[] v) {
        if (v == null || v.length < 2) {
            return;
        }

        int len = v.length;
        int index = 0, nextIndex = 0;

        int temp = v[0];
        while (len-- > 0) {
            index = nextIndex;
            nextIndex = v[index];
            v[index] = v[v[index]];
        }
        v[index] = temp;
    }

- AlexB December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Awesome solution. The first solution to this post.

- Anonymous January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ALL integers from 0 to N-1 are in the array.
Effectively, elements of the array are pointing to each other.
This forms cycles of pointers. Extreme cases are: one long cycle of N elements
or: N 'cycles' of one elment each (the case when array is sorted).
One can follow the pointers in a cycle until returning back its start,
then move on to another cycle.

The first issue is how to locate the next cycle?
This is done by marking each 'visited' element so it is not picked more than once.
We notice that the elements of N must all be positive, therefore we can use the
highest order bit as a 'visited' flag. All the flags will get reset at the end.

Secondly, the first link in the cycle must be remembered since it gets overwritten.

public static void modifyArray(int[] a) {

  // nothing to do when less than 2 elements
  if (a == null || a.length < 2) {
    return;
  }

  int pos = 0;
  int visited = 0;      // starts at 0, keeps increasing until all are visisted
  int first = a[pos];   // remember first value in the cycle
  
  while (true) {
    
   int nextPos = a[pos]; 
    
   int val = -1;
    
   // guard case when cycle length is 1 (nextPos < 0)
   if (nextPos >= 0) {
     val = a[nextPos];
   }
  
    
   // check if flag was set (negative)
   if (val < 0) {
     
     // complete current cycle 
     a[pos] = ~first;
     
     // find next unvisited element
     while (true) {
       visited++;
       if (visited == a.length) {
         // visited all elements, reset flags
         for (int i = 0; i < a.length; i++) {
           a[i] = ~a[i];
         }
         return;
       }
       
       // start new cycle here?
       if (a[visited] >= 0) {
         pos = visited;
         first = a[pos];
         nextPos = pos;
         break;
       }
     }  
   } else {
     a[pos] = ~val; // modify and add flag (complement)
     pos = nextPos; // new position
   }
    
  }
}

- Jamie June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Arr{
	public static void main(String[] args){
		int[] arr = {2,3,1,0};
		int[] arr2 = new int[arr.length];
		for(int i=0;i<arr.length;i++){
			arr2[i] = arr[i];
		}
		for(int i=0;i<arr.length;i++){
			arr[i] = arr2[arr[i]];
		}
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+",");
		}
	}
}

- Milin Joshi September 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Arr{
	public static void main(String[] args){
		int[] arr = {2,3,1,0};
		int[] arr2 = new int[arr.length];
		for(int i=0;i<arr.length;i++){
			arr2[i] = arr[i];
		}
		for(int i=0;i<arr.length;i++){
			arr[i] = arr2[arr[i]];
		}
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+",");
		}
	}
}

- milincjoshi September 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
using namespace std;

bool inPlaceSwapByIndex(vector<int>& arr)
{
int anchorItem = 0;
int anchor = 0;
bool anchorSet = false;

for(int i = 0; i < arr.size(); ++i)
{
if(i == arr[i])
{
continue;
}

if( anchorSet && arr[i] == anchor )
{
arr[i] = anchorItem;
anchorSet = false;
continue;
}

if(!anchorSet)
{
anchor = i;
anchorItem = arr[i];
anchorSet = true;
}
arr[i] = arr[arr[i]];
}
}

- ztian@thoughtworks.com February 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
{{{def f(a,n,i): if i < n: a_a_i = a[a[i]] f(a,n,i+1) a[i] = a_a_i - {{{r}}} February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can be accomplished the same way you would do it with memory allocation, but instead using pointers.

void mymod(vector<int> & array)
{
        vector<int*> pointers(array.size(),NULL);
        for (unsigned int i = 0; i < array.size(); i++)
        {
                pointers[i] = &array[array[i]];
                cout<<*pointers[i]<<" ";
        }
        cout<<endl;

}

- Anonymous February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Reverse function can be work in this use case:
example : if a = {2,3,1,0} ----> Reverse(0,4)--> 0,1,3,2----> reverse (0,1)---> 1 ,0 ,3,2

- Raj March 01, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More