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.

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.

Hints

  1. 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.
  2. 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.

Loading coding console...