找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3531|回复: 6
收起左侧

[Microsoft] MS昂塞

[复制链接]

1161

主题

184

精华

3664

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3664
发表于 2-23-2017 03:56 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-24-2017 10:18 AM 编辑 1 G1 C1 B7 `) L  @+ Z0 Z

) d0 N! F9 ^% {$ ?/ _Write a program in that determines the members and parents of nested groups without using recursion.
, O) t- a4 P8 I1 I9 D& S1 R% N5 K( Y% \
( ~, M6 ?8 @% K3 [+ rThese are the requirements.' {! a8 y! m3 Q6 R& p
) C" g: S: e% M6 I
1. A group can have 0 or more members.
: y$ ]1 z. A, g2 J; s) q2. A group can be member of one or more groups7 @( _- V& f5 {: O: j* k
3. A group can be member of itself.+ R9 D! U& u) j, b
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 N; [5 O' }3 ^& O- Y7 m
5. A group can have users or groups as members6 ?3 x. o1 z9 @$ B8 e4 B

6 l2 \2 f" S3 E$ MEX: Input looks like this</p><p><code><pre class="language-java">var groupMembers = new Dictionary<string, HashSet<string>>* J( |8 m3 O. O
            {
: a# h+ n7 L% z0 v) y# n                {  "G4", new HashSet<string> { "U1","G1"} },
0 C+ M# h6 G7 N                {  "G1", new HashSet<string> { "G2","G3","G6"} },( j; a/ e4 h+ T2 p! x: v
                {  "G3", new HashSet<string> { "G3","G5"} },% r6 ^, L( q2 n5 @8 ?0 e; Y
                {  "G2", new HashSet<string> { "G4","U2"} },
9 `: Z7 |; p2 b$ n! S) N                {  "G5", new HashSet<string> { "U2","G6"} },
0 P; O+ C3 s7 z4 T3 \5 t                {  "G6", new HashSet<string> { "U3"} },' g" E5 U# e, S, i7 `9 d8 {# d4 x, A
            };: p0 v  H9 H: k5 ~2 |! A, d; e
Signature of function is:& n# b8 h5 l+ W
private List<MyGroup> FindMembers(Dictionary<string, HashSet<string>> groupMembers)
/ [3 U4 q3 o' |# iYou need to make sure that you take care of cycles in the graph and not go into infinite recursion.% W1 w8 X" `6 Z0 ~
0 H" q7 ^9 i; r% l: H! l
Output should look like a list of groups where a group is as follows.
7 H3 v- n0 `, O: o5 u. d- Z
6 X  N$ @) E' J$ W1 v7 jprivate class MyGroup5 j6 ^% }; K1 k4 G. l9 P
    {
  E, Q2 s# @% ^) J" N        public string Identity { get; set; }
# Y# V" m6 p: @9 H$ x9 C7 t, {5 O8 _& G" T8 |& X: U5 D8 z$ l
        public Dictionary<string, MyGroup> MemberOf { get; set; }* q$ y- b; H4 N; }, \- Q2 G# Y

; p( O6 i0 v3 o  c# i% B# J        public Dictionary<string, MyGroup> Members { get; set; }7 ~$ H6 s+ i8 j* A$ f6 P
* W7 m" `+ y( T' X# J5 W
        public HashSet<string> Users { get; set; }7 V4 j* _' [5 l. r! v9 V
: y4 n) I# N4 T1 }6 t- M. I
        public MyGroup(string name)
( u9 }: U: {$ a3 a2 {        {5 @2 O  z/ J: g3 }, S
            this.Identity = name;
0 k+ m/ M+ Y2 m            this.MemberOf = new Dictionary<string, MyGroup>();
. h  j7 N$ T: A& c+ `% }/ L            this.Members = new Dictionary<string, MyGroup>();
; }$ z2 C2 g) N* Y            this.Users = new HashSet<string>();
1 e( ]" A+ h% B5 q# F9 g+ @$ i        }
" w4 G0 M" C  W" V5 X}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.

1178

主题

174

精华

3584

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3584
发表于 2-23-2017 03:56 PM | 显示全部楼层

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

1157

主题

163

精华

3497

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3497
发表于 2-23-2017 03:56 PM | 显示全部楼层

working code?

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表