[Solution]Problem 19: Help Couples sit together [Spotify]
Recursion. Branching, Combinatorics, Couples, Rearragment
Problem
This problem was asked by Spotify.
There are N
couples sitting in a row of length 2 * N
. They are currently ordered randomly but would like to rearrange themselves so that each couple's partners can sit side by side.
What is the minimum number of swaps necessary for this to happen?
Brute Force
The clearest thing we can do here is to create our brute force solution. Brute force solutions can point us in relevant directions to come up with the optimal solution.
Suppose the couples are labeled (0, 1), (2, 3), (4, 5), ...
,(n-1, n) and they are sitting on consecutive couches in the following arrangement: [(0, n), (1, n-3), (2, n-6), ...]
.
Then for the first pair, there are two ways to make a swap such that a couple will end up together on the first couch. That is, we can either swap person 0
with person n-3
, or swap person n
with person 1
.
For either option, we have possibly two options for creating a couple on the second couch, and then possibly two options for creating a couple on the third couch, and so on. Even though there are eventual cases where we have a couple already sitting on a bench, we will on average have two options/unordered pair. This concept is called the branching factor. The branching factor is the number of children at each node, the outdegree. Note that if this value is not uniform, an average branching factor can be calculated. We use branching factors to calculate the time and space complexity of our algorithms (think of how).
In our code, we could recursively go through each of these options, tracking the total number of swaps, and at the end return the minimum. Write this code out and post in the comments below for a code review. We will not write it out, because in your interviews you should ideally not waste time on such solutions if you have a better one. You want to let the interviewer know that you know the idea behind the brute force, mention the time and space complexity, and move on to a better solution.
In our case, this would take O(2^N)
, since we branch off into two paths at every couch. We also use O(2^N)
space, since each time we branch we create two new rows.
A Better Solution
Surely there’s a better solution than just brute-forcing it. If you’re anything like me, you might try some combinatorial mathematics. However, given that we’re dealing with random configurations, this will not work. The second option would be attempting to write Monte Carlo simulations. This approach is viable in Data Science, but generally not suggested in coding interviews
Let’s take a look at our solution. You will notice one thing: At worst, one swap will fix one couple as in (0, 1), (n-1, n-3),…. We can’t do any better than choosing the first person from the pair, finding the position of their partner, and swapping the second person with their partner. On average this will fix one couple’s seating. In rare cases, two couples will be fixed.
Greedy algorithms are simple, intuitive algorithms that are used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem. However, since they don’t look ahead, they might be short-sighted and miss out on the best ways.
In our case, greedy algorithms will allow us to be optimal because of the properties we derived. So what would our algorithm look like? What kind of time/space complexity will it have? Think for a second before proceeding.
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.