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.