I often get asked: how do I practice for interview code exercises, and do something useful at the same time? Here is an idea.
COVID-19 had severely affected cinemas and theatres. As of June 2020, most countries will allow them to reopen under some restrictions. A frequent restriction is to disallow customers on consecutive seats, unless they belong to the same household.
Write a program that allocates cinema seats so that there is a minimum of one empty seat between households. Here are the inputs:
- The number of rows.
- The number of seats per row.
- The households map. In the following example, ten people are going to the cinema on their own, five pairs and three households of four people each.
1 -> 10 2 -> 5 4 -> 3
As most interview coding exercises, requirements are not fully defined; in an interview setting, you would be encouraged to ask questions such as:
- What if it’s not possible to fit that many people in the cinema?
- How do I represent the output? Would a list of the occupied seat such as A1, A3, B1 be ok?
Equally, think about follow up questions that an interviewer would typically ask:
- Does your algorithm guarantee that the distribution is optimal, i.e., we fit as many people as possible?
- If the cinema is not full, can you re-design your solution to maximise the distance between cinema-goers? This question would normally trigger a discussion on what the interviewer means by maximise the distance.
- How do you adapt your solution for the more generic case where rows may have different number of seats?
When you finish, package your solution and email it to your local cinema and theatre. Stay safe and be kind to each other.