Google L3 | Full Question
Anonymous User
6045

Had my second onsite interview. The Interviewer was from Warsaw. The question was only mentioned verbally. However, from what I can recall, it was roughly the following:

Imagine you are responsible for leading a car rental company. You are given a collection of reservation times with the following structure:

struct reservation{
	int id;
	int pickup_time;
	int return_time;
}

Your task is to assing as less cars as possible to the collection of reservations. 
Furthermore, you are tasked with returning the set of time intervals each respective car was used.

Example Input:
Reservations: [[1,4],[2,5],[3,7],[6,9]]

Example Output:
car1 -> [{1,4},{6,9}]
car2 -> [{2,5}]
car3 -> [{3,7}]

Constraints and questions, which I asked:
	- Is the collection of reservations sorted? -> No
	- Are there any rules according to which the available cars should be assigned? -> No, just pick any arbitrary car, which is available

Provided a sweep line solution to solve this question. The interviewer seemed satisfied and the solution passed my debugging test cases.

Comments (10)