A cinema has rows of seats, each with 10 seats (labeled 1-10). Seats are divided into three sections: [1], [2,3,4,5], [6,7,8,9], [10]. A group of 4 people wants to sit together in a row. They can sit in seats [2,3,4,5], [6,7,8,9], or the middle [4,5,6,7]. Given a list of reserved seats, find the maximum number of 4-person groups that can be accommodated.
Companies like LinkedIn and Microsoft use this to test your ability to handle large input sizes ( can be ) using efficient data structures. Since you can't iterate through rows, you must only process rows that have reserved seats. It evaluates your skill in Bit Manipulation and Hash Tables.
This problem uses the Hash Table and Bit Manipulation pattern. For each row that has at least one reservation, you represent the seat occupancy as a 10-bit integer. You check three bitmasks:
0111100000 (seats 2,3,4,5)0000011110 (seats 6,7,8,9)0001111000 (seats 4,5,6,7)
For rows with no reservations, the answer is always 2 groups. For reserved rows, you count how many of these masks can be applied without overlapping with reserved seats.Row 1: Seat 3 is reserved.
The most common mistake is trying to create an array of size , which causes a Memory Limit Exceeded error. Another error is not realizing that a row can fit two groups if the groups don't overlap (seats 2-5 and 6-9). Some might also forget that the middle group [4,5,6,7] is only an option if neither of the side groups can be fully seated.
When is very large but the number of "special" items is small, only store and process the special items using a Map. For fixed-size problems (like 10 seats), bitmasks are the most efficient way to check configurations.