Given an input array and another array that describes a new index for each element, mutate the input array so that each element ends up in their new index. Discuss the runtime of the algorithm and how you can be sure there won't be any infinite loops.

Question

Kyle · Accepted Answer

Essentially the same as Anh's answer but less code, assuming ES5 is available

var arr = ["a","b","c","d","e","f"];
var indices = [2, 3, 4, 0, 5, 1];

arr = indices.map(function (item, index) {
    return arr[indices.indexOf(index)];
});

Anh Nguyen · Answer

function reposition(arr, indices)
{
	var newArr = [];   // I'm not sure if extra space is allowed. If it is, the solution should be this simple.
	
	for(var i = 0; i < arr.length; ++i)
	{
		var newIndex = indices[i];
		newArr[newIndex] = arr[i];
	}
	
	return newArr;
}

var arr = ["a", "b", "c", "d", "e", "f"];
var indices = [2, 3, 4, 0, 5, 1];

reposition(arr, indices); 
// returns: ["d", "f", "a", "b", "c", "e"]

Attila · Answer

Utilisateur anonyme · Answer

Simple solution using .map() & ES6:

const inputArray = ["one", "two", "three", "four", "five", "six"]
const indexArray = [2, 1, 3, 5, 4, 6]

function mutate(input, index) {
  const newArray = index.map(i => input[i - 1])
  return newArray
}

// output: ["two", "one", "three", "five", "four", "six"]

Rahul · Answer

public static void permute(String[] a, int[] b)
{
	int n = a.length;
	for (int i = 0; i < n; i++)
	{
		while (b[i] != i)
		{
			swap(i, b[i], a, b);
		}
		for (int j = 0; j < n; j++)
		{
			System.out.print(a[j]);
		}
		System.out.println();
	}
}

public static void swap(int i, int j, String[] a, int[] b)
{
	int bt = b[j];
	b[j] = b[i];
	b[i] = bt;
	String at = a[j];
	a[j] = a[i];
	a[i] = at;
}

// you know there aren't infinite loops because the algorithm reduces the number of misplaced elements at each step

Kaanon · Answer

function remap(arr1, arr2){
            var tmp1 = arr1.slice();
            arr2.map(function(newIdx, realIdx){
                arr1[newIdx] = tmp1[realIdx];
            });
        }

Jessica · Answer

OK, and here's my in place version. It could definitely be improved since I just wrote it using the bubble sort algorithm. Any other sorting algorithm would work just fine too. Basically it works by sorting the index array and every time something in the index array is moved, it moves the same elements on the original array.

function mutateArray(arr,indexes) {
  var swapped = true;
  while(swapped) {
    swapped = false;
    for(var i = 1; i  indexes[i]) {
        swap(arr,i-1,indexes[i-1]);
        swap(indexes, i-1, indexes[i-1]);
        swapped = true;
      }
    }
  }
}

function swap(arr, oldIx, newIx) {
  var temp = arr[newIx];
  arr[newIx] = arr[oldIx];
  arr[oldIx] = temp;
}

An example:

var arr = [5,2,1,8,9,1];
var indexes = [2,4,1,0,3,5];
var expectedResult = [8,1,5,9,2,1];

Utilisateur anonyme · Answer

or if you truly want to mutate the array rather than outputting a new array:

let inputArray = ["one", "two", "three", "four", "five", "six"]
const indexArray = [2, 1, 3, 5, 4, 6]

inputArray = indexArray.map(i => inputArray[i-1])
// output: ["two", "one", "three", "five", "four", "six"]

Utilisateur anonyme · Answer

Working off of Travis' answer, but removing the need for a new array:

function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

function reposition(input, indices) {
  indices.forEach(function(newIdx, i) {
    if (indices.indexOf(i) > i) {
      swap(input, i, newIdx)
    }
  });
}

JS solution that handles repeatable elements · Answer

Travis Kaufman · Answer

Javascript Version:

function mutate(input, specArr) {
  var visited = [];
  specArr.forEach(function(newIdx, i) {
    var tmp;

    visited.push(newIdx);
    if (visited.indexOf(i) < 0) {
      tmp = input[i];
      input[i] = input[newIdx];
      input[newIdx] = tmp;
    }
  });
}

Trick is to keep track of visited indices and make sure you're not performing unecessary replacements. Run time is THETA(n) as indexOf is a constant-time operation since an array in javascript is simply an object (see http://es5.github.io/#x15.4.4.14 ).

Simple Javascript solution · Answer

function changeArr(arr,indArr) {
 var i,
   retArr = [];
  for( i = 0; i

Marti · Answer

Also for those using indexOf that's an extra O(n) you're using there!

Utilisateur anonyme · Answer

Andy · Answer

function sort(a,b){
	for(let i=0, l=b.length; i

YoYo · Answer

Yx · Answer

O(n) time and O(1) solution. Only issue is input can't be negatives or zeroes.

function changeIdxO1(A,I) {
    for (let i = 0; i  0) {
            [A[next], A[current]] = [A[current], A[next]];
            [I[next], I[current]] = [I[current], I[next]];
            A[next] = -A[next];
            next = I[current];
        }
    }
    for (let i = 0; i < A.length; i++) A[i] = Math.abs(A[i]);
    return A;
}

ela pou sai · Answer

const updatePositions = (A,B) => B.map(item => A[item])

Would that be enough?

Utilisateur anonyme · Answer

function sort(items, newOrder) {
    let i = 0
    while (i < newOrder.length - 1) {
        let j = newOrder[i]

        if (i != j) {
            swap(i, j, newOrder)
            swap(i, j, items)
        }
        else i++
    }
    return items

    function swap(i, j, arr) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
}

Ariel Azoulay · Answer

const sortBy = (inputArr, idxArr) => 
  idxArr.reduce((acc, x) => acc.concat(inputArr[x]), [])

Jessica · Answer

Here's my take on this, though I think my approach is cheating a little bit since I'm mutating, but not directly in place. It does add a little space complexity since I'm adding a new array, but there are no infinite loop problems and the runtime is just O(n) (I think...I'm really bad at big O notation calculation).

function mutateArray(arr,indexes) {
  var newArr = [];
  indexes.forEach((ix) => {
    newArr.push(arr[ix]);
  });
  arr.splice(0).push.apply(arr,newArr);
}

Jessica · Answer

OK, and after seeing that there's some confusion amongst expected outputs, I've updated my implementation based on the other take on the expected output. This version assumes that each index in the provided index array is the index value of where the element is in the starting array. So if the value at indexes[0] = 3, that would mean the first value in the output would be originalArray[3];

function mutateArray(arr,indexes) {
  var newArr = new Array(arr.length);
  indexes.forEach((ix, i) => {
    newArr[ix] = arr[i];
  });
  arr.splice(0).push.apply(arr,newArr);
}

var original = [2, 3, 1, 6, 4];
var ixes = [1, 2, 0, 4, 3];
expected results: [1, 2, 3, 4, 6]

For clarity, the other variant is in my answer above. That assumes that the value of each element in the indexes array represents the index of the value of the original array. So in the example above, the output would be [3, 1, 2, 4, 6].

Apparently a common twist is to then ask the interviewee to do this without a new array. So that's worth practicing too.

Dennis · Answer

//Bringing 2 UNIDEAL solutions

var A = ['a', 'b', 'c', 'd', 'e', 'f'];
var B = [4, 3, 2, 5, 1, 0];

//PROBLEM we need a copy of an A to get a proper base index of an element in the sort function
var BaseA = A.concat([]);

A.sort(function(a, b){
    return A.indexOf(a) < B.indexOf(BaseA.indexOf(a));
});

alert[A);

//OR We'll just add up to A sorted values and then cut off the tail, I believe it's 
//almost same performace as to create new array but well, it does mutate A
//so is it "Done is better then perfect" after all? :)

for(var i = 0, l = B.length; i < l; i++){
    A.push(A.splice(B[i], 1, undefined).pop())
}
A.splice(0, B.length);
alert[A);

Sandesh K · Answer

void swap(int a[],int b[], int i,int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
	
	temp = b[i];
	b[i] = b[j];
	b[j] = temp  ;
}

void mutate(int a[], int b[], int n)
{
	// solutions 1 . we can sort an array b and while doing that we will 
	// adjust the A[] elements as well 
	// but it is going to be nlogn
	
	// Solution 2: swap the elements of b[] ( together with a[] elements) until the number in the b[i] matches the index i then move on to i+1
	// for each swap we are placing one item in the right place. 
	// so the complexity would be O(n)

	for(int i=0;i= n)
		{
			cout << "Index out of bound " << b[i] <<< endl;
			break;
		}

		if(i != b[i]) // this may go in infinite loop, if the indices are not good in b like two 0s in the b[] 
		{
			if(b[i] == b[b[i]])
			{
				cout << "Infinite Loop Detected for the index " << b[i] << endl;
				break;
			}
			swap(a,b,i,b[i]);
		}
		else
		{
			i++;
		}
	}
}

Marti · Answer

For all of the answer using map, and visited arrays,  just to say that you are creating a new array, and from the word "mutate" I assume they don't want any extra space being used at all (also it takes longer)

My solution using ES6 is:

function mutate(input, indices) {
  const swap = (i, j) => {
    let tmp = input[i];
    input[i] = input[j];
    input[j] = tmp;
  };

  indices.forEach((newIndex, i) => swap(newIndex, i));

  return input;
}

Meta

Question d’entretien chez Meta

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois