Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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...
@/
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.
@ 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.
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.
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.
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.
I don't get it - if you are modifying elemants as per @zelox991 example, why not just:
a[i]=i
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
}
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.
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;
}
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;
}
}
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.
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.
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]]
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?
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).
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;
}
@BigKdotAtTdot
if(i == array.length)
indicates that all elements are relocated. Then it can jump out of the loop.
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));
}
}
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.
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.
This method assuming the length is smaller enough to put into integer (8/16/32 bits?) right?
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, 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.
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;
}
}
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;
}
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;
}
}
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;
}
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;
}
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);
}
}
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;
}
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));
}
}
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;
}
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));
}
}
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
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;
}
}
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;
}
}
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));
}
Not sure why there is ; appended to the end of shift operator, but anyway, you got the idea.
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;
}
- (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
*/
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
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;
}
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
}
}
}
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]+",");
}
}
}
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]+",");
}
}
}
#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]];
}
}
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;
}
- Ganesh Ram Sundaram March 01, 2014