Find accessible devices via nested memberships

Q: Find accessible devices via nested memberships

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.