2
$\begingroup$

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?

$\endgroup$
15
  • $\begingroup$ What is the rule to handle overlaps ? $\endgroup$ May 5 at 13:23
  • $\begingroup$ what do you mean the rule? No rule, there can be overlaps. As I was explained, this can happen if somebody reserves for many people. This can happen. $\endgroup$
    – Andrei T
    May 5 at 13:25
  • 1
    $\begingroup$ For a reservation, is checkout greater than checkin? Must res_ids be increasing/distinct in a chain? Or we are supposed to ask these clarifications during the interview? I am concerned whether there might be cycles. For example, {user = 5, res_id = 1020, checkin = 100, checkout 101 }, and {user = 5, res_id = 1021, checkin = 101, checkout 100 }. There is an infinite chain, 5: {{1020, 1021, 1020, 1021, ...}}. $\endgroup$
    – John L.
    May 5 at 14:16
  • $\begingroup$ How about a directed graph in which nodes represent time (100, 101...) and edge between node A to node B exists with label=user_id if user_id checked-in at time A and checked-out at time B. Each chain of a user is then a map from user_id to a 2d array with size(n, 2). To get the chains for each user run DFS, for each edge of user_id you encounter, append [checkin, checkout] to the respective chain? $\endgroup$ May 5 at 15:08
  • $\begingroup$ @JohnL, yes check_out is bigger than check_in. $\endgroup$
    – Andrei T
    May 5 at 15:13

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.