1
\$\begingroup\$

The task:

Write a function that rotates a list by k elements. For example, [1, 2, 3, 4, 5, 6] rotated by two becomes [3, 4, 5, 6, 1, 2]. Try solving this without creating a copy of the list. How many swap or move operations do you need?

const lst = [1, 2, 3, 4, 5, 6];
const rotateBy = 2;

The functional solution takes 2 operations (slice twice)?:

// I guess a slice is technically not a "copy of the list" but rather it's sub-elements, so it's allowed?

const rotate = (lst, rotateBy) => [...lst.slice(rotateBy % lst.length), ...lst.slice(0, rotateBy % lst.length)];

console.log(rotate(lst, rotateBy));


console.log(rotate(lst, rotateBy));

The imperative solution takes as many operations as there are elements:

function rotate(lst, rotateBy) {
  const res = [];
  for (let i = rotateBy % lst.length, len = lst.length; res.length < len; i = ++i % len) {
    res.push(lst[i]);
  }
  return res;
}
console.log(rotate(lst, rotateBy));
\$\endgroup\$
  • \$\begingroup\$ The functional (declarative) approach may only take 2 calls but its about how much work the CPU is doing, not the selection of high level calls you make. If there was an array method Array.rotate(2) would that count as one operation? Also you are copying the array items with slice so total move ops is 2 * array.length. 1 each for slice to temp array, then 1 each from temp array to new array. All your problem refer to lists, in many languages lists are linked, a linked list can be rotated in 2 operations (if it is indexed), or 2 + rotateBy if no index \$\endgroup\$ – Blindman67 Apr 8 at 11:45
  • \$\begingroup\$ You should consider edge cases as well. Your solutions no longer work when the number of rotations exceeds the length of the array. \$\endgroup\$ – TheDancingCode Apr 9 at 7:03
  • \$\begingroup\$ @TheDancingCode would you say that’s an edge case or error case? I would consider edge cases to be valid cases whereas error cases are invalid cases. I do agree though that both have to be caught \$\endgroup\$ – thadeuszlay Apr 9 at 7:39
  • \$\begingroup\$ I'd argue it's an edge case. Rotating 7 times when you only have 6 elements isn't efficient, but it's not non-sensical. \$\endgroup\$ – TheDancingCode Apr 9 at 10:57
  • \$\begingroup\$ @TheDancingCode code updated. \$\endgroup\$ – thadeuszlay Apr 9 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.