Restaurant order summary

Prompt

Given an array of order objects for a restaurant, each with a table number and a list of ordered items, write a function that returns an object mapping each table number to a summary of how many times each item was ordered at that table.

Example 1

Input:

const orders = [
  { table: 1, items: ["burger", "fries"] },
  { table: 2, items: ["burger", "burger", "fries"] },
  { table: 1, items: ["salad"] },
  { table: 2, items: ["fries"] }
];

> orderSummary(orders)

Output:

{
  1: { burger: 1, fries: 1, salad: 1 },
  2: { burger: 2, fries: 2 }
}
// or, string output format:
"Table 1 ordered 1 burger, 1 fries, and 1 salad. Table 2 ordered 2 burgers and 2 fries."

Approach: Horizontal scan

1. Initialize the object to return. I'll refer to it as returnedObject for now.
2. Loop through the orders array. For each of these items:
   1. Check if the table number exists as a key within returnedObject
      • If not, initialize returnedObject[table] with the value of an empty object, {}
   2. Loop through the items array. For each of these items:
      1. Check if that item exists as a key within returnedObject[table]
         • If not, initialize returnedObject[table][item] as 0
      2. Add 1 to returnedObject[table][item].
3. Return returnedObject.

This approach, where the algorithm processes entire rows of data sequentially, is called a horizontal scan or full table scan. My process was to brute force this originally with a couple of for Loops and a helper function, and then to clean things up with the .reduce method.

Solution

function orderSummary(orders) {
  if (!Array.isArray(orders) || orders.length === 0) {
    throw new Error("Invalid or empty orders array provided.");
  }
  return orders.reduce((acc, order) => {
    const { table, items } = order;
    // Initialize the table's summary if it doesn't exist
    acc[table] = acc[table] || {};

    // Iterate through the items and count them
    for (const item of items) {
      acc[table][item] = (acc[table][item] || 0) + 1;
    }
    return acc;
  }, {});
}

Big O of this solution

The Big O for time complexity is O(N +M), where N is the total number of orders and M is the total number of individual items across all orders. This is simply the sum of the outer loop over the orders array and the inner loop over each items array. The operations inside of the loop (property access, initialization, and addition) all happen in constant time, so they don't affect the outcome too much. However, as you might imagine if we wind up with a lot more tables or a wider variety of food items able to order, those permutations can start to stack up.