TopcoderArchive
Archive
Algorithm problem

RestaurantQueue

Problem statement, definition, constraints, and public examples.

Problem Statement

In restaurants, people wait for food in queues. There is a meal service that acts as a bridge between people in the queue and the restaurant's kitchen. In this problem, you need to simulate the work of such a service.

Given class MealService:

Represents the meal service that acts as a bridge between the people queue and the kitchen.

public abstract class MealService {  

  /**
   *  Call this to initialize the meal service before using it.
   *
   *  @param restaurantName is a String representing the name of a restaurant.
   */
  public final void init(String restaurantName);
  
  /**
   *  Gets the Kitchen the instance serves.
   *
   *  @return Kitchen object associated with this meal service.
   */  
  public final Kitchen getKitchen();
  
  /**
   *  Use this method to save the information about a 
   *  dish served by this meal service.
   *
   *  @param foodName is a String representing the name of a dish.
   */
  public final void addFood(String foodName);

  /**
   *  Kitchen calls this method when the preparation
   *  of the currently ordered dish is complete.
   */
  public abstract void foodDelivered();
  
  /**
   *  Each client in the queue calls this method to get a dish.
   *
   *  The implementation must order a dish at the kitchen and block the current
   *  thread until the dish is prepared. The implementation must call addFood with
   *  the name of the dish prepared for this client.
   */
  public abstract void giveMeTheFood();
  
  /**
   *  Gets a summary representation of the all food served by this service.
   * 
   *  @return A summary integer of food added to this service.
   */
  public final int getFoodRepresentation();
}

Given class Kitchen:

Represents a kitchen at a restaurant. The kitchen is associated with a MealService object. Before the meal service can serve a dish to a client, it must first get it prepared in the kitchen.

public class Kitchen {
  /**
   *  Creates new kitchen given the name of a restaurant
   *  and an instance of MealService.
   *
   *  @param restaurantName is a String representing the name of a restaurant.
   *  @param srvc MealService object associated with the kitchen.
   */
  Kitchen(String restaurantName, MealService srvc);
  
  /**
   *  This method should be called by the meal service
   *  when it needs a dish for a client.
   *
   *  The preparation of a dish takes some time (at most 30 milliseconds).
   *  When the preparation is complete, the kitchen notifies the meal
   *  service by calling foodDelivered(). The preparation 
   *  of food is done in a separate thread and does not block the thread
   *  that called this method.
   *
   *  Note the kitchen can't prepare two or more dishes at the same time.
   *
   *  To simplify this problem, assume that a client cannot order
   *  a specific dish and some random dish is prepared in the kitchen.
   *  The kitchen knows the name of the dish immediately after
   *  this method is called and this name is returned.
   *
   *  @return The name of the dish that will be prepared.
   */
  public synchronized String getAFood();
}

Given class ClientsQueue:

Represents a queue of clients coming to a restaurant.

public class ClientsQueue extends Thread {
  /**
   *  Creates an instance of ClientsQueue given the name of a restaurant
   *  and an instance of MealService.
   *
   *  Once the queue is created, it immediately starts working. Each queue can have
   *  between 1 and 20 clients, inclusive. Each client calls srvc.giveMeTheFood()
   *  after coming to get food. After the food is prepared and served to a client,
   *  the next client requests food, and so on.
   *
   *  There can be a delay of a maximum of 30 milliseconds between between the moment
   *  when giveMeTheFood() completes for one client and when it's called by the
   *  next client.
   *
   *  @param restaurantName is a String representing the name of a restaurant.
   *  @param srvc is a MealService that will serve the queue.
   */
  ClientsQueue(String restaurantName, MealService srvc);
  
  /**
   *  When this method is called from a thread, the thread blocks
   *  and waits until all people from this ClientsQueue receive their
   *  ordered meals.
   */
  public synchronized void sleepUntilFinish();  
}

CUSTOM MEALSERVICE

Extend the class MealService and implement all its abstract methods. Ensure that your implementation satisfies the previous criteria.

DEFINITION

You must define public class RestaurantQueue with public method int getNames(String restaurantName).

To implement getNames, create an instance srvc of CustomMealService. Create an instance of ClientsQueue by passing restaurantName and srvc to ClientsQueue(String, MealService).

Wait until all clients in the queue are served using sleepUtilFinish(). Return srvc.getFoodRepresentation().

Definition

Class:
RestaurantQueue
Method:
getNames
Parameters:
String
Returns:
int
Method signature:
int getNames(String restaurantName)
(be sure your method is public)

Constraints

  • restaurantName will contain between 1 and 50 characters, inclusive.
  • Each character of restaurantName will be a letter ('a' - 'z', 'A' - 'Z').

Examples

  1. "HashMap"
    Returns: 274383
    There are 2 people in the queue for this restaurant. They will get food with names QYDMcPpZamWv and F, respectively.
  2. "case"
    Returns: 245122
    There are 4 people in the queue for this restaurant. They will get food with names USVEdsSxn, CQAIzxCuJDSD, lsvKcdPBDVyul and xV, respectively.
  3. "else"
    Returns: 615091
    There are 5 people in the queue for this restaurant. They will get food with names UHX, FXo, oCZHeTwrAwINumEMcpBM, zSXqiqplQMn and VjHZurDwzamqrRlAEHL, respectively.
  4. "Bokachi"
    Returns: 578641
    There are 6 people in the queue for this restaurant. They will get food with names sLoCRJwxA, Hg, dmaZNurJad, RZhW, LqvGVBOZAKqFZbOKn and k, respectively.
  5. "Petrarka"
    Returns: 731937
    There are 12 people in the queue for this restaurant. They will get food with names BPzl, wKljVFVZ, hYcmMVZ, isrGhKVyS, jlULeenFGZKHEmUDQwG, NeXIjnLdcDN, bMKdwRrMvvWPBlebuibJ, ZZrDuDhrld, tCUBPBgvMLbWPLKE, CkBlRr, BOmdiyazLHitt and lMxbycKFbNNyQvP, respectively.
Back to all problems