User and Group Membership Index
Updated
Problem statement
Build a small membership index for users and groups. A user can belong to many groups, and a group can hold many users. Users and groups are both identified by integer IDs, and the two kinds of ID are separate: user 5 and group 5 have nothing to do with each other.
At the start, nobody belongs to any group. Process the calls in order. Call i is operations[i] with the user users[i] and the group groups[i]:
"add": make the user a member of the group. If the user is already a member, nothing changes."remove": take the user out of the group. If the user is not a member, nothing changes."groupsOf": report every group the user belongs to, in ascending order.groups[i]is not used."usersOf": report every user in the group, in ascending order.users[i]is not used.
Return a list with one entry for each "groupsOf" or "usersOf" call, in order. An entry is an empty list when there is nothing to report. "add" and "remove" calls add nothing to the result.
Follow-up: how would you store the memberships if hash maps were not allowed, and how does each design scale as the number of users and groups grows?
Function
processMemberships(operations: String[], users: int[], groups: int[]) → int[][]Examples
Example 1
operations = ["add","add","add","groupsOf","usersOf","usersOf"]users = [7,7,3,7,0,0]groups = [20,10,20,0,20,10]return = [[10,20],[3,7],[7]]- User 7 joins groups 20 and 10, and user 3 joins group 20.
groupsOfuser 7 returns[10, 20], sorted.usersOfgroup 20 returns[3, 7], andusersOfgroup 10 returns[7].
Example 2
operations = ["add","add","add","remove","groupsOf","usersOf","remove","groupsOf"]users = [1,1,2,1,1,0,5,2]groups = [4,4,4,4,0,4,9,0]return = [[],[2],[4]]- Adding user 1 to group 4 twice still makes one membership, and user 2 also joins group 4.
- The first
removetakes user 1 out of group 4, so user 1 is in no group:groupsOfuser 1 returns[], and group 4 now holds only user 2. - Removing user 5 from group 9 changes nothing, because that membership never existed. User 2 is still in group 4, so the last query returns
[4].
Example 3
operations = ["add","add","usersOf","groupsOf","usersOf","groupsOf"]users = [5,2,0,5,0,9]groups = [2,5,5,0,2,0]return = [[2],[2],[5],[]]- User 5 joins group 2, and user 2 joins group 5. User IDs and group IDs are separate, so these are two different memberships.
usersOfgroup 5 returns[2],groupsOfuser 5 returns[2], andusersOfgroup 2 returns[5].- User 9 never joined anything, so
groupsOfuser 9 returns[].
Constraints
1 <= operations.length <= 10^4users.length == groups.length == operations.length- Each
operations[i]is"add","remove","groupsOf"or"usersOf". 0 <= users[i], groups[i] <= 10^5- All returned lists together hold at most
10^5IDs.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Versioned Social NetworkOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Spreadsheet Formula DependenciesAmazon Web Services · ONSITE INTERVIEWAmazon Web Services interview questions
- Agent Task Dependency TrackerPerplexity AI · PHONE SCREENPerplexity AI interview questions
- Clone an Undirected Graph StateApple · OAApple interview questions
- Spreadsheet Formula DependenciesCitadel · PHONE SCREENCitadel interview questions
- Spreadsheet With Dependent CellsCharacter.AI · PHONE SCREEN
- Evaluate Live Spreadsheet ExpressionsStrala · PHONE SCREEN
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Random Dasher Set OperationsDoorDash · ONSITE INTERVIEWDoorDash interview questions
- LRU CacheLotusFlare · ONSITE INTERVIEW