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 Axon.

What role is this question designed for?

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

Find accessible devices via nested memberships

Company: Axon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an access model with **nested groups**: - A **group** can contain **users** and also contain other **groups** (subgroups). - A **user** can own or be assigned multiple **devices**. When a group is granted access, all users in that group **and in any nested subgroups (recursively)** have access to their devices. ### Input - `groupChildren`: a mapping from `groupId -> list of subgroupIds`. - `groupUsers`: a mapping from `groupId -> list of userIds`. - `userDevices`: a mapping from `userId -> list of deviceIds`. - `startGroups`: a list of groupIds that are granted access. ### Output Return the **set/list of unique deviceIds** that are accessible from `startGroups` by expanding subgroup membership recursively. ### Constraints - The group graph may contain **cycles** (e.g., A contains B, B contains A). - The total number of groups/users/devices can be large, so your solution should be near-linear in the size of the input. ### Example If `startGroups = ["G1"]`, and `G1` contains `G2`, `G2` contains user `U1`, and `U1` has devices `[D1, D2]`, then the answer includes `D1, D2`.

Quick Answer: This question evaluates understanding of graph traversal and set-based aggregation, with emphasis on handling nested group memberships, cycle-safe expansion, and mapping users to devices.

You are given an access model with nested groups. A group can directly contain users and can also contain other groups. If a starting group is granted access, then every user in that group and in all recursively reachable subgroups contributes their devices to the accessible set. The group graph may contain cycles, so your solution must avoid infinite loops. Return a sorted list of unique device IDs that are accessible from the given startGroups. If a group or user is missing from a mapping, treat it as having no children, no users, or no devices.

Constraints

0 <= total number of subgroup links + group-user memberships + user-device assignments <= 200000
The group graph may contain cycles and duplicate references
All IDs are strings
Your traversal should be near-linear in the size of the reachable input

Examples

Input: ({'G1': ['G2', 'G3'], 'G2': [], 'G3': []}, {'G1': ['U1'], 'G2': ['U2'], 'G3': ['U3']}, {'U1': ['D1'], 'U2': ['D2', 'D3'], 'U3': ['D4']}, ['G1'])

Expected Output: ['D1', 'D2', 'D3', 'D4']

Explanation: Starting from G1 reaches G1, G2, and G3. Their users are U1, U2, and U3, whose devices combine into D1, D2, D3, and D4.

Input: ({'A': ['B'], 'B': ['C'], 'C': ['A']}, {'A': ['U1'], 'B': ['U2', 'U1'], 'C': ['U3']}, {'U1': ['X1', 'X2'], 'U2': ['X2', 'X3'], 'U3': []}, ['A'])

Expected Output: ['X1', 'X2', 'X3']

Explanation: The groups form a cycle A -> B -> C -> A, but each group is visited once. U1 appears in two groups and X2 appears twice across users, so duplicates are removed.

Input: ({'G1': ['G2'], 'G4': ['G5']}, {'G2': ['U2'], 'G4': ['U4'], 'G5': ['U5']}, {'U2': ['D2'], 'U4': ['D4'], 'U5': ['D5']}, ['G1', 'G4', 'Missing'])

Expected Output: ['D2', 'D4', 'D5']

Explanation: G1 reaches G2 and contributes D2. G4 reaches itself and G5, contributing D4 and D5. The missing start group contributes nothing.

Input: ({}, {}, {}, [])

Expected Output: []

Explanation: With no groups, users, devices, or starting points, no devices are accessible.

Input: ({'G1': ['G1', 'G2', 'G2'], 'G2': []}, {'G1': ['U1', 'U1'], 'G2': ['U2']}, {'U1': ['D1', 'D1'], 'U2': ['D2']}, ['G1', 'G1'])

Expected Output: ['D1', 'D2']

Explanation: Self-references, repeated child links, repeated users, repeated devices, and repeated start groups should all be handled without duplicate output.

Hints

Model the groups as a directed graph and traverse from all startGroups using DFS or BFS.
Use visited sets so you do not process the same group or user more than once, especially when cycles or duplicate memberships exist.

Quick Overview

This question evaluates understanding of graph traversal and set-based aggregation, with emphasis on handling nested group memberships, cycle-safe expansion, and mapping users to devices.