How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Maximize tokens from nested crates | Airbnb Coding Question

Maximize tokens from nested crates

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given n crates, each either locked or unlocked. Each crate i contains: an integer tokens[i]; a list of keys that can unlock other crates; and a list of new crates that become available when you open it. You start with a set of initial crates you can access (they may be locked). You may repeatedly: open any accessible unlocked crate, collect its tokens, add any newly found crates to your accessible set, and use any keys found to unlock crates. Return the maximum total tokens you can collect. Design an algorithm with near O(n + total_edges) time, specify data structures, and correctly handle cycles, duplicates, and crates discovered before their keys.

Quick Answer: This question evaluates proficiency with graph-based algorithms, state management, and data structure selection for handling dependencies, cycles, duplicates, and dynamic discovery in resource-collection scenarios.

You are given n crates numbered from 0 to n-1. Each crate is either locked or unlocked. Crate i contains a number of tokens, a list of keys that can unlock other crates, and a list of other crates that become accessible once crate i is opened. You start with a set of initial crates that are accessible, but some of them may still be locked. You may repeatedly open any crate that is both accessible and unlocked. When you open a crate, you collect its tokens, gain all keys inside it, and add all contained crates to your accessible set. A key may be found before or after the corresponding crate becomes accessible. Lists may contain duplicates, and the crate graph may contain cycles. Each crate can be opened at most once. Return the maximum total number of tokens you can collect.

Constraints

0 <= n <= 100000
len(status) == len(tokens) == len(keys) == len(contained_crates) == n
0 <= tokens[i] <= 10^9
0 <= each crate index in keys, contained_crates, and initial_crates < n
The total number of entries across all keys lists and contained_crates lists is at most 200000
Duplicates and cycles are allowed

Examples

Input: ([1,0,0,0], [5,10,20,1], [[1], [2], [3], []], [[1], [2], [3], []], [0])

Expected Output: 36

Explanation: Open crate 0, then 1, then 2, then 3. The total is 5 + 10 + 20 + 1 = 36.

Input: ([1,0,1,0], [7,5,4,9], [[], [3], [1], []], [[1,2], [3], [], []], [0])

Expected Output: 25

Explanation: Crate 1 is discovered first but stays locked. Crate 2 is accessible and unlocked, and opening it gives the key to crate 1. Then opening crate 1 reveals crate 3, which is already unlocked by its key. Total = 7 + 4 + 5 + 9 = 25.

Input: ([1,0,0], [2,3,4], [[1,1], [2], [0]], [[1,1], [2,0], [1]], [0,0])

Expected Output: 9

Explanation: Duplicates and cycles do not change the result because each crate is opened at most once. All three crates become openable, so the total is 2 + 3 + 4 = 9.

Input: ([0,0], [5,6], [[1], []], [[1], []], [0])

Expected Output: 0

Explanation: Crate 0 is accessible but locked, and no other crate can be opened to obtain its key. Therefore no tokens can be collected.

Input: ([], [], [], [], [])

Expected Output: 0

Explanation: There are no crates, so the answer is 0.

Solution

def solution(status, tokens, keys, contained_crates, initial_crates):
    from collections import deque

    n = len(status)
    unlocked = [s == 1 for s in status]
    accessible = [False] * n
    opened = [False] * n
    queue = deque()

    for crate in initial_crates:
        if not accessible[crate]:
            accessible[crate] = True
            if unlocked[crate]:
                queue.append(crate)

    total = 0

    while queue:
        crate = queue.popleft()
        if opened[crate] or not accessible[crate] or not unlocked[crate]:
            continue

        opened[crate] = True
        total += tokens[crate]

        for key in keys[crate]:
            if not unlocked[key]:
                unlocked[key] = True
                if accessible[key] and not opened[key]:
                    queue.append(key)

        for nxt in contained_crates[crate]:
            if not accessible[nxt]:
                accessible[nxt] = True
                if unlocked[nxt] and not opened[nxt]:
                    queue.append(nxt)

    return total

Time complexity: O(n + E), where E is the total number of entries across all keys and contained_crates lists. Space complexity: O(n).

Hints

A crate becomes openable only when two conditions are true at the same time: it is accessible and it is unlocked. Track these states separately.
Use a queue for crates that are ready to open. Opening one crate can unlock previously discovered crates or make previously unlocked crates newly accessible.

Quick Overview

This question evaluates proficiency with graph-based algorithms, state management, and data structure selection for handling dependencies, cycles, duplicates, and dynamic discovery in resource-collection scenarios.