## Facebook Interview Question for Software Engineer / Developers

• 7

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
35
of 37 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;
}
}``````

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

Hi,

Can you tell me how this works?

Thanks

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

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

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.

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.

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

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.

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

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.

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

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.

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

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

a[i]=i

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

for size greater than long long int ?

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

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

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.

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

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

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
for(int i=0; i<bits; i++) {
}

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

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.

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

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.

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

The condition is 'arr[I] = arr[arr[I]]'. In your example for l = 0
arr = 1
arr = 0
so arr[I] != arr[arr[I]]

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

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?

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

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).

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

public static void modIndex(int[] array){
int pre = array;
int idx = 0;
array = -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;
}

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

``if(i == array.length) break;``

:_(

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

@BigKdotAtTdot

``if(i == array.length)``

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

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

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

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

Or comment your code? Or both :)

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

}
}``````

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

Can u plz explain ur logic ?

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

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.

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.

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

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

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

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.

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

@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.

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

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

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

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

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

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

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

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

this only works if 0 is the last element

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

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

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

Here we have a loop. a becomes a and a becomes a... a->a->a->a->a. 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;
}``````

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

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

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

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

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;

}``````

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 {
PrintWriter out = new PrintWriter(System.out);

int[] A = new int[N];

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

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++*/``````

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

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

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)); } }
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) {
while (true) {
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));
}
}``````

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

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

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

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

}``````

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)

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

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

call using f(0, False)

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 = arr[arr - 1] = arr[3 - 1] = arr

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

then we at the position 2,
arr = arr[arr - 1] = arr[value - 1] = arr
then we swap position 2 and 1, and update "value" to arr
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 = arr[arr - 1] = arr[value - 1] = arr
since arr 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;
}
}``````

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

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

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

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.

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?

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

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

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

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

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

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..?

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] :4];
for(int i=0;i<4;i++)
{
NSLog(@"%d",arr1[i]);
}
// Output:
/*
1,0,3,2
*/``````

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
temp=list123
firsttemp=list123[temp]
list123=list123[list123]

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

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;
while (len-- > 0) {
index = nextIndex;
nextIndex = v[index];
v[index] = v[v[index]];
}
v[index] = temp;
}``````

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

Awesome solution. The first solution to this post.

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
}

}
}``````

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

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

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

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

}

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

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.