Question

Google | Interview experiences | SDE | 2023 | Set-67

Answer 1

The question was to book a table in restaurants. Its LC Medium with a LC hard follow-up. This is like a design question. He asked me which all APIs I provide and what data structures. Then he said he is satisfied the way I designed but don't need that much information. So we will proceed with adding 3 interfaces: add a booking, delete a booking, assign a booking.
I used a map with customer size and vector of booking ids. When a table is free,
get lower_bound of map which will return the vector booking ids.
If the map entry size is greater than table size, return the prev map entry.
Pop the front of vector and return it.

 

This solution was accepted and he asked me to proceed with coding. The follow-up was how to do if table size is also configured. I suggested to keep an availability list and free list as well. So we can assign the best one based on the customer size.

 

In this round as well, we didn't discuss about time complexities. There was enough time at the end but I forgot to mention about time complexity and he too didn't ask about it.