2023 Kakao New Graduate Coding Test: Explanation of the Hotel Reservation Problem Applying Memory Fragmentation Concepts

The 'Hotel Reservation' problem in the second round of the 2023 Kakao new graduate coding test is an optimization problem that applies the concept of memory fragmentation during the process of accepting group reservations and assigning rooms. It requires a strategy to resolve situations where reservations must be rejected due to a lack of contiguous space, even when there are sufficient vacant rooms.

Evaluation Criteria and Strategy

The score consists of accuracy, efficiency, and penalties. Accuracy is determined by whether the utilization target is met (Scenario 1: 60%, 2: 75%), while efficiency results in a maximum difference of 10 points based on response speed. The most critical aspect is minimizing penalties, particularly since rejecting or failing to assign reservations with a large number of rooms incurs significant penalties; avoiding these is key to increasing the total score.

Key Approaches

Candidates solved the problem by combining various strategies, such as:

• First-fit: The simplest method, assigning rooms sequentially starting from the lowest-numbered vacant room.
• Priority-based response: Utilizing the response deadline to prioritize reservations with a large number of rooms and quickly responding only to confirmed reservations.
• Best-fit: Finding and assigning contiguous space similar in size to the room requirement to minimize the remaining vacant space (fragmentation) after assignment.
• Grouping: Assigning reservations with similar specifications (number of rooms, duration, etc.) to specific floors or zones to prevent fragmentation.