LoopCoach
Airbnb questions

Restaurant Menu Combinations

AirbnbPhone screenMedium

A guest wants to order dishes whose prices add up to exactly a given amount. The menu lists each dish as [name, price] with prices in whole cents (so $2.15 is 215). Names are unique, and the list order is the menu order. An order is any non-empty collection of dishes where each dish may be ordered any number of times, and the sequence does not matter.

Part 1: Orders that hit the target

Given a menu of dishes and a target amount in cents, return every distinct order whose prices sum to target.

Write each order as a list of dish names in menu order; a repeated dish appears that many times in a row. Return the orders sorted by comparing their menu positions lexicographically: an order starting with an earlier dish comes first, and among orders with the same start, compare the next dish, and so on. If no order reaches target, return an empty list.

  1. Example 1
    menu
    [["Fruit",215],["Fries",275],["Salad",335],["Wings",355],["Mozzarella",420],["Plate",580]]
    target
    550
    Output
    [["Fruit","Salad"],["Fries","Fries"]]

    Why: Two Fries cost 275 + 275 = 550 and Fruit + Salad cost 215 + 335 = 550. Orders list dishes in menu order and are sorted by menu position, so ["Fruit", "Salad"] (positions 0, 2) comes before ["Fries", "Fries"] (positions 1, 1).

Constraints

  • 1 <= len(menu) <= 10
  • 1 <= menu[i][1] <= 10^4, and every menu[i][1] is an integer
  • 1 <= len(menu[i][0]) <= 10, and the names menu[i][0] are unique
  • 1 <= target <= 10^4
  • possible_orders returns at most 10^4 orders
Sign up to practice