[Solution]Problem 21: Rotate List by k elements[Facebook/Meta]
Lists, Rotation, Array Functions, Pattern Finding
Problem
This problem was asked by Facebook/Meta.
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?
Step 1: Simple Solution
What is the simplest solution we can come up with? We could rotate the list by one element, and call this rotation k times. This would look like this:
def rotate_list(list):
##if you're a beginner, implement this for practice. For more experienced people this should be a trivial problem.
def soln(list, k):
for _ in range(k):
list=rotate(list)
return list
For those who want their rotation, code reviewed just leave the solution in the comments (or DM me). I’ll give you feedback on it.
Proceeding with the solution, it should be fairly clear that this solution would be O(n*k) time and constant space.
So now we should think of how to improve upon this solution.
Step 2: Pattern Finding
One of the goto problem-solving techniques is pattern finding. The reason this can be very effective is that we can start pretty quickly. Unlike some other problem-solving techniques, we can start running simple simulations as soon as we have the required details on hand. And you’d be shocked how often simple simulations are all we need. So let’s look at how we can effectively use this amazing technique.
The first thing we will do is take a simple example. Let’s take a list= [1,2,3,4,5]
for k=0 our output is [1,2,3,4,5]
for k=1 our output is [2,3,4,5,1]
for k=2 our output is [3,4,5,1,2]
for k=3 our output is [4,5,1,2,3]
for k=4 our output is [5,1,2,3,4]
for k=5 our output is [1,2,3,4,5]
Notice anything? To me, the most obvious pattern is that our code has a periodicity. Periodic functions are functions that repeat at regular intervals. The intervals with which they repeat are called their period. The below function repeats after T units (in the x axis). Therefore, it has a period of T
Why is this important? Imagine we were dealing with really large n and k. Instead of looping through the whole thing, we can simply run our solution a smaller number of times. This kind of optimization is crucial when it comes to the day-day of software engineering.
Looking at the structure of the solution, it is clear that our periodicity is n (the length of the list). Therefore, when we start our solution we should set our k to k%n. If this doesn’t make sense, feel free to reach out, and I will create a full mathematical breakdown. This will be helpful to us for optimization.
Now let’s get back to problem-solving. Can we notice any other patterns that can be useful? Let’s copy our basic example, for convinience:
list= [1,2,3,4,5]
for k=0 our output is [1,2,3,4,5]
for k=1 our output is [2,3,4,5,1]
for k=2 our output is [3,4,5,1,2]
for k=3 our output is [4,5,1,2,3]
for k=4 our output is [5,1,2,3,4]
for k=5 our output is [1,2,3,4,5]
Step 3: Looking at the elements
When we see the elements, and particularly how they shift you will notice something interesting. After shifting by k elements our list looks like this: lst[k:] + lst[:k]. For those unfamiliar with list notation:
lst[k:] returns a sublist of all elements starting from the kth element upto (including) the last element. So lst[n-3:] would return the sublist [lst[n-3],lst[n-2], lst[n-1]]
lst[:k] returns a sublist of all elements up to (not including) k. lst[:3] would give you [lst[0], lst[1], lst[2]]
Doing some quick checks, it’s clear that our pattern is valid. And this makes on an intuitive level. Rotating a list by k elements is basically taking the last k elements of the elements, and moving them upfront. Our new pattern does exactly that.
Depending on which language you’re using, this would be it. However, many languages will not accept this as a solution. So for their sake, let’s see our solution to the end. Coming up with a solution will also improve our coding + problem-solving skills.
So how can we get the new rotated list without relying on language-specific implementations or creating new copies? This is where we must get creative. The following section is extremely important understanding this approach can help you in many similar problems.
Step 4: Identify Pivot
One of the clear insights we can gain by splitting into multiple sublists is the following: we can use k (k%n) as our pivot. Furthermore, we need to apply some functions on the sublists generated from our pivot to get our output. Now let’s look into the details.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.