One hungover morning about a year ago a friend and I were having breakfast at a typically terrible cafe in London, trying to prepare for an interview that afternoon. It was the first time we were interviewing candidates for that company and needed to decide on what questions we were going to ask. Most cafes in the UK have set meals but also let you create your own meal from a selection of standard (bacon, eggs, etc.) and not so standard (coleslaw? tuna???) breakfast items. Inspired by our surroundings we came up with the question:

Given a list of food items with different prices and a maximum budget find all possible meals that could be purchased.

Which is essentially a confusing way of setting up a variation on the subset sum problem. Subsets are sets that can be made from the elements of a parent S. All possible subsets of a set is known as the powerset of that set. For example:

Or in terms of our problem:

So a naive approach for small sets is to generate the powerset and find all subsets that match the criteria.

Recursive solution

The recursive solution to this problem is probably easiest to understand. If you think of each subset as either containing or not containing each element then we can use the empty set as the base case and recurse back up, copy all current subsets and add the current element to each of those.

In code this would look something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

package breakfast

type MenuItem struct {
  name  string
  price float32
}

type Meal struct {
  price float32
  items []MenuItem
}

func FindMealsRecursively(menu []MenuItem, budget float32) (meals []Meal) {
  if len(menu) == 0 {
    return []Meal{Meal{}}
  }

  current := menu[0]
  meals = FindMealsRecursively(menu[1:], budget)

  for _, meal := range meals {
    meal.items = append(meal.items, current)
    meal.price += current.price

    if meal.price <= budget {
      meals = append(meals, meal)
    }
  }

  return
}

Iterative solution

The iterative solution is a bit trickier to understand in my opinion. It uses a bit array to represent inclusion of an element in a subset. For example, 10 would translate to the subset {eggs} because 1 is at the zero index. Similarly, 11 would be {eggs,bacon} and so on. We can use this to represent the powerset of a set by shifting 1 by the length of the set and iterating from 0 up to that number.

A concrete example might help to explain this. If we take {eggs, bacon} as our set S then shifting 1 by 2 will give us 100 or 4 as an integer. Iterating from 0 to 4 will give us the following bit arrays: 00, 01, 10, 11. We can then use these values to represent each subset as a bit array.

Here’s the code for this solution. The only tricky part is padding bit arrays so that they all contain the same number of characters. E.g. we want 1 to be 01 to correctly represent {bacon}.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

package breakfast

type MenuItem struct {
  name  string
  price float32
}

type Meal struct {
  price float32
  items []MenuItem
}

func FindMealsIteratively(menu []MenuItem, budget float32) (meals []Meal) {
  n := int64(1 << uint64(len(menu)))

  for i := int64(0); i < n; i++ {
    bits := strconv.FormatInt(i, 2)
    padding := strings.Repeat("0", len(menu)-len(bits))
    bits = padding + bits
    meal := Meal{}

    for position, bit := range bits {
      if bit == '1' {
        meal.items = append(meal.items, menu[position])
        meal.price += menu[position].price
      }
    }

    if meal.price <= budget {
      meals = append(meals, meal)
    }
  }

  return
}

Conclusion

In hindsight, this is a terrible interview question. First, it relies on having come across similar problems in the past (probably in previous interviews) because it’s unlikely either solution would jump out at someone in a thirty minute whiteboard session. Secondly, both solutions have a running time of O(2^n). Generally, if I’m given a whiteboard problem and my solution is slower that O(n log n) then I feel like I’ve probably missed something. If we had set the problem up slightly differently and asked for a meal within our budget then a dynamic programming solution would be viable. But, as we presented it, candidates were understandably confused even if they had come across similar problems in the past.

tl;dr — please don’t ask this in real interviews, but it is kind of a fun problem to solve.