Show all chains per user

Question

Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it.

You have a chains of reservations from AirBnb:

reservations:[
    {user = 1, res_id = 1001, checkin = 100, checkout = 101},
    {user = 2, res_id = 1002, checkin = 104, checkout = 105},
    {user = 1, res_id = 1003, checkin = 101, checkout = 103},
    {user = 3, res_id = 1004, checkin = 104, checkout = 105},
    {user = 3, res_id = 1005, checkin = 105, checkout = 107},
    {user = 4, res_id = 1006, checkin = 106, checkout = 108},
    {user = 4, res_id = 1007, checkin = 108, checkout = 110},
    {user = 4, res_id = 1008, checkin = 108, checkout = 109},
    {user = 4, res_id = 1009, checkin = 110, checkout = 112},
    {user = 4, res_id = 1010, checkin = 109, checkout = 113},
];

where all res_ids are unique and check_out is always bigger than check_in for a reservation.

We name a chain something like:

[checkin = 1, checkout = 3], [checkin = 3, checkout = 5].

If there are no two reservations connected then no chain. We are interested only in reservation chains, two or more reservations connected by checkin/checkout. Since check_out is always bigger than check_in for a reservation, there will be no cycles.

My task was to find all the chains per user. In the example from above the chains would be:

Example: { 1: {{1001, 1003}}, 3: {{1004, 1005}}, 4 : {{1006, 1007, 1009}, {1006, 1008, 1010}} }

In fact, I do not need the users, only the list would work too.

{ {1001, 1003}, {1004, 1005}, {1006, 1007, 1009}, {1006, 1008, 1009}}.

In case the chains were not overlapping I solved it by using sorting based on checkin and checkout. It worked. However, when the reservations were overlapping I had no idea.

I put here an example where they are overlapping.
I tried using a stack, something similar to the minimum number of knight moves to reach coordinate (x, y) from (0, 0) but with no success as number of top level are not one after the other. Any suggestions?

Answer 1

I am assuming that the question is asking for maximal chains. (It's not too difficult to modify the below procedure to get all possible chains)

Below is the step by step approach.

1. It is trivial to group the the given data by users (can use sorting or a hash table on the user id). Now, we can find the chains for each user separately. (All the next steps are at a per-user level)
2. Map all the checkin and checkout timings (in sorted order) to a list of integers 1,2,....,n. Let us call this MAPPING. Let us also store an inverse to this mapping, TIME. First mapping can be stored using an hashtable/BST and the inverse mapping can stored using an array.
3. Create a list (of lists) R of size n, where R[i] stores all the reservations with checkin at TIME[i].
4. Now create a list (of lists) L of size n, where we will store all the chains starting at TIME[i] in L[i].

 5. You can fill L by iterating i from end(n) to start(1)
    a. For each reservation res at R[i]:
           for each chain ch at L[MAPPING[res.checkout]]:
               L[i].append({current_res_id,ch})
           if(L[MAPPING[res.checkout]] is empty)
               L[i].append({current_res_id})
    b. Remove all chains at L[i] that are of a smaller length than the largest one at L[i]

Now, your maximal chains will be a part of the array L and you should not have much difficulty filtering them out. You can mark the chains that are part of a larger chain during the above procedure and ignore them.