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 Technical Screen rounds at Airbnb.

What role is this question designed for?

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

Count Candies from Unlockable Boxes | Airbnb Coding Question

Count Candies from Unlockable Boxes

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an object-oriented representation of boxes in a house. Initially, exactly one box is physically accessible. Each `Box` has: - A unique `id`. - A boolean `isOpen`, indicating whether the box can be opened without a key. - A non-negative integer `candies`, the number of candies inside the box. - A list of keys, where each key opens the box with the corresponding id. - A list of child boxes physically contained inside the box. Rules: - You may collect candies from a box only after opening it. - When you open a box, you immediately collect all candies inside it, obtain all keys inside it, and gain physical access to all child boxes inside it. - A locked box can be opened only if you have obtained its key. - Some boxes may already be open and do not require a key. - Some boxes may never have a corresponding key. - The same key or box may be encountered more than once; do not double-count candies from any box. Design a `Box` class and implement a function that takes the initially accessible box and returns the total number of candies that can eventually be collected.

Quick Answer: This question evaluates a candidate's understanding of graph traversal, state management, and object-oriented design to determine reachability and resource collection in a dependency graph of boxes and keys.

You are modeling boxes in a house. Conceptually, each box is an object with these fields: `id`, `isOpen`, `candies`, `keys`, and `children`. Initially, exactly one box is physically accessible. Rules: - You may collect candies from a box only after opening it. - When you open a box, you immediately collect all candies inside it, obtain all keys inside it, and gain physical access to all child boxes inside it. - A locked box can be opened only if you already have its key. - Some boxes may already be open. - Some boxes may never have a corresponding key. - The same key or box may appear more than once. Never count candies from the same box more than once. For this problem, the object graph is serialized using arrays indexed by box id: - `status[i]` is `1` if box `i` is already open, otherwise `0`. - `candies[i]` is the number of candies in box `i`. - `keys[i]` is a list of box ids whose keys are inside box `i`. - `children[i]` is a list of box ids physically contained in box `i`. - `root` is the id of the only box initially accessible. You may define a `Box` class internally if you wish. Return the total number of candies that can eventually be collected.

Constraints

1 <= n == len(status) == len(candies) == len(keys) == len(children) <= 100000
0 <= root < n
status[i] is either 0 or 1
0 <= candies[i] <= 10000
Every value in keys[i] and children[i] is a valid box id from 0 to n - 1
The total number of key references plus child references across all boxes is at most 200000

Examples

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

Expected Output: 21

Explanation: Open box 0 to collect 5, get key 1, and gain boxes 3 and 1. Box 3 is already open, so collect 4 and get key 4 plus box 4. Box 1 can now be opened, giving 7, key 2, and box 2. Finally open boxes 4 and 2 for 2 and 3 more candies. Total = 21.

Input: (0, [0], [10], [[]], [[]])

Expected Output: 0

Explanation: The only accessible box is locked, and there is no way to obtain its key.

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

Expected Output: 16

Explanation: Box 1 and its key appear more than once, and box 2 also appears more than once, but each box can contribute candies only once. Total = 2 + 5 + 9 = 16.

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

Expected Output: 21

Explanation: Box 0 gives the key to box 2 before box 2 is physically found. After opening box 1, box 2 becomes accessible and can be opened immediately, which unlocks box 3. Total = 4 + 6 + 8 + 3 = 21.

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

Expected Output: 23

Explanation: Box 1 is first discovered while locked. Box 2 is already open and provides key 1, so box 1 can be opened. Box 1 then provides key 3, allowing box 3 to open. Cycles back to box 0 do not add candies again. Total = 23.

Hints

Track two separate things: which boxes are physically reachable, and which boxes are currently openable.
If you discover a locked box before finding its key, do not discard it. A later key may let you open it.

Quick Overview

This question evaluates a candidate's understanding of graph traversal, state management, and object-oriented design to determine reachability and resource collection in a dependency graph of boxes and keys.