Skip to content

Instantly share code, notes, and snippets.

@mcsheffrey
Last active September 26, 2017 17:33
Show Gist options
  • Save mcsheffrey/6977999 to your computer and use it in GitHub Desktop.
Save mcsheffrey/6977999 to your computer and use it in GitHub Desktop.
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. Run time of this solution is THETA(n) as indexOf is a constant-time operation since an array in…
var input = [1,2,3,4,5],
specArr = [0,2,1,4,3];
function mutate(input, specArr) {
var visited = [0,2]
for(var i=0; i<specArr.length; i++) {
var tmp;
//keep track of array items we've already looped through (wouldn't want to mutate twice :D)
visited.push(specArr[i]);
// if index hasn't changed we do nothing to input arr
if (visited.indexOf(1) < 0) {
// if it has changed temporarily store the value
tmp = input[i];
//swap input array item with spec item
input[i] = input[specArr[i]];
//swap specced array item with input item above
input[specArr[i]] = tmp;
}
}
}
mutate(input, specArr);
@gkatsanos
Copy link

I don't understand what this is intended to solve. It only works for the specific input above?! warning to anyone coming from google.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment