Problem Statement |
| | A small company has recently been growing quickly and has decided that it needs to restructure its organisation. In the past, there were no permanent managers and project teams were formed on an ad-hoc basis depending on which employees were available at the time. This has lead to a situation where many of the employees have managed each other at some time in the past. Now that the company is bigger, it wants to impose a more formal hierarchical structure. The company is to be divided into divisions, each of which will be structured as a tree. One employee in each division will be assigned as the division leader and can be the permanent manager of some other employees. These employees can in turn manage futher employees, and so on. Each employee will belong to exactly one division and each employee in a division other than the division leader will have a permanent manager in the division.
The company knows that such a restructuring may lead to ill-feeling amongst the employees, particularly if an employee ends up being managed permanently by another employee that he or she has managed in the past. It has therefore come up with the following model to try to minimise this ill-feeling. If an employee has managed a person in the past, then he or she feels superior to that person. This is also transitive, so if A has managed B, and B has managed C, then A feels superior to both B and C, even if A has not directly managed C. More formally, an employee X0 feels superior to another employee Xk, if and only if there exists a sequence of employees X0, X1, X2 ... Xk, where employeee Xi has managed employee Xi+1 for each value of i < k. This can clearly lead to cases where each one of a pair of employees feels superior to the other and such a pair is termed mutually superior. These pairs of employees tend to spend a lot of time arguing about who is superior, so the company wishes to ensure they are separated in the new company structure. It has put the following restrictions on the structure of the new divisions.
- The new permanent manager of an employee must have managed that employee in the past.
- No employee can feel superior to his or her direct permanent manager.
- No pair of mutually superior employees can have the same direct permanent manager.
The company wishes to end up with as few divisions as possible. You are given a String[] hasManaged, which details which employees have managed others in the past. Character j of element i will be 'Y' if employee i has managed employee j in the past and 'N' otherwise. Return the minimum number of divisions that the company must create in order to satisfy the above restrictions. |
| |
Definition |
| | | Class: | CompanyRestructuring | | Method: | fewestDivisions | | Parameters: | String[] | | Returns: | int | | Method signature: | int fewestDivisions(String[] hasManaged) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | hasManaged will contain between 1 and 50 elements, inclusive. |
| - | Each element of hasManaged will contain the same number of characters as there are elements in hasManaged. |
| - | Each character of hasManaged will be 'Y' or 'N'. |
| - | Character i of element i of hasManaged will be 'N'. |
| |
Examples |
| 0) | |
| | {"NNNN","NNYN","NNNN","YYYN"} |
| Returns: 1 | There are no mutually superior employees here and only a single division is needed. There are 2 possible structures:
3
/ \
0 1
\
2
or
3
/ | \
0 1 2
|
|
|
| 1) | |
| | {"NNYN","NNYN","YNNN","YYYN"} |
| Returns: 1 | | This case is similar to case 0), except now employees 0 and 2 are mutually superior, so cannot have the same manager. The second structure shown above is therefore invalid, but the first one is still possible. |
|
|
| 2) | |
| | {"NYNNN","NNYNN","NNNYN","NNNNY","YNNNN"} |
| Returns: 5 | | Everybody feels superior to everybody else, so there is no way that any of them can work in the same division. |
|
|
| 3) | |
| | {"NYNYYYNN"
,"NNNNYYNN"
,"NYNNYYNN"
,"NNYNYYNN"
,"NNNNNNNN"
,"NYYNYNNN"
,"YYNYYYNN"
,"YYNYYYYN"} |
| Returns: 1 | |
|
| 4) | |
| | {"NYNYNNYYNYNNNYYNYNYY"
,"YNNNNNYYNNNYYNYNYNYY"
,"NNNNNNYYNNNYYNYNNNNY"
,"YNYNNNNYNNNYNNYNYNNY"
,"NYNNNNNYYYYNYNYYNNYN"
,"YYYYNNYNYNNNNNYYNYNY"
,"NNNNNNNNNNNYYNNNNNYY"
,"NNNNNNYNNNNYYNYNNNYN"
,"NYYYNNNYNNNNYYNYYNYY"
,"NNYNNNYYNNNNYNNNNNYY"
,"YYNNNYNNYNNNNYNNYNYY"
,"NNNNNNNYNNNNYNYNNNNY"
,"NNNNNNYNNNNYNNNNNNNN"
,"NNYNNNNNNNNYYNYNNYYN"
,"NNNNNNNNNNNYNNNNNNNY"
,"YNYYNYYNNNYYNNNNYNYY"
,"NYNNNNNYNYNYYYYNNNNY"
,"NNYNNNNYNYNYYYNNNNYY"
,"NNNNNNNYNNNYNNNNNNNY"
,"NNNNNNYYNNNYYNYNNNYN"} |
| Returns: 4 | |
|
| 5) | |
| | {"NNNYNNNNNNNYNNNNNNNN"
,"NNNNNNYNNYNNNNNYNYYN"
,"YNNNNNYNYNNNNNNNNNNY"
,"YNNNNNNNNNNNNNNNNNNN"
,"NNYNNNYNYNNYNNYNNNNY"
,"NNNYNNNNNNNYNNYYYNYY"
,"NNYYNNNNYNNNNNNNNNNY"
,"NYNNNYNNYNNNYNYNYNNN"
,"NNNNNNNNNNNNNNNNNNNN"
,"YNNNNNNNNNNYNNYYNNYN"
,"NNYYNYNNYYNNNNYYNYNN"
,"NNNNNNNNYNNNNNNNNNNN"
,"NNNYYNYNYYYYNNNNYNYY"
,"NNYYNYNNYYYYNNNNNYNY"
,"NNYYYNNNYNNNNNNNNNNN"
,"YNNYYYNNNNNNNNYNYNYY"
,"NNNNYNYNNNNYNNYNNNNN"
,"YNNYYYYNNYNNYNNNYNYN"
,"YNNYYYYNYNNYNNYYYNNY"
,"YNYNNNNNYNNYNNNNNNNN"} |
| Returns: 2 | |
|
| 6) | |
| | {"NNNNN","NNNNN","NNNNN","NNNNN","NNNNN"} |
| Returns: 5 | | Nobody has managed anybody in the past, so nobody can be a manager in the new structure either. |
|
|