1) Finish writing the below me

Google Interview Question for Backend Developers

of 0 votes

2
Answers

1) Finish writing the below method: bookReservation(Reservation reservation)

2) You are free to add, modify, etc the following classes and method

import java.time.Duration;
import java.time.LocalTime;
import java.util.List;
import java.util.Map;

// Your goal is to write business logic for a very simple Restaurant booking system
// You are encouraged to refactor exisiting code, create other classes, write helper methods etc
// You also need to make sure that the implementation works correctly


class Reservation
{
    public String name;
    public int partySize;
    public LocalTime startTime;
}

class Table
{
    public int tableNumber;
    public int maxPartySize;      
}

class Restaurant
{
    public List<Table> tables;   
    public LocalTime openTime;
    public LocalTime closeTime;
    public Map<Integer, Duration> reservationDurationsPerPartySize;
    
    // Returns a Table if Reservation could be booked, null otherwise
    // Booking rules: 
    // 1) Reservation could be made only when the Restaurant is open.
    // 2) Only one Reservation can be seatted a Table at any time.
    // 3) Reservation can be seatted only at a Table of the same or a bigger size.
    // 4) Reservation should stay on the same Table for the whole Duration.
    // 5) Reservation Duration is determined by PartySize.
    public Table bookReservation(Reservation reservation) {
          //fill this method
}

Email me when people comment.

An error occurred in subscribing you.

Country: United States

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

public Table bookReservation(Reservation req) {
  Table ret = null;
  if(req.startTime.between(openTime, closeTime) && 
     req.startTime.plus(reservationDurations.get(req.startTime)).between(openTime, closeTime)) {
    int minDifference=Integer.MAX_VALUE;
    for(Table t : tables) {
      if(!t.isTaken() && t.maxPartySize - req.partySize < minDifference) {
        minDifference = t.maxPartySize - req.partySize;
        ret = t;
      }
    }
  }
  ret.markTaken(); // so that future requests don't use this table
  return ret;
}

Although, I wouldn't use a List<> datastructure to store all the tables, since they are constantly being allocated and de-allocated based on requests. I'd use a hash map with it's key as party size, and value as a list of tables that serve that party size.

Every time we get a request to make a reservation, we can do binary search on the keys of this hashmap using the request partySize. Then we pull out the first available table of that size and return. If this is the last such table, we remove this key from the hashmap, so that any further requests will attempt to use a table of larger size. Similarly, as tables become available again, we can just add it back to the hash map using the table's maxPartySize. Such an implementation exists in Java, for example. It's called TreeMap.

- Killedsteel February 20, 2017 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Shouldn't you check if t.maxPartySize - req.partySize > 0
if t.maxPartySize - req.partySize = -1, if could also meet the condition
t.maxPartySize - req.partySize < minDifference

- joyfeng February 24, 2017 | Flag Reply

CareerCup

Google Interview Question for Backend Developers

Books

Videos

Resume Review

Mock Interviews