Interview Question

Front End Engineer Interview

-Menlo Park, CA

Facebook

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.

Answer

Interview Answers

24 Answers

11

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

Kyle on

3

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

Anh Nguyen on

2

function repositionElements(arr, indices) { // assert(arr.length === indices.length) var moved = []; for (var i = 0; i < arr.length; i++) { moved.push(false); } var moveFrom, moveTo, itemToMove; for (moveFrom = 0; moveFrom < arr.length; moveFrom++) { itemToMove = arr[moveFrom]; while (!moved[moveFrom]) { moveTo = indices[moveFrom]; var tmpItem = arr[moveTo]; arr[moveTo] = itemToMove; itemToMove = tmpItem; moved[moveFrom] = true; moveFrom = moveTo; } } return arr; } var arr = ["a", "b", "c", "d", "e", "f"], indices = [2, 3, 4, 0, 5, 1]; repositionElements(arr, indices); // returns: ["d", "f", "a", "b", "c", "e"]

Attila on

1

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

Kaanon on

1

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

Anonymous on

1

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

Jessica on

0

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

Simple Javascript solution on

0

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

Marti on

0

let input = [1,2,3,4,5]; let newIndex = [3,1,0,4,2]; function transform(input, newIndex) { let res = []; for (let i = 0; i < input.length; i++) { let index= newIndex[i]; let val = input[i]; res[index] = val; } return res; } function transform2(input, newIndex) { let i = 0; while (i < input.length) { if (i == newIndex[i]) { i++; } else { swap(input, i, newIndex[i]); swap(newIndex, i, newIndex[i]); } } } function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

Anonymous on

0

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

Andy on

0

function correctTheOrder(arr, indices) { return arr.map((noUse, index) => { return arr[indices.indexOf(index)] }) } // Time complexity = O(n2) // Space complexity = O(n) function correctTheOrder2(arr, indices) { let i = 0; while (i < arr.length) { if (indices[i] === i) { i++; } else { let temp = arr[i]; arr[i] = arr[indices[i]]; arr[indices[i]] = temp; temp = indices[i]; indices[i] = indices[indices[i]]; indices[temp] = temp; } } return arr; } // Time complexity = O(n) // Space complexity = O(1)

YoYo on

0

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

Yx on

0

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

ela pou sai on

1

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

Anonymous on

0

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

Ariel Azoulay on

0

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 on

0

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.

Jessica on

0

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

Dennis on

0

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

Sandesh K on

1

var assert = require('assert'); var arr = ['a','b','c','d','e','f','g', 'a']; var indexes = [2,1,0,3,4,5,7,6] var mutate = function mutate(arr, ind){ var swapped = {}; indexes.forEach(function(nI, i){ var newEl, el; el = arr[i]; arr[i] = swapped[nI] || arr[nI]; swapped[i] = el; }); }; mutate(arr, indexes) assert.deepEqual(arr, ['c','b','a','d','e','f','a', 'g']);

JS solution that handles repeatable elements on

0

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

Anonymous on

0

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

Marti on

2

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

Rahul on

1

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

Travis Kaufman on

Add Answers or Comments

To comment on this, Sign In or Sign Up.