← Airbnb Interview Insights

Airbnb·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Airbnb coding round for a software engineer position. One meaty graph/BFS-style problem that looked deceptively clean on the surface but had a lot of edge cases hiding underneath.

Questions Asked (1)

Q1

You have n crates, each either locked or unlocked. Each crate holds a token count, a set of keys that unlock other crates, and a list of new crates that become accessible when opened. You start with an initial set of accessible crates. You can open any accessible unlocked crate, collect its tokens, discover new crates, and use found keys to unlock others. What's the maximum tokens you can collect, and how do you design an algorithm close to O(n + total_edges) that correctly handles cycles, duplicate references, and crates you find before you have the key for them?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I went in thinking BFS, which was right, but I underestimated how much state you need to track.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph traversal where crates are nodes and keys/accessibility define edges. Use a worklist algorithm with separate queues for unlocked and locked crates, processing unlocked crates immediately and deferring locked ones until their key is found. Track visited crates to avoid cycles and duplicates, and accumulate tokens as you open crates.

Pro tip: Emphasize that the algorithm must handle dynamic discovery: new crates and keys are added during traversal, so you need to check deferred locked crates whenever a new key is acquired. This shows you understand the incremental nature of the problem.

1. Model the problem as a graph

Represent each crate as a node with attributes: locked/unlocked status, token count, keys it contains, and crates it unlocks. Edges represent accessibility: from a crate to the crates it makes accessible, and from keys to the crates they unlock.

2. Initialize data structures

Use a queue for accessible unlocked crates, a map from key to locked crates waiting for that key, a set for visited crates, and a set for collected keys. Start by enqueuing all initially accessible unlocked crates.

3. Process crates with BFS/DFS

While the queue is not empty, dequeue a crate, mark it visited, add its tokens, collect its keys, and for each key, unlock any waiting crates and enqueue them if they become accessible. Also enqueue any newly discovered crates that are unlocked and accessible.

4. Handle locked crates and deferred processing

When encountering a locked crate, if you have the key, unlock and enqueue it; otherwise, add it to a waiting list for that key. When a new key is found, check the waiting list and enqueue any crates that can now be unlocked.

5. Terminate and return total tokens

Continue until the queue is empty. The total tokens collected is the sum of tokens from all visited crates. Ensure all crates are processed at most once to achieve O(n + total_edges) time.

Key Points to Mention

  • Use a queue for BFS or stack for DFS to traverse accessible crates, ensuring each crate is processed once.
  • Maintain a mapping from keys to locked crates waiting for that key to efficiently unlock crates when keys are found.
  • Track visited crates to avoid cycles and duplicate processing, and to handle duplicate references.
  • Handle crates discovered before their key is available by deferring them until the key is collected.
  • The algorithm should be O(n + total_edges) by processing each crate and each edge (key-crate relationship) at most once.
  • Consider edge cases: initially locked crates that are accessible but no key, cycles in accessibility, and multiple keys for the same crate.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.