Scale Engineer

Display Table of Food Orders in a Restaurant

Med
#1312Time: O(N * (T + U)), where N is the number of orders, T is the number of unique tables, and U is the number of unique food items. The final pass to populate counts dominates, as each of the N orders requires searching through T tables and U food items.Space: O(T * U + U*L_f + T*L_t), where T is the number of unique tables, U is the number of unique food items, and L_f/L_t are average string lengths. The dominant term is `O(T * U)` for storing the result table.2 companies
Algorithms
Sorting
Data structures
ArrayHash TableStringOrdered Set
Companies
J.P. MorganNordstrom

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves multiple iterations over the input data. First, it collects all unique food items and table numbers. Then, it sorts them to establish the structure of the output table. Finally, it iterates through the orders again to populate the counts, using inefficient linear searches to find the correct row and column for each order.

Algorithm

  • Step 1: Collect Unique Items:
    • Create a HashSet for food items and another HashSet for table numbers.
    • Iterate through the orders list once to populate both sets with all unique values.
  • Step 2: Sort Headers and Rows:
    • Convert the food item set to a List and sort it alphabetically. This list will form the column headers.
    • Convert the table number set to a List, parse the string numbers to integers, sort them numerically, and store the sorted list.
  • Step 3: Initialize Result Table:
    • Create the final result List<List<String>>.
    • Add the header row, which consists of "Table" followed by the sorted food items.
    • For each sorted table number, add a new row to the result. This row will start with the table number, followed by "0" for each food item count.
  • Step 4: Populate Counts:
    • Iterate through the original orders list a second time.
    • For each order, find its corresponding row and column in the result table by performing a linear search on the sorted table list and sorted food list.
    • Once the correct cell is located, parse its string value to an integer, increment it, and update the cell with the new count as a string.
  • Step 5: Return Result:
    • Return the fully populated table.

Walkthrough

The brute-force method tackles the problem in a straightforward but inefficient manner. It separates the problem into distinct phases: data collection, sorting, table initialization, and data population. The main drawback is the final population step. For every single order in the input, it searches for the correct table row and food column by scanning through the previously created lists of sorted tables and foods. This repeated searching process makes the algorithm very slow as the number of orders, tables, or food items increases.

import java.util.*;import java.util.stream.Collectors; class Solution {    public List<List<String>> displayTable(List<List<String>> orders) {        // Step 1: Collect unique food items and table numbers        Set<String> foodSet = new HashSet<>();        Set<String> tableSet = new HashSet<>();        for (List<String> order : orders) {            tableSet.add(order.get(1));            foodSet.add(order.get(2));        }         // Step 2: Sort headers and rows        List<String> foodHeader = new ArrayList<>(foodSet);        Collections.sort(foodHeader);         List<String> sortedTables = new ArrayList<>(tableSet);        Collections.sort(sortedTables, Comparator.comparingInt(Integer::parseInt));         // Step 3: Initialize result table        List<List<String>> displayTable = new ArrayList<>();        List<String> headerRow = new ArrayList<>();        headerRow.add("Table");        headerRow.addAll(foodHeader);        displayTable.add(headerRow);         for (String table : sortedTables) {            List<String> row = new ArrayList<>(Collections.nCopies(foodHeader.size() + 1, "0"));            row.set(0, table);            displayTable.add(row);        }         // Step 4: Populate counts with linear scans (inefficient)        for (List<String> order : orders) {            String table = order.get(1);            String food = order.get(2);             int rowIndex = sortedTables.indexOf(table) + 1; // Linear scan            int colIndex = foodHeader.indexOf(food) + 1;   // Linear scan             List<String> targetRow = displayTable.get(rowIndex);            int currentCount = Integer.parseInt(targetRow.get(colIndex));            targetRow.set(colIndex, String.valueOf(currentCount + 1));        }         return displayTable;    }}

Complexity

Time

O(N * (T + U)), where N is the number of orders, T is the number of unique tables, and U is the number of unique food items. The final pass to populate counts dominates, as each of the N orders requires searching through T tables and U food items.

Space

O(T * U + U*L_f + T*L_t), where T is the number of unique tables, U is the number of unique food items, and L_f/L_t are average string lengths. The dominant term is `O(T * U)` for storing the result table.

Trade-offs

Pros

  • Conceptually simple and breaks the problem down into easy-to-understand steps.

Cons

  • Highly inefficient due to multiple passes over the data.

  • The final step of populating counts involves linear searches within a loop, leading to a poor time complexity of O(N * (T + U)), which will likely result in a 'Time Limit Exceeded' error for large inputs.

Solutions

class Solution {public  List<List<String>> displayTable(List<List<String>> orders) {    Set<Integer> tables = new HashSet<>();    Set<String> foods = new HashSet<>();    Map<String, Integer> mp = new HashMap<>();    for (List<String> order : orders) {      int table = Integer.parseInt(order.get(1));      String food = order.get(2);      tables.add(table);      foods.add(food);      String key = table + "." + food;      mp.put(key, mp.getOrDefault(key, 0) + 1);    }    List<Integer> t = new ArrayList<>(tables);    List<String> f = new ArrayList<>(foods);    Collections.sort(t);    Collections.sort(f);    List<List<String>> res = new ArrayList<>();    List<String> title = new ArrayList<>();    title.add("Table");    title.addAll(f);    res.add(title);    for (int table : t) {      List<String> tmp = new ArrayList<>();      tmp.add(String.valueOf(table));      for (String food : f) {        tmp.add(String.valueOf(mp.getOrDefault(table + "." + food, 0)));      }      res.add(tmp);    }    return res;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem