Airbnb Interviews · 3

I was asked a problem which was a variation of the LC combination-sum problem https://leetcode.com/problems/combination-sum/description/

Problem:

A customer at a restaurant wants to order appetizers that total a specific amount. Given a menu with item prices, find and return all possible combinations of items that sum to the target amount. If no combination is found, return an empty list.

Example Menu:

• Nachos — $3.50

• Spring Rolls — $2.80

• Chicken Wings — $4.10

• Fries — $3.20

Example #1:

Input: possible_order(6.70)
Output: [["Nachos", "Fries"], ["Spring Rolls", "Chicken Wings"]]

Example #2:

Input: possible_order(9.50)
Output: [["Nachos", "Chicken Wings", "Fries"], ["Nachos", "Spring Rolls", "Chicken Wings"], ["Spring Rolls", "Fries", "Chicken Wings"]]

Solution:

def possible_orders(target: float):
    menu = [
        ("Nachos", 3.50),
        ("Spring Rolls", 2.80),
        ("Chicken Wings", 4.10),
        ("Fries", 3.20)
    ]
    
    result = []

    # backtrack through combinations
    def backtrack(current_combination, start, current_sum):
        if current_sum == target:
            result.append(list(current_combination)) # found a valid combination
            return
        if current_sum > target:
            return

        for i in range(start, len(menu)):
            item, price = menu[i]
            current_combination.append(item)
            backtrack(current_combination, i, current_sum + price)
            current_combination.pop()  # backtrack
    
    backtrack([], 0, 0)

    return result

print(possible_orders(9.50))  # two combinations
print(possible_orders(5.30))  # one combination
print(possible_orders(10.50)) # no combination

Only had the first coding round of 45 mins where the interviewer asked to implement the "Connect Four" game, where two players alternately drop colored discs into a 7-column, 6-row grid. The goal is to be the first player to arrange four of their discs consecutively in a row, either horizontally, vertically, or diagonally.

I didn't do great and the interviewer wasn't much help when I got stuck.

Was asked to create an iterator for a nested list of integers. I solved it in time and the interviewer was nice and helpful.

Problem Statement:

You’re given a nested list that contains both integers and arrays (which can have more integers or even other arrays). Your task is to implement an iterator that can go through all the elements in the list by flattening any arrays along the way and outputs all the integers in order.

was told to implement the following methods:

• hasNext(): Returns true if there are more elements (either integers or arrays) to iterate over, or false if we've reached the end.

• next(): Returns the next element in the list (either an integer or an array).

• remove(): Removes the current element (the one returned last by the next() method)

Example:

Input: [[], [1, 2], [3, [4, 5]], [[6], 7], []]
Output: 1, 2, 3, 4, 5, 6, 7