[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.
Generally, with the rotation/shifting questions, a common function applied is reversing. Looking at the question from this perspective, what pops out? When we reverse a list, we are swapping elements whose indexes add up to (n-1). For this code, given a value k, we want our 0th element at index n-k, 1th element to end up n-k+1, and the ith element to end up at n-k+i. This pattern holds true for the right sublist (lst[:k]). For the left sublist, our pattern is slightly different. Since we took k elements from the front, the indexes drop by k. So an element at index j is now in index j-k.
We can now leverage this to figure out how we can possibly reverse the sublists into creating our final solution. After a bit of trial and error, we get the following insight: By reversing these subarrays and then reversing the whole array we can effectively rotate the array in linear time and without copying.
Let’s take an example-
List [1, 2, 3, 4, 5] and k = 2.
First reverse from 0 to k:
[2, 1, 3, 4, 5]Then reverse from k to n:
[2, 1, 5, 4, 3]Then reverse from 0 to n:
[3, 4, 5, 1, 2]
Our code would look like this:
def rotate(lst, k):
reverse(lst, 0, k - 1)
reverse(lst, k, len(lst) - 1)
reverse(lst, 0, len(lst) - 1)
def reverse(lst, i, j):
while i < j:
lst[i], lst[j] = lst[j], lst[i]
i += 1
j -= 1Since reversing a list takes O(n) and we do a constant number of reversals (3), this algorithm takes O(n) time.
Final: O(n) time and o(1) space
Bonuses/Promotion (Get Free Stuff)
To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.
For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.
To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75
Thanks for this problem!
this is a great question