Left rotation arrays algorithm

Question

This is my solution to the common 'Array Rotation' algorithm. As I am currently practicing for coding interviews, I want to make sure that my code in fact valid for coding interview scenarios. Would I lose points for using JavaScript's built-in shift and push array methods?

function main() {
var n_temp = readLine().split(' ');
var arrLength = parseInt(n_temp[0]);
var rotations = parseInt(n_temp[1]);
var frontNum;
a = readLine().split(' ');
a = a.map(Number);
for (var i = 0; i < rotations; i++) {
 frontNum = a.shift();
 a.push(frontNum);
}
 console.log(a.join(' '));
}

• Phrancis: Can you clarify the premise of your question? None of us are in position to tell you what your interviewer(s) would consider valid or invalid, or worthy of losing points. If you're looking to improve your code in general terms, please rephrase your question accordingly.

Answer 1

As Phrancis noted, there's no way for us to tell what an interviewer might want to learn from this. So this is just based on my impressions.

I don't know why this is wrapped in a main function. The code appears written to run once, and take its input from the command line. But in that case, there's no reason to wrap it at all, really.
Conversely, if you do wrap it in a function, something has to actually call that function, but I don't see that anywhere.

So the code looks like it's supposed to be a standalone example that you just run - but it won't do anything unless you call main() yourself. However, if the point is to make a function that can be used with other code, then:

1. Don't call your function main, because that makes no sense
2. Don't take over input and output. If I call a function to rotate an array, I'd expect to pass in the array to rotate, and get an array back. I don't expect to have to enter stuff manually, and just have the results printed back at me.

It'd make more sense if your code only handled the rotation itself, returned the rotated array, and left everything else to other code. Rotating the array is the core task here; not input handling or printing. That's just scaffolding to prove it works - you can still add all that, and make a self-contained little test script, but again, that's not the point of implementing array rotation.

So I'd focus on the rotation itself, put that in a function. Something like rotateArray(array, steps).

Now, for your actual implementation:

• There's a straight-up bug: If the array is empty to begin with, shift() will return undefined which then that gets pushed back to the array n times. So for n rotations of an empty array, you'll get an array back with n values in it (which are all undefined).

• I wonder what'll happen if I try to rotate an array, say, 9,007,199,254,740,990 times. I'm betting it'd take a while (code's \$O(n)\$). And in the end, the rotated array might be back where it started, making all those trillions of shifts and pushes pointless. So that seems like there are optimizations that can be made.

• Using shift and push is a valid solution, just not a very efficient one. Rotating an array is the same as chopping it into two pieces and putting them together "backwards". That is what shift and push does too, they just can't do more than one element at a time.

• Why can't I pass a negative rotation-count to rotate right instead?

Here's what I'd do:

function rotateArray(array, steps) {
 // check if there's even something to rotate
 if(array.length < 2) {
 return array.slice(0); // always return a copy
 }
 // get the number of actual rotations to perform
 var n = steps % array.length;
 // check if there's any need to rotate
 if(n === 0) {
 return array.slice(0); // always return a copy
 }
 // slice and concat
 if(n < 0) {
 return array.slice(n).concat(array.slice(0, array.length+n));
 } else {
 return array.slice(n).concat(array.slice(0, n));
 }
}

This code does a few simple checks to see if there's any reason to rotate the array at all, and, if there is, it does by concatenating two slices (code's \$O(1)\$), rather than going steps number of iterations with shift and push.
And in case there's no reason to rotate anything, it just returns a copy of the input array (so that the output is always a new array, even if nothing needed to be rotated).

• tony19: In the case of no rotation, why return a copy instead of the original array? (Could we optimize by simply returning array in that case?)
• Flambino: @tony19 Because the function should always return a copy in order to be consistent. If it sometimes doesn't, you don't know what you're getting. E.g. you have array a, and you do var x = rotateArray(a, n).pop(). If the function returns a copy, a remains untouched. But if it just returns a reference to its input, then the pop will actually be modifying the original a array. If the function's inconsistent, you just don't know what'll happen. The function could also be written to do the opposite: Always modify the array in-place (i.e. side-effects). But I'd rather get a copy back.
• cFreed: Excellent review. But I suggest a slight improvement: the whole // slice and concat part might be replaced by a // splice and concat which is merely return array.splice(n).concat(array);. This way only one splice() operation is needed instead of two slice() ones, and it works with n positive or negative.
• Flambino: @cFreed Good point. However, splice modifies in-place, which I'd rather avoid (though it's a valid solution; alluded to something like that in an earlier comment). You could of course make a copy and modify that with splice
• cFreed: Oops! You're totally right. The ironic point is that I'd previously read the comment about not modifying the original array, and already strongly agreed. But I forgot it when I thought to use splice()! Sigh...