Connection Status:
Competition Arena > PermissionTree

PermissionTree

SRM 218 · 2004-11-04 · by erinn

SRM 218 · 2004-11-04 · by erinn · Recursion, Search
Class Name: PermissionTree
Return Type: int[]
Method Name: findHome
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

You are building a web site for your clients to access, and want to create a welcome screen that serves as a starting point where they can view various pieces of data.

All of your data is stored hierarchically in folders, much like a file system. You are given a String[] folders, where each element includes the id of the parent folder, a space, and a comma-delimited list of users who have permission to view that folder. The root level folder, 0, is its own parent, and all folders are descendants of the root node. Additionally, you are given a String[], users, which contains a list of the users who will be accessing the web site.

For each user, you are to determine which folder should serve as their "home folder". A user's home folder is defined as the deepest folder which contains all of the folders the user can access.

Suppose the data is very simple, such that folders looks like this:

folders = { "0 Administrator",
            "0 Joe,Phil",
            "0 Joe" }

and your users are Administrator, Joe, and Phil. Clearly, the Administrator's home folder is 0, since he can access the root node. Similarly, Phil's home folder is 1, since he can only access folder 1. But Joe can access folders 1 and 2, so his home folder must be folder 0, which contains folders 1 and 2.

The return value should be a int[], indicating the home folder for each corresponding element of users. Users who have access to no folders are assigned a home folder of -1.

Notes

  • User names are case-sensitive

Constraints

  • folders will have between 1 and 50 elements, inclusive.
  • users will have between 1 and 50 elements, inclusive.
  • Each element of users will have between 1 and 50 alphabetic ('A'-'Z' or 'a'-'z') characters.
  • Each element of folders will be of the form " " (quotes added for clarity).
  • Each element of folders will contain between 3 and 50 characters, inclusive.
  • will be an integer index of an element of folders, between 0 and n - 1, inclusive, where n is the number of elements in folders. Leading zeroes are permitted.
  • will be a comma-delimited list of user names, with no spaces, and containing only the characters 'A'-'Z', 'a'-'z', or ','.
  • cannot be empty, but may contain repeats.
  • The elements of folders will define a valid tree.
Examples
0)
{"0 Admin", "0 Joe,Phil", "0 Joe"}
{"Admin", "Joe", "Phil"}
Returns: { 0,  0,  1 }

The example from the problem statement.

1)
{"0 Admin"}
{"Peter", "Paul", "Mary"}
Returns: { -1,  -1,  -1 }

There is not much to access, and only the admin can see it.

2)
{"0 Admin", "2 John", "0 Peter,John", "0 Tim", "1 John"}
{"John"}
Returns: { 2 }

Notice that, apart from the root node always being (0), other folders are not necessarily defined in order of depth. (Here, folder 2 is the parent of folder 1.)

3)
{"0 Administrator", "0 Admin"}
{"Admin"}
Returns: { 1 }
4)
{"0 Admin",
"0 Jeff", "1 Mark,Tim", "1 Tim,Jeff",
"0 Dan", "4 Ed", "4 Tom", "4 Kyle,Ed",
"0 Ben", "8 Rich", "8 Sam", "8 Tim"}
{"Jeff", "Ed", "Tim", "Steve"}
Returns: { 1,  4,  0,  -1 }
5)
{"0 Admin", "0 Bob,Joe,Bob", "0 Joe"}
{"Joe", "Bob"}
Returns: { 0,  1 }

Notice here that a username can be repeated for a given folder.

Submissions are judged against all 14 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PermissionTree with a public method vector<int> findHome(vector<string> folders, vector<string> users) · 14 test cases · 2 s / 256 MB per case

Submitting as anonymous