Search code examples
pythoncocoapyobjc

Flatten structure and return users for given group (iOS)

Given a dictionary of a directed graph, representing nested groups and their members, flatten the structure and return all the users for a given group.

MEMBERS_BY_GROUPS = {
    'Group0': {
        'NestedGroups': ['Group3'],
        'Members': ['User0', 'User1']
    },
    'Group1': {
        'NestedGroups': ['Group3'],
        'Members': ['User2', 'User3', 'User4']
    },
    'Group2': {
        'NestedGroups': ['Group3', 'Group5'],
        'Members': ['User4', 'User5']
    },
    'Group3': {
        'NestedGroups': ['Group4'],
        'Members': ['User6', 'User7']
    },
    'Group4': {
        'NestedGroups': [],
        'Members': ['User8', 'User9']
    },
    'Group5': {
        'NestedGroups': [],
        'Members': ['User10', 'User11']
    }
}


def flattenGroup(members_by_groups, group_name): // (MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']

I was given this as an assignment and I do not know how to answer. How do I go about this?

Solution

  • I was given this as an assignment and I do not know how to answer. How do I go about this?

    Well you start by designing an algorithm to solve the problem, then you implement that algorithm a programming language - Objective-C in your case.

    So start by looking at the problem:

    Given a dictionary of a directed graph, representing nested groups and their members, flatten the structure and return all the users for a given group.

    Given you've been given this as an assignment I assume you know what a dictionary and a directed graph are. The sample data also appears to use arrays - the lists of items in square brackets ([, ]).

    The question refers to the data representing a directed graph, the sample data happens to represent a directed acyclic graph (DAG). If there can be cycles in your data you will need to handle them in your algorithm, if you don't your algorithm could quite literally end up going around circles forever... For the moment let's assume you do actually just have a DAG - no cycles.

    The question also includes:

    def flattenGroup(members_by_groups, group_name):

    along with sample data and a sample query:

    flattenGroup(MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']

    So what information do we have from the question:

    • "Given a dictionary of a directed graph" - You have a directed graph, we're assuming its a DAG, represented as a dictionary
    • "representing nested groups and their members" & the sample data - Each node/entry in the dictionary is itself a dictionary containing two items: a list (array) of members and a list of nested groups
    • "flatten the structure and return all the users for a given group" & "def flattenGroup(members_by_groups, group_name):" - Produce an algorithm flattenGroup which given the data and a group name returns all the members in that group and its nested groups.
    • "flattenGroup(MEMBERS_BY_GROUPS, 'Group2') -> ['User4', 'User5', 'User6', 'User7', 'User8', 'User9',, 'User10', 'User11']" - It appears the query should return a list (array) (the [ & ]), contain no duplicates (e.g. User4 only occurs once - check the sample data, it is found twice when following the DAG), and be ordered (that might just be coincidental);

    Given that we can just read off an algorithm (in pseudo code):

    def flattenGroup(members_by_groups, group_name):
    { members of group_name } // the set of all members of group_name
    ∪ // union
    { members of first nested group } // the set of all members of the first nested group
    ∪ // union
    ...
    ∪ // union
    { members of last nested group }

    Note: I've written that using sets, both because it makes sense to describe the algorithm that way and as sets don't contain duplicates. Whether you implement it using sets or lists is an implementation detail.

    Does the algorithm make sense to you? Do not proceed until it does.

    Now lets elaborate the algorithm. The first sub-expression is:

    { members of group_name } // the set of all members of group_name

    that is pretty simple, each node contains a list of members, no need to elaborate this further. The second and subsequent sub-expressions are of the form:

    { members of first nested group } // the set of all members of the first nested group

    that is certainly more complicated because the members of a nested group include in turn its nested groups, so this could do with elaborating but what to? Well the task of this sub-expression is exactly the same as the algorithm we are writing, except for a different group, so that line is just:

    flattenGroup(members_by_groups, first nested group)

    and the whole algorithm is now:

    def flattenGroup(members_by_groups, group_name):
    { members of group_name }
    ∪
    flattenGroup(members_by_groups, first nested group)
    ∪
    ...
    ∪
    flattenGroup(members_by_groups, last nested group)

    Do you understand why this algorithm would fail if there were cycles? Do not continue unless you do!

    Well now you have an algorithm, time to write some code...

    Which is your job! We've used dictionaries, arrays and sets, these are provided in Objective-C by Cocoa's NSDictionary, NSArray, and NSSet along with NSMutableX versions of each.

    Go read the documentation and code your algorithm. If you get stuck ask a new question, include your algorithm, the code you've written, and the problem you have. Somebody will probably help you.

    HTH