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
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
Definition
- Class:
- PermissionTree
- Method:
- findHome
- Parameters:
- String[], String[]
- Returns:
- int[]
- Method signature:
- int[] findHome(String[] folders, String[] users)
- (be sure your method is public)
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 Admin", "0 Joe,Phil", "0 Joe"}
{"Admin", "Joe", "Phil"}
Returns: { 0, 0, 1 }
The example from the problem statement.
{"0 Admin"}
{"Peter", "Paul", "Mary"}
Returns: { -1, -1, -1 }
There is not much to access, and only the admin can see it.
{"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.)
{"0 Administrator", "0 Admin"}
{"Admin"}
Returns: { 1 }
{"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 }
{"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.
{"0 Root", "00 Test", "001 A", "000 B", "00002 A,B,C"}
{"A", "B", "C"}
Returns: { 2, 0, 4 }
{ "0 Admin", "0 Bob,Joe,Bob", "0 Joe" }
{ "Joe", "Bob" }
Returns: { 0, 1 }
{ "0 Admin" }
{ "Peter", "Paul", "Mary" }
Returns: { -1, -1, -1 }
{ "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 }
{ "0 Admin", "0 A", "0 AB", "0 B" }
{ "A", "B" }
Returns: { 1, 3 }
{ "0 Admin", "0 Joe,Phil", "0 Joe" }
{ "Admin", "Joe", "Phil" }
Returns: { 0, 0, 1 }
{ "0 Admin", "8 b", "10 c", "10 e", "10 e", "9 e", "8 e", "8 e", "0 a", "0 a", "0 a", "4 c,d", "1 b,d", "4 d", "1 d", "4 d", "1 d", "3 d", "3 c,d", "3 c,d", "6 d", "6 d", "6 b,d" }
{ "Admin", "a", "b", "c", "d" }
Returns: { 0, 0, 8, 10, 0 }
{ "0 Adam", "0 Joe,Phil", "0 Joe", "0 Joe,Phil,Adam,Admin" }
{ "Admin", "Joe", "Phil", "Adam" }
Returns: { 3, 0, 0, 0 }