Taro Logo

Display Table of Food Orders in a Restaurant

#14 Most AskedMedium
Topics:
ArraysStrings

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders.

Return the restaurant's “display table”. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] 
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito". 

Example 2:

Input: orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
Output: [["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]] 
Explanation: 
For the table 1: Adam and Brianna order "Canadian Waffles".
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".

Example 3:

Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

Constraints:

  • 1 <= orders.length <= 5 * 10^4
  • orders[i].length == 3
  • 1 <= customerNamei.length, foodItemi.length <= 20
  • customerNamei and foodItemi consist of lowercase and uppercase English letters and the space character.
  • tableNumberi is a valid integer between 1 and 500.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Should the customer name be ignored when building the table?
  2. Must food names be listed alphabetically and table numbers be listed numerically?
  3. When a table never ordered a food, should that cell be zero?
  4. Are table numbers stored as text but ordered by their numeric value, so table three comes before table ten?
  5. Should every count and every table number in the result be text, with the first header cell reading Table?

Brute Force Solution

Approach

The distinct foods and distinct tables are collected, foods are sorted alphabetically, and tables are sorted numerically. Each body cell is filled by scanning every order and counting the matches for that table and food. The header begins with Table, and every cell is text.

Here's how the algorithm would work step-by-step:

  1. Collect the distinct food names and the distinct table labels.
  2. Sort the foods alphabetically and sort the tables by their numeric value.
  3. Start the result with a header whose first cell is Table, followed by the sorted foods.
  4. For each table in numeric order, start a row with that table number written as text.
  5. For each food, scan every order and count how many times that table ordered that food.
  6. Append each count as text, then append the finished row to the result.

Code Implementation

def displayTable(orders):
    unique_food_items = set()
    for order in orders:
        food_item = order[2]
        unique_food_items.add(food_item)

    unique_table_numbers = set()
    for order in orders:
        table_number = order[1]
        unique_table_numbers.add(table_number)

    # The header must be alphabetically sorted to define the column order for all subsequent rows.
    sorted_food_items = sorted(list(unique_food_items))
    header_row = ['Table'] + sorted_food_items

    # Table numbers must be sorted numerically to ensure the output rows are in the correct order.
    sorted_table_numbers_as_int = sorted([int(table) for table in unique_table_numbers])

    final_display_table = [header_row]
    for table_number_int in sorted_table_numbers_as_int:
        table_number_string = str(table_number_int)
        current_row = [table_number_string]

        # For each table, we must recount its orders from the original list to build its summary row.
        for food_item_in_header in sorted_food_items:
            count_for_this_food = 0
            for order in orders:
                order_table = order[1]
                order_food = order[2]
                if order_table == table_number_string and order_food == food_item_in_header:
                    count_for_this_food += 1
            current_row.append(str(count_for_this_food))
        
        final_display_table.append(current_row)

    return final_display_table

Big(O) Analysis

Time Complexity
O(t * f * n) – Let n be the number of orders, t the number of distinct tables, and f the number of distinct foods. Finding the distinct labels scans the orders once. Sorting the tables and foods is smaller than the cell work when every cell is filled by a full scan. Each of the t times f cells walks all n orders, and that product is O(t * f * n), which is the total time.
Space Complexity
O(t * f) – Let t be the number of distinct tables and f the number of distinct foods. The result has one header plus one row per table, and every row has one cell per food plus the table label. That output occupies O(t * f) cells. The sets of labels are no larger than the output. The extra space is O(t * f).

Optimal Solution

Approach

Orders are tallied once into a count for each table and food, while the distinct foods and tables are collected. Foods are sorted alphabetically and tables numerically. Each result cell is then a lookup of the already computed count, written as text under a header that starts with Table.

Here's how the algorithm would work step-by-step:

  1. Walk the orders once, recording each food, each table, and the count of that pair.
  2. Sort the foods alphabetically and sort the tables by numeric value.
  3. Start the result with a header whose first cell is Table, followed by the sorted foods.
  4. For each table in numeric order, start a row with that table number written as text.
  5. Look up the stored count for that table and each food, using zero when the pair never occurred.
  6. Append each count as text and append the finished row.

Code Implementation

def display_table(orders):
    # Using sets is an efficient way to find all unique food items and table numbers.
    all_food_items = set()
    all_table_numbers = set()

    for customer, table_number_string, food_item in orders:
        all_food_items.add(food_item)
        all_table_numbers.add(int(table_number_string))

    sorted_food_items = sorted(list(all_food_items))
    sorted_table_numbers = sorted(list(all_table_numbers))

    header_row = ['Table'] + sorted_food_items
    display_table_result = [header_row]

    # A map is needed to quickly look up order counts for a given table and food item.
    table_food_counts = {}
    for customer, table_number_string, food_item in orders:
        if table_number_string not in table_food_counts:
            table_food_counts[table_number_string] = {}
        
        table_food_counts[table_number_string][food_item] = table_food_counts[table_number_string].get(food_item, 0) + 1

    # Iterate through sorted tables to construct each row in the correct order.
    for table_number in sorted_table_numbers:
        table_number_string = str(table_number)
        current_row = [table_number_string]
        current_table_orders = table_food_counts.get(table_number_string, {})
        
        # Iterate through the sorted food items to maintain column consistency.
        for food_item in sorted_food_items:
            count = current_table_orders.get(food_item, 0)
            current_row.append(str(count))
        
        display_table_result.append(current_row)

    return display_table_result

Big(O) Analysis

Time Complexity
O(n + t * f + t log t + f log f) – Let n be the number of orders, t the number of distinct tables, and f the number of distinct foods. The first pass reads every order once, which is O(n). Sorting tables and foods adds O(t log t + f log f). Writing the header and the body visits every output cell, which is O(t * f), and each cell is a direct lookup. Adding those parts gives O(n + t * f + t log t + f log f).
Space Complexity
O(n + t * f) – Let n be the number of orders, t the number of distinct tables, and f the number of distinct foods. The tally can store one count per order in the worst case, which is O(n). The printed table has O(t * f) cells. Both are kept at the same time. The extra space is O(n + t * f).

Edge Cases

There is only one order
How to Handle:
The header lists Table and that one food, and the single body row shows a count of one.
The same table orders the same food more than once
How to Handle:
Those orders add together in that cell.
A table never ordered one of the foods
How to Handle:
That cell is zero.
Table numbers arrive out of numeric order
How to Handle:
They are sorted numerically, so three appears before ten.
Food names differ only by letter case or spacing
How to Handle:
They stay distinct and are ordered alphabetically as written.
0/86 completed