FastPrepUser and Group Membership Index

User and Group Membership Index

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

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.
  • groupsOf user 7 returns [10, 20], sorted.
  • usersOf group 20 returns [3, 7], and usersOf group 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 remove takes user 1 out of group 4, so user 1 is in no group: groupsOf user 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.
  • usersOf group 5 returns [2], groupsOf user 5 returns [2], and usersOf group 2 returns [5].
  • User 9 never joined anything, so groupsOf user 9 returns [].

Constraints

  • 1 <= operations.length <= 10^4
  • users.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^5 IDs.

More Microsoft Onsite Interview questions

Similar questions at other companies

Interview reports that mention this question

Microsoft interview experiences

All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[][] processMemberships(String[] operations, int[] users, int[] groups) {
        // Write your code here.
    }
}
Checking account…