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.

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.

Hints

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

Loading coding console...