enok
BAN USER- 1of 1 vote
AnswersWrite a program in that determines the members and parents of nested groups without using recursion.
These are the requirements.
1. A group can have 0 or more members.
2. A group can be member of one or more groups
3. A group can be member of itself.
4. If there is a path from a group either directly or through multiple hops, then that user is considered as member of the group.
5. A group can have users or groups as members
EX: Input looks like thisvar groupMembers = new Dictionary<string, HashSet<string>> { { "G4", new HashSet<string> { "U1","G1"} }, { "G1", new HashSet<string> { "G2","G3","G6"} }, { "G3", new HashSet<string> { "G3","G5"} }, { "G2", new HashSet<string> { "G4","U2"} }, { "G5", new HashSet<string> { "U2","G6"} }, { "G6", new HashSet<string> { "U3"} }, };
Signature of function is:
private List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
You need to make sure that you take care of cycles in the graph and not go into infinite recursion.
Output should look like a list of groups where a group is as follows.private class MyGroup { public string Identity { get; set; } public Dictionary<string, MyGroup> MemberOf { get; set; } public Dictionary<string, MyGroup> Members { get; set; } public HashSet<string> Users { get; set; } public MyGroup(string name) { this.Identity = name; this.MemberOf = new Dictionary<string, MyGroup>(); this.Members = new Dictionary<string, MyGroup>(); this.Users = new HashSet<string>(); } }
Each group object should contain all the groups it's a memberOf (directly or indirectly), all the groups that are it's members (directly or indirectly) and all users that are it's members.
- enok in United States| Report Duplicate | Flag | PURGE
Google Senior Software Development Engineer Algorithm - 3of 3 votes
AnswersGiven a dictionary that contains mapping of employee and his/her manager like this
- enok in United States
Dictionary<string, string> employees = new Dictionary<string, string>()
{
{ "A","C" },
{ "B","C" },
{ "C","F" },
{ "D","E" },
{ "E","F" },
{ "F","F" }
};
Write a function to get no of employees under each manager in the hierarchy not just their direct reports.
In the above dictionary the root node/ceo is listed as reporting to himself.
Output should be a Dictionary<string,int> that contains this
A - 0
B - 0
C - 2
D - 0
E - 1
F - 5| Report Duplicate | Flag | PURGE
Microsoft SDE1 Algorithm - 2of 2 votes
AnswersYou are given a text file that has list of dependencies between (any) two projects in the soure code repository. Write an algorithm to determine the build order ie. which project needs to be build first, followed by which project..based on the dependencies.
- enok in United States
Bonus point: If you can detect any circular dependencies and throw an exception if found.
EX: ProjectDependencies.txt
a -> b (means 'a' depends on 'b'..so 'b' needs to be built first and then 'a')
b -> c
b -> d
c -> d
Then the build order can be
d , c, b, a in that order| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
This sounds like a good plan. Do you have pseudo code for this approach? Would love to see how the algorithm looks in real code
- enok July 23, 2015