3-Topping Pizzas McKinsey SQL Interview Question

You’re a consultant for a major pizza chain that will be running a promotion where all 3-topping pizzas will be sold for a fixed price, and are trying to understand the costs involved.

Given a list of pizza toppings, consider all the possible 3-topping pizzas, and print out the total cost of those 3 toppings. Sort the results with the highest total cost on the top followed by pizza toppings in ascending order.

Break ties by listing the ingredients in alphabetical order, starting from the first ingredient, followed by the second and third.

P.S. Be careful with the spacing (or lack of) between each ingredient. Refer to our Example Output.

Notes:

• Do not display pizzas where a topping is repeated. For example, ‘Pepperoni,Pepperoni,Onion Pizza’.
• Ingredients must be listed in alphabetical order. For example, 'Chicken,Onions,Sausage'. 'Onion,Sausage,Chicken' is not acceptable.

Table:

Example Input:

Example Output:

Explanation

There are four different combinations of the three toppings. Cost of the pizza with toppings Chicken, Pepperoni and Sausage is $0.55 + $0.50 + $0.70 = $1.75.

Additionally, they are arranged alphabetically; in the dictionary, the chicken comes before pepperoni and pepperoni comes before sausage.

The dataset you are querying against may have different input & output - this is just an example!

We have developed 4 solutions to solve this question:

1. Using INNER JOIN
2. Using CROSS JOIN
3. Using RECURSIVE CTE
4. USING Array function

Solution #1: Using INNER JOIN

Step 1: Join the tables thrice horizontally

First, we create a table where the ingredients are displayed in horizontal style 3 times. That will make the concatenation easier.

Important tip: Instead of matching the tables on columns using the equal sign , we use the less than sign to ensure that:

1. There is no duplication of the ingredients across each row.
2. The ingredients are arranged in an alphabetical manner from left to right.

Showing the output of the first 3 rows:

Step 2: Combine pizza toppings and add the ingredients

Next, we will design the table based on the required output, which is a 3-topping combination and total ingredient cost.

To combine the 3 toppings into a single string, we can either use the function or pipe .

We'll use the function for this question. As for the total ingredient costs, just add them up using the plus sign as you would use a calculator.

Step 3: Order the output accordingly

Finally, order the output by the highest cost at the top and to break ties, sort the pizza ingredients in ascending order (it also means sort in alphabetical order.

---

Solution #2: Using CROSS JOIN

This solution by @Prathamesh Barane is so ingenious that we could not help but use it as our official solution.

Let's split the problem into 3 slices.

1. Get every possible combination of 3-topping pizzas
2. Discard rows with duplicate toppings and arrange them according to alphabetical order
3. Order output by lowest to highest cost

Step 1: 3-Topping Combinations

Using a neat trick with , we're joining the table horizontally 3 times to obtain an output with 3 columns of the .

Output of randomly selected 5 rows:

Step 2: Discard duplicates and arrange them alphabetically

Our idea is to concatenate the topping names across a single row, however, in the above output, we have rows where the topping names are duplicates of each other (i.e. [Pepperoni, Pepperoni, Pepperoni], [Pepperoni, Pepperoni, Sausage]).

To ensure that the topping names across a row are different, we use comparison operators in the clause.

Using for string values is a handy trick to prevent duplication. Not only that, remember the question's requirement of "break ties by listing the ingredients in alphabetical order"?

Well, by writing , it ensures that the second topping's name () comes after first topping's name (). Isn't this cool?

Step 3: Return desired output

To retrieve the combination of 3-topping values in a single cell, we can use function and then add up all the ingredient's cost.

---

Solution #3: Using RECURSIVE CTE

Using the recursive Common Table Expression (also known as recursive CTE), we will find every possible combination of 3-toppings pizzas.

The term recursive CTE refers to a subquery that references itself. There are essentially 3 parts to it:

1. Non-recursive query (AKA the base query or anchor),
2. Recursive query, and
3. Termination condition

Note that strictly speaking, this process is iteration not recursion, but RECURSIVE is the terminology chosen by the SQL standards committee; see PostgreSQL Documentation.

Here is how it is structured in PostgreSQL:

For our problem, let's start by enclosing the non-recursive query in the recursive CTE.

Displaying randomly selected 4 records in the output:

A newly created column is introduced which serves as a numerical representation of the number of toppings each pizza has. Since each of these toppings in the output is a separate item, the topping number would equal to 1. As more toppings are placed onto the pizza, this will increase incrementally.

We will use this non-recursive query (or the anchor) and iterate through to create different combinations of toppings using a recursive CTE.

Let's incorporate the recursive query inside this CTE – this is the part that makes it recursive.

Note that a recursive CTE must have all 3 of the elements in place for it to work.

The first requirement of is:

• Each operation within the must produce result sets with an identical number of fields and data types.
• Due to syntax limitations in PostgreSQL, we have to explicitly cast the columns and AS and datatypes in the non-recursive query, respectively.
  • PostgreSQL considers (before casting) and (after casting) to be two different entities.
  • The field in the non-recursive query is of the datatype as defined in the table.
  • After casting, the in the recursive query becomes a data type.
  • Similarly, we cast to as well.

Note the termination condition in the recursive query: . It compares the topping names between the non-recursive and recursive query and prevents the same topping names from showing up multiple times in the 3-topping combination. This recursive query will continue to run until the clause condition is met.

Let's interpret the clause of the recursive query:

• The function is used to combine two or more toppings.
• The cost of the new topping will be added to the expenses of the prior toppings.
• When a topping is put on a pizza, the topping counter () will be incremented.

The recursive CTE will continue to run as more toppings are introduced until all possible combinations have been found.

Each new result is added to the preceding result set using the operator.

Showing 5 records for toppings Pepperoni, Extra Cheese, Sausage and Chicken.

We can filter for pizzas with 3 toppings, or :

Output:

Step 2: Arrange toppings alphabetically

We'll use the following steps to arrange each set of pizza toppings alphabetically:

1. Divide the toppings up into multiple rows.
2. Sort them alphabetically and combine the toppings from the same group.

We will split the toppings using the function . It splits the values in form of rows based on the specified delimiter. Let's call this column .

Showing how toppings are split for a pizza with Sausage, Pepperoni, Chicken toppings.

The values in the column will then be sorted and combined to restore their previous groupings.

One function, , can do both of these things! joins sets of strings into a single string. The inner clause then sets the order of the concatenated results.

The output is then arranged in descending order of total cost, followed by the names of the toppings.

We've reached the end of this long road, and our final query is ready :)

---

Solution #4: Using Array Function

Array functions can also be used to sort toppings.