Google Interview Question Senior Software Development Engineers
Country: United States
Interview Type: In-Person
This can accomplished using 2 stack + dfs + visited flag array. Idea is as you go down the graph you build the memberOf groups and as you trace back up you build the members groups for the Group you are traversing.
a. Iterator over hashmap
b. For each entry do following
Invariant is for Groups in parent stack you have computed memberOf groups. When you pop groups from parent stack you will be going back up and computing members group.
1. initial 2 stack. a parent and a child stack. initial parent stack with G4 and child with its children i.e G1. Memberof Parent G4 are none so nthing to do here
2. When you pop a element from child stack , create a new object MyGroups. Get the parent of child (G4, maintain 2 hashmaps for Parent to child and child to parent mapping). Mark it as visited and add users to MyGroup's user list.
3. Add parent (G4) to memberOf of child (G1). Add memberOFs of parent(G4) to membersOf child as well. Push this child to parent stack.
4. Update parent-child mapping and child-parent mapping.
5. Get the children of G1 from input dictionary and push them on child stack.
6. Continue steps 2-5 till child stack is empty.
7. Child stack is now empty.
8. Pop element from parent stack . Note the leaf of the graph will be at top now.
9. Get it's child from the parent-child mapping we build when we worked on child stack.
10. add the child to member of this group's MyGroup object. Get the child's member list and also add it to this group's MyGroup object.
Node. if its a leaf the there won't be any entry the the parent-child mapping unless it a cycle.
11. Continue poppping elements from parent stack and repeat steps 9-10 till parent stack is empty.
c. Once we have execute step b for all entries in input dictionary return our build list of MyGroup
public static List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
{
Dictionary<string, MyGroup> groups = new Dictionary<string, MyGroup>();
List<KeyValuePair<string, string>> map = new List<KeyValuePair<string, string>>();
foreach (var groupName in groupMembers.Keys)
{
groups.Add(groupName, new MyGroup(groupName));
foreach (var memberName in groupMembers[groupName])
{
map.Add(new KeyValuePair<string, string>(groupName, memberName));
}
}
foreach (var pair in map)
{
var parent = groups[pair.Key];
if (groups.ContainsKey(pair.Value))
{
var child = groups[pair.Value];
parent.Members.Add(pair.Value, child);
child.MemberOf.Add(pair.Key, parent);
}
else
{
parent.Users.Add(pair.Value);
}
}
return groups.Values.ToList();
}
public static List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
{
Dictionary<string, MyGroup> groups = new Dictionary<string, MyGroup>();
List<KeyValuePair<string, string>> map = new List<KeyValuePair<string, string>>();
foreach (var groupName in groupMembers.Keys)
{
groups.Add(groupName, new MyGroup(groupName));
foreach (var memberName in groupMembers[groupName])
{
map.Add(new KeyValuePair<string, string>(groupName, memberName));
}
}
foreach (var pair in map)
{
var parent = groups[pair.Key];
if (groups.ContainsKey(pair.Value))
{
var child = groups[pair.Value];
parent.Members.Add(pair.Value, child);
child.MemberOf.Add(pair.Key, parent);
}
else
{
parent.Users.Add(pair.Value);
}
}
return groups.Values.ToList();
}
public static List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
{
Dictionary<string, MyGroup> groups = new Dictionary<string, MyGroup>();
List<KeyValuePair<string, string>> map = new List<KeyValuePair<string, string>>();
foreach (var groupName in groupMembers.Keys)
{
groups.Add(groupName, new MyGroup(groupName));
foreach (var memberName in groupMembers[groupName])
{
map.Add(new KeyValuePair<string, string>(groupName, memberName));
}
}
foreach (var pair in map)
{
var parent = groups[pair.Key];
if (groups.ContainsKey(pair.Value))
{
var child = groups[pair.Value];
parent.Members.Add(pair.Value, child);
child.MemberOf.Add(pair.Key, parent);
}
else
{
parent.Users.Add(pair.Value);
}
}
return groups.Values.ToList();
}
public static List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
{
Dictionary<string, MyGroup> groups = new Dictionary<string, MyGroup>();
List<KeyValuePair<string, string>> map = new List<KeyValuePair<string, string>>();
foreach (var groupName in groupMembers.Keys)
{
groups.Add(groupName, new MyGroup(groupName));
foreach (var memberName in groupMembers[groupName])
{
map.Add(new KeyValuePair<string, string>(groupName, memberName));
}
}
foreach (var pair in map)
{
var parent = groups[pair.Key];
if (groups.ContainsKey(pair.Value))
{
var child = groups[pair.Value];
parent.Members.Add(pair.Value, child);
child.MemberOf.Add(pair.Key, parent);
}
else
{
parent.Users.Add(pair.Value);
}
}
return groups.Values.ToList();
}
public class GroupMembership {
public class Group {
public String Name;
public List<Group> memberOf;
public List<Group> members;
public List<String> users;
public Group(String name){
this.Name = name;
memberOf = new ArrayList<Group>();
members = new ArrayList<Group>();
users = new ArrayList<String>();
}
public void printMembers(){
for(int i=0;i< this.members.size();i++){
System.out.print(this.members.get(i).Name+((i<this.members.size()-1)?", ":""));
}
System.out.println();
}
public void printParents(){
for(int i=0;i< this.memberOf.size();i++){
System.out.print(memberOf.get(i).Name+((i<this.memberOf.size()-1)?", ":""));
}
System.out.println();
}
public void printUsers(){
for(int i=0;i< this.users.size();i++){
System.out.print(users.get(i)+((i<this.users.size()-1)?", ":""));
}
System.out.println();
}
}
public HashMap<String, Group> findMembership(HashMap<String, HashSet<String>> groups){
HashMap<String, Group> visitedGroups = new HashMap<String, Group>();
Set<String> keys = groups.keySet();
Iterator<String> keysItr = keys.iterator();
while(keysItr.hasNext()){
//get the group name
String parentGroupName = keysItr.next();
if(!visitedGroups.containsKey(parentGroupName)){
Group newGroup = new Group(parentGroupName);
visitedGroups.put(parentGroupName,newGroup);
}
Group mainGroup = visitedGroups.get(parentGroupName);
HashSet<String> ownGroups = groups.get(parentGroupName);
Iterator<String> itr = ownGroups.iterator();
while(itr.hasNext()){
String currGroupName = itr.next();
if(currGroupName.startsWith("U")){
mainGroup.users.add(currGroupName);
continue;
}
if(visitedGroups.containsKey(currGroupName)){
if(currGroupName == parentGroupName){
visitedGroups.put(parentGroupName,mainGroup);
mainGroup = visitedGroups.get(parentGroupName);
}
Group gp = visitedGroups.get(currGroupName);
gp.memberOf.add(visitedGroups.get(parentGroupName));
visitedGroups.put(currGroupName,gp);
mainGroup.members.add(gp);
}else{
Group newGroup = new Group(currGroupName);
newGroup.memberOf.add(mainGroup);
visitedGroups.put(currGroupName,newGroup);
mainGroup.members.add(newGroup);
}
}
visitedGroups.put(parentGroupName,mainGroup);
}
return visitedGroups;
}
public static void main(String [] args){
GroupMembership gm = new GroupMembership();
HashMap<String, HashSet<String>> groups = new HashMap<String, HashSet<String>>();
HashSet<String> temp1 = new HashSet<String>();
temp1.add("U1");temp1.add("G1");
groups.put("G4", temp1);
HashSet<String> temp2 = new HashSet<String>();
temp2.add("G2");temp2.add("G3");
groups.put("G1", temp2);
HashSet<String> temp3 = new HashSet<String>();
temp3.add("G3");temp3.add("G5");
groups.put("G3", temp3);
HashSet<String> temp4 = new HashSet<String>();
temp4.add("U2");temp4.add("G4");
groups.put("G2", temp4);
HashSet<String> temp5 = new HashSet<String>();
temp5.add("U2");temp5.add("G6");
groups.put("G5", temp5);
HashSet<String> temp6 = new HashSet<String>();
temp6.add("U3");
groups.put("G6", temp6);
HashMap<String, Group> processedGroups = gm.findMembership(groups);
Set<String> keys = processedGroups.keySet();
Iterator<String> keysItr = keys.iterator();
while(keysItr.hasNext()){
Group currGroup = processedGroups.get(keysItr.next());
System.out.println("Name: "+currGroup.Name);
System.out.print("Member Groups: ");
currGroup.printMembers();
System.out.print("Member Of: ");
currGroup.printParents();
System.out.print("Users: ");
currGroup.printUsers();
System.out.println();
}
}
}
package main.Questions.ID5191526374178816;
import java.util.*;
public class Members {
Map<String, MyGroup> groupList = new HashMap<String, MyGroup>();
public Map<String, MyGroup> getMyGroupsList(Map<String, HashSet<String>> groupMembers) {
for (Map.Entry<String, HashSet<String>> groupMember : groupMembers.entrySet()) {
MyGroup myGroup = createMyGroup(groupMember.getKey());
findMyGroupMembers(groupMembers, groupMember, myGroup);
}
return groupList;
}
private void findMyGroupMembers(Map<String, HashSet<String>> groupMembers, Map.Entry<String, HashSet<String>> groupMember, MyGroup myGroup) {
Queue<HashSet<String>> subGroupMembersQueue = new LinkedList<HashSet<String>>();
HashSet<String> visited = new HashSet<String>();
subGroupMembersQueue.add(groupMember.getValue());
while (subGroupMembersQueue.size() > 0) {
HashSet<String> subGroupMembers = subGroupMembersQueue.remove();
for (String subGroupMember : subGroupMembers) {
if (isaGroup(groupMembers, subGroupMember)) {
if (!visited.contains(subGroupMember)) {
visited.add(subGroupMember);
subGroupMembersQueue.add(groupMembers.get(subGroupMember));
}
MyGroup subMyGroup = createMyGroup(subGroupMember);
subMyGroup.MemberOf.put(myGroup.Identity, myGroup);
groupList.put(subMyGroup.Identity, subMyGroup);
myGroup.Members.put(subMyGroup.Identity, subMyGroup);
} else {
myGroup.Users.add(subGroupMember);
}
}
}
groupList.put(myGroup.Identity, myGroup);
}
private boolean isaGroup(Map<String, HashSet<String>> groupMembers, String subGroupMember) {
return groupMembers.containsKey(subGroupMember);
}
private MyGroup createMyGroup(String key) {
if (!groupList.containsKey(key)) {
MyGroup myGroup = new MyGroup(key);
groupList.put(key, myGroup);
}
return groupList.get(key);
}
}
git.io/vOnjm -- source
git.io/vOnj8 -- test
A long solution..
Do 2 dfs for parents and children.
public static class Group{
public String identity;
public HashMap<String, Group> memberOf;
public HashMap<String, Group> members;
public HashSet<String> users;
public Group(String name){
identity = name;
memberOf = new HashMap<String, Group>();
members = new HashMap<String, Group>();
users = new HashSet<String>();
}
}
public static class Node{
String identity;
List<Node> child;
int state;
List<Node> parent;
public Node(String name){
identity = name;
child = new ArrayList<Node>();
state = 0;
this.parent = new ArrayList<Node>();
}
}
public static List<Group> findGroup(HashMap<String, HashSet<String>>
groupMembers){
List<Group> result = new ArrayList<Group>();
HashMap<String, Node> nodeHashMap = new HashMap<String, Node>();
for(Map.Entry<String, HashSet<String>> entry : groupMembers.entrySet()){
String name = entry.getKey();
HashSet<String> member = entry.getValue();
Node node;
if(nodeHashMap.containsKey(name)){
node = nodeHashMap.get(name);
}else{
node = new Node(name);
nodeHashMap.put(name, node);
}
for(String elem : member){
Node child;
if(nodeHashMap.containsKey(elem)){
child = nodeHashMap.get(elem);
}else{
child = new Node(elem);
nodeHashMap.put(elem, child);
}
child.parent.add(node);
node.child.add(child);
}
}
HashMap<String, Group> groupHashMap = new HashMap<String, Group>();
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()) {
Group group = new Group(entry.getKey());
groupHashMap.put(entry.getKey(), group);
result.add(group);
}
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()){
Node node = entry.getValue();
if(node.state == 2){
Group g = groupHashMap.get(node.identity);
if(!g.members.isEmpty() && !g.users.isEmpty()) continue;
for(Node nd : node.child){
String ndId = nd.identity;
if(ndId.startsWith("G")){
g.members.put(ndId, groupHashMap.get(ndId));
}else{
g.users.add(ndId);
}
}
continue;
}
Stack<Node> nodeStack = new Stack<Node>();
nodeStack.add(node);
while(!nodeStack.isEmpty()){
Node curNode = nodeStack.peek();
if(curNode.state == 1){
curNode.state = 2;
Set<String> allchild = new HashSet<String>();
for(Node curNodeChild : curNode.child){
allchild.add(curNodeChild.identity);
for(Node curNodeGrandChild : curNodeChild.child){
allchild.add(curNodeGrandChild.identity);
}
}
curNode.child.clear();
for(String id : allchild){
curNode.child.add(nodeHashMap.get(id));
}
nodeStack.pop();
continue;
}
curNode.state = 1;
List<Node> child = curNode.child;
for(Node childNode : child){
if(childNode.state == 1){
return null;
}else{
nodeStack.push(childNode);
}
}
}
Group g = groupHashMap.get(node.identity);
for(Node nd : node.child){
String ndId = nd.identity;
if(ndId.startsWith("G")){
g.members.put(ndId, groupHashMap.get(ndId));
}else{
g.users.add(ndId);
}
}
}
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()) {
entry.getValue().state = 0;
}
for(Map.Entry<String, Node> entry : nodeHashMap.entrySet()) {
Node node = entry.getValue();
if (node.state == 2) {
Group g = groupHashMap.get(node.identity);
if (!g.memberOf.isEmpty()) continue;
for (Node nd : node.parent) {
String ndId = nd.identity;
g.memberOf.put(ndId, groupHashMap.get(ndId));
}
continue;
}
Stack<Node> nodeStack = new Stack<Node>();
nodeStack.add(node);
while (!nodeStack.isEmpty()) {
Node curNode = nodeStack.peek();
if (curNode.state == 1) {
curNode.state = 2;
Set<String> allparent = new HashSet<String>();
for (Node curNodeParent : curNode.parent) {
allparent.add(curNodeParent.identity);
for (Node curNodeGrandParent : curNodeParent.parent) {
allparent.add(curNodeGrandParent.identity);
}
}
curNode.parent.clear();
for (String id : allparent) {
curNode.parent.add(nodeHashMap.get(id));
}
nodeStack.pop();
continue;
}
curNode.state = 1;
List<Node> parent = curNode.parent;
for (Node parentNode : parent) {
if (parentNode.state == 1) {
return null;
} else {
nodeStack.push(parentNode);
}
}
}
Group g = groupHashMap.get(node.identity);
for (Node nd : node.parent) {
String ndId = nd.identity;
g.memberOf.put(ndId, groupHashMap.get(ndId));
}
}
return result;
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
HashMap<String, HashSet<String>> groupMembers = new HashMap<String, HashSet<String>>()
{{
put("G4", new HashSet<String>() {{ add("U1"); add("G1"); }});
put("G1", new HashSet<String>() {{ add("G2"); add("G3"); add("G6"); }});
put("G3", new HashSet<String>() {{ add("G3"); add("G5"); }});
put("G2", new HashSet<String>() {{ add("G4"); add("U2"); }});
put("G5", new HashSet<String>() {{ add("U2"); add("G6"); }});
put("G6", new HashSet<String>() {{ add("U3"); }});
}};
ArrayList<Group> result = FindMembers(groupMembers);
for (Group g : result)
{
System.out.println(g.toString());
}
}
public static ArrayList<Group> FindMembers(HashMap<String, HashSet<String>> groupMembers)
{
if (groupMembers == null) { throw new IllegalArgumentException("groupMembers"); }
if (groupMembers.size() == 0) { return new ArrayList<Group>(); }
HashSet<String> visited = new HashSet<String>(); // keep track of which group has been visited
HashMap<String, Member> members = new HashMap<String, Member>(); // for fast member lookup
// Performing a breadth-first traversal using a Queue and a loop
Queue<Member> queue = new LinkedList<Member>();
for (String key : groupMembers.keySet())
{
Group group = new Group(key);
queue.offer(group);
members.put(key, group);
}
while (!queue.isEmpty())
{
Member member = queue.poll();
if (member instanceof Group)
{
Group group = (Group)member;
String memberName = member.getName();
if (!visited.contains(memberName))
{
visited.add(memberName);
// Now process the children
HashSet<String> children = groupMembers.get(memberName);
for (String c : children)
{
Member m = members.get(c);
if (m != null && m instanceof Group)
{
Group g = (Group)m;
g.addMemberOf(group);
group.addMember(g);
queue.offer(g);
}
else // user
{
User u = m == null ? new User(c) : (User)m;
group.addMember(u);
}
}
}
}
}
ArrayList<Group> results = new ArrayList<Group>();
for (Member m : members.values())
{
if (m instanceof Group)
{
results.add((Group)m);
}
}
return results;
}
private static class Member
{
private String name;
protected Member(String name)
{
if (name == null || name.length() == 0)
{
throw new IllegalArgumentException("name");
}
this.name = name;
}
public String getName() { return this.name; }
public String toString() { return this.getName(); }
}
private static class User extends Member
{
public User(String name)
{
super(name);
}
}
private static class Group extends Member
{
private HashMap<String, Group> memberOf = new HashMap<String, Group>();
private HashMap<String, Member> members = new HashMap<String, Member>();
public Group(String name)
{
super(name);
}
public HashMap<String, Group> getMemberOf() { return this.memberOf; }
public HashMap<String, Member> getMembers() { return this.members; }
public void addMember(Member m)
{
if (!this.members.containsKey(m.getName()))
{
this.members.put(m.getName(), m);
}
}
public void addMemberOf(Group g)
{
if (!this.memberOf.containsKey(g.getName()))
{
this.memberOf.put(g.getName(), g);
}
}
public String toString()
{
StringBuilder sb = new StringBuilder();
sb.append("Group: " + this.getName() + "\n");
sb.append("MemberOf: ");
for (Group g : this.getMemberOf().values())
{
sb.append(g.getName() + ", ");
}
sb.append("Members: ");
for (Member m : this.getMembers().values())
{
sb.append(m.getName() + ", ");
}
return sb.toString();
}
}
}
Success time: 0.11 memory: 320512 signal:0
Group: G1
MemberOf: G4, Members: G2, G3, G6,
Group: G2
MemberOf: G1, Members: G4, U2,
Group: G3
MemberOf: G1, G3, Members: G3, G5,
Group: G4
MemberOf: G2, Members: G1, U1,
Group: G5
MemberOf: G3, Members: U2, G6,
Group: G6
MemberOf: G1, G5, Members: U3,
c++
Step 1: Build base MyGroup object map
Step 2: For each object, Search Graph (DPS) , building members, memberOf and users
Step 3: Build output vector
#include <iostream>
#include "vector"
#include "map"
#include "stack"
#include "queue"
#include "string"
using namespace std;
typedef map<string, class MyGroup *> groupObjectMap;
typedef vector<class MyGroup *> groupObjectList;
typedef vector<string> ulist;
class MyGroup
{
public:
string name;
groupObjectMap memberOf;
groupObjectMap members;
ulist users;
} ;
typedef map<string, vector<string>> groupsHash;
// build intersection_list list
void searchDFSIterative(string node, groupsHash groupMembers, groupObjectMap &objects, MyGroup *object)
{
stack<string> mystack;
map<string, bool> visited;
// Base Case, tree is empty
if (node.empty())
return;
mystack.push(node);
while (!mystack.empty())
{
node = mystack.top();
mystack.pop();
if (visited.find(node) == visited.end())
{
visited[node] = true;
if (object->name != node)
{
// add visited node to me (excluding me)
object->members[node] = objects[node];
// add me to visited node
objects[node]->memberOf[object->name] = object;
}
for (auto name : groupMembers[node])
{
if (name.substr(0, 1) == string("U"))
{
if (find(object->users.begin(), object->users.end(), name) == object->users.end())
{
object->users.push_back(name);
}
}
else
{
mystack.push(name);
}
}
}
}
}
vector<MyGroup *>FindMembers(groupsHash groupMembers)
{
groupObjectMap groupObjects;
vector<MyGroup *> output;
// Build the parents
for (auto grouppair : groupMembers)
{
// Each of these is a node/root with members
MyGroup *object = new MyGroup();
object->name = grouppair.first;
groupObjects[grouppair.first] = object;
}
for (auto objectpair : groupObjects)
{
// Each of these is a node/root with members
MyGroup *object = objectpair.second;
searchDFSIterative(objectpair.first, groupMembers, groupObjects, object);
}
for (auto grouppair : groupObjects)
{
output.push_back(grouppair.second);
}
for (auto group : output)
{
cout << "Group " << group->name << endl;
cout << " memberOf: ";
for (auto memberpair : group->memberOf)
{
cout << memberpair.first << " ";
}
cout << endl;
cout << " members: ";
for (auto memberpair : group->members)
{
cout << memberpair.first << " ";
}
cout << endl;
cout << " users: ";
for (auto user : group->users)
{
cout << user << " ";
}
cout << endl;
}
return output;
}
int main(int argc, char **argv)
{
groupsHash groups;
groups["G4"] = { "U1", "G1" };
groups["G1"] = { "G2", "G3", "G6" };
groups["G3"] = { "G3", "G5" };
groups["G2"] = { "G4", "U2" };
groups["G5"] = { "U2", "G6" };
groups["G6"] = { "U3" };
FindMembers(groups);
}
c++ answer
Step 1: Build map of base group objects
Step 2: for each base object, DFS search to build members, memberof and users
Step 3: Build output
#include <iostream>
#include "vector"
#include "map"
#include "stack"
#include "queue"
#include "string"
using namespace std;
typedef map<string, class MyGroup *> groupObjectMap;
typedef vector<class MyGroup *> groupObjectList;
typedef vector<string> ulist;
class MyGroup
{
public:
string name;
groupObjectMap memberOf;
groupObjectMap members;
ulist users;
} ;
typedef map<string, vector<string>> groupsHash;
// build intersection_list list
void searchDFSIterative(string node, groupsHash groupMembers, groupObjectMap &objects, MyGroup *object)
{
stack<string> mystack;
map<string, bool> visited;
// Base Case, tree is empty
if (node.empty())
return;
mystack.push(node);
while (!mystack.empty())
{
node = mystack.top();
mystack.pop();
if (visited.find(node) == visited.end())
{
visited[node] = true;
if (object->name != node)
{
// add visited node to me (excluding me)
object->members[node] = objects[node];
// add me to visited node
objects[node]->memberOf[object->name] = object;
}
for (auto name : groupMembers[node])
{
if (name.substr(0, 1) == string("U"))
{
if (find(object->users.begin(), object->users.end(), name) == object->users.end())
{
object->users.push_back(name);
}
}
else
{
mystack.push(name);
}
}
}
}
}
vector<MyGroup *>FindMembers(groupsHash groupMembers)
{
groupObjectMap groupObjects;
vector<MyGroup *> output;
// Build the parents
for (auto grouppair : groupMembers)
{
// Each of these is a node/root with members
MyGroup *object = new MyGroup();
object->name = grouppair.first;
groupObjects[grouppair.first] = object;
}
for (auto objectpair : groupObjects)
{
// Each of these is a node/root with members
MyGroup *object = objectpair.second;
searchDFSIterative(objectpair.first, groupMembers, groupObjects, object);
}
for (auto grouppair : groupObjects)
{
output.push_back(grouppair.second);
}
for (auto group : output)
{
cout << "Group " << group->name << endl;
cout << " memberOf: ";
for (auto memberpair : group->memberOf)
{
cout << memberpair.first << " ";
}
cout << endl;
cout << " members: ";
for (auto memberpair : group->members)
{
cout << memberpair.first << " ";
}
cout << endl;
cout << " users: ";
for (auto user : group->users)
{
cout << user << " ";
}
cout << endl;
}
return output;
}
int main(int argc, char **argv)
{
groupsHash groups;
groups["G4"] = { "U1", "G1" };
groups["G1"] = { "G2", "G3", "G6" };
groups["G3"] = { "G3", "G5" };
groups["G2"] = { "G4", "U2" };
groups["G5"] = { "U2", "G6" };
groups["G6"] = { "U3" };
FindMembers(groups);
}
Group G1
memberOf: G2 G4
members: G2 G3 G4 G5 G6
users: U3 U2 U1
Group G2
memberOf: G1 G4
members: G1 G3 G4 G5 G6
users: U2 U1 U3
Group G3
memberOf: G1 G2 G4
members: G5 G6
users: U2 U3
Group G4
memberOf: G1 G2
members: G1 G2 G3 G5 G6
users: U1 U3 U2
Group G5
memberOf: G1 G2 G3 G4
members: G6
users: U2 U3
Group G6
memberOf: G1 G2 G3 G4 G5
members:
users: U3
Simple Solution
- Anonymous July 23, 20151.) Start with all keys in dictionary.
2.) For each key do a BFS search , putting groups in a hashset of used group , so that you don't queue them again in BFS. When you encounter a user in queue just add it to group list , when you encounter a group put group in queue for going deep.