Skip to content

Instantly share code, notes, and snippets.

@mayashavin
Created February 11, 2018 21:51
Show Gist options
  • Save mayashavin/7d669a232a3c5d35dda472e954259665 to your computer and use it in GitHub Desktop.
Save mayashavin/7d669a232a3c5d35dda472e954259665 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
// Input: [a,b,c,d,e,f,g] & [3,6,2,4,0,1,5]
// Output: [e,f,c,a,d,g,b]
// Question to ask: Input validation? Length same? indices array has to contains only numbers from 0 -> length - 1.
function reorderArr(arr, indices){
//Check if arrays are same length
if (arr.length !== indices.length || invalidOrder(indices, arr.length - 1)) return;
for (var i = 0; i < arr.length; i++){
while (indices[i] !== i){
var newPos = indices[i];
var savedPos = indices[newPos], savedEl = arr[newPos];
//swap
indices[newPos] = newPos;
arr[newPos] = arr[i];
arr[i] = savedEl;
indices[i] = savedPos;
}
}
return arr;
}
function invalidOrder(orders, maxNumber){
for (var i = 0; i < orders.length; i++){
var order = orders[i];
if (isNaN(order) || order < 0 || order > maxNumber){
return false;
}
}
return true;
}
//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
// Input arr = [8, 6, 7, 5, 3, 0, 9];
// indices = [3, 6, 2, 4, 0, 1, 5];
// Output [5, 9, 7, 3, 8, 6, 0];
function reorderArr2(arr, indices){
//Check if arrays are same length
if (arr.length !== indices.length || invalidOrder(indices, arr.length - 1)) return;
for (var i = 0; i < arr.length; i++){
var element = arr[i];
var currPos = i;
while (indices[currPos] !== i){
var nextPos = indices[currPos];
arr[currPos] = arr[nextPos];
indices[currPos] = currPos;
currPos = nextPos;
}
arr[currPos] = element;
}
return arr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment