PROBLEM STATEMENT
As a newly hired HR manager for a business you need to evaluate the in place
organizational structure. Unfortunately, all the previous manager left you was
a napkin with a pile of names scratched on it. As a quick fix, you want a
program which will report if there are any catastrophic problems (loops in the
chain of authority or multiple CEO's) and if none of those are found, give you
the length of the longest potential line of command.
The previous HR manager recorded the organization structure on the napkin with
entries like this: NAME:BOSS,BOSS,...,BOSS. The NAME is the name of the
employee, and the comma seperated list of BOSS are all the people whom the
employee reports too. All the names are case sensitive ("Jim Black" is not
"jim black"). Names contain only the characters (A-Z, a-z and spaces ' ').
Names cannot start or end with a space. Every employee who is still working
for the company is listed in a NAME entry.
BOSS entries may reference people (such as the former HR manager) who have been
fired. In that case, the entry should be ignored. Any employee who has no
valid BOSS entries is a CEO. If there is more then 1 CEO, then that is a
catastrophic error and you should return -1 (the code to give up and start
working on your resume!)
A loop in the command structure is where, by any set of intermediaries, two
employees both have authority over each other. A simple example would be: one
of Jim's bosses is Joe, and one of Joe's bosses is Jim. The situation is the
same if Jim's boss is Joe, but Jim has authority to give orders to Tia who can
order Bob who can order Sam who is one of Joe's bosses. In any situation, this
is a horrible error, and you should return -1.
If no catastrophic errors are found, then it's time to get to work! Return the
longest possible path a message could take, traveling the CEO down the chain of
command. If the CEO is the only employee, then the length of the path is 0.
The output should be -1 if there is a catastrophic error, or the length of the
longest possible path a message could take traveling down the chain of command.
DEFINITION
Class name: Manager
Method name: orgChart
Parameters: String[]
Return type: int
Method signature: int orgChart( String[] napkin )
Be sure to make your method public.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
napkin is a String[] of 1-50 elements (inclusive)
each element has the form NAME:BOSS,...,BOSS
each NAME:BOSS list is 2-50 (inclusive) characters in length (the shortest
possible list would be something like "C:").
NAME and BOSS will contain only letters (a-z and A-Z) and the space ' '
character and will not begin or end with a space.
A NAME or BOSS must contain at least 1 character.
There will be no duplicate NAME's in the String[].
There will be no duplicate BOSS's in any specific NAME:BOSS,BOSS list.
There will be no one who is their own BOSS.
EXAMPLES:
napkin { "Jill:George,Bill,Duby", "Duby:Colin p", "Colin p:George", "George:" }
Returns 3, because the longest possible message chain would be: George (CEO) ->
Colin p -> Duby -> Jill.
napkin { "Bob:" }
Returns 0, because Bob the CEO has no one to issue a message to.
napkin { "Bob:Paula,James,Quirk,Joe", "Quirk:Paula,James", "Paula:James",
"James:Joe", "Joe:Quirk" }
Returns -1, because the following chain is possible: Quirk -> Joe -> James ->
Quirk (ie there is a loop in the chain of command).
napkin { "Joe:", "Walter:Bob" }
Returns -1 because since Bob is not an employee, Walter does not have a boss,
which leaves Walter and Joe both as CEO.
napkin { "Me:", "Mini Me:Me", "Irish:Mini Me,Me", "Ninja:Me,Irish",
"Scientist:Ninja", "Engineer:Scientist" }
Returns 5.