FastPrepCompany Score with Manager Caps
Problems/Company Score with Manager Caps

Company Score with Manager Caps

Indeed logoIndeed● HardNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: Several reports describe this test, and one author confirmed its input: each employee has a 0-based ID, a score and a manager, and the answer is the company's total score. The last part asks, for T = 1, 2 and 10, which T people to train for the highest total, where training lifts the cap that a manager's score puts on everyone below.

The reports do not give the exact rules or any limits. Here, an untrained employee's score is cut to their manager's effective score, so a low score holds back everyone below it. A trained employee keeps their own score and still holds back their own reports. The top employee has manager -1, and you train at most t people, with t up to 10. The original test read the input and printed the answer. Here you get the arrays and return the total. The limits on the number of employees and on the scores are practice choices. The test also asked which data structure you would use, your time complexity, and how you could do better. Those parts are not judged here, and the editorial covers them. One earlier report gives a different optional last part, about how to handle an additional element. It is not judged here either.

The judged task matches the reports at about 70%.

A company has n employees with IDs 0 to n - 1. Employee i has the score scores[i] and reports to the manager managers[i]. The top employee has managers[i] == -1. Everyone else reaches the top employee by following managers.

A manager holds back the people who report to them. Each employee's effective score is:

  • their own score, if they are the top employee or have been trained;
  • otherwise, the smaller of their own score and their manager's effective score.

So an untrained employee can never do better than the person they report to, and a low score near the top holds back everyone below it. A trained employee keeps their own score and is no longer held back by anyone above them. They still hold back the people who report to them, like any other manager.

The company's total score is the sum of all effective scores. You may train at most t employees. Return the highest total score you can reach.

Function

maxCompanyScore(scores: int[], managers: int[], t: int) → long

Examples

Example 1

scores = [5,8,3,6]managers = [-1,0,0,1]t = 0return = 18

No one is trained. Employee 0 is the top employee and keeps 5. Employee 1 reports to 0, so it gets min(8, 5) = 5. Employee 2 gets min(3, 5) = 3. Employee 3 reports to employee 1, whose score is now 5, so it gets min(6, 5) = 5.

The total is 5 + 5 + 3 + 5 = 18.

Example 2

scores = [4,9,2,7,8]managers = [2,0,-1,0,3]t = 1return = 20

Employee 2 is the top employee with score 2, so with no training every score is cut to 2 and the total is 10.

Train employee 3. It keeps its 7, and employee 4 reports to it, so employee 4 gets min(8, 7) = 7. Employees 0 and 1 still get 2. The total is 2 + 2 + 2 + 7 + 7 = 20.

Training employee 0 gives 2 + 4 + 4 + 4 + 4 = 18, employee 1 gives 17, and employee 4 gives 16, so 20 is the best.

Example 3

scores = [1,5,10,10]managers = [-1,0,1,1]t = 2return = 22

With no training every score is 1, for a total of 4. Training only employee 1 gives 1 + 5 + 5 + 5 = 16, the best single choice.

Adding a second person to employee 1 gives at most 1 + 5 + 10 + 5 = 21. Training employees 2 and 3 instead gives 1 + 1 + 10 + 10 = 22, which is the best pair.

Constraints

  • 1 <= n <= 500, where n == scores.length
  • managers.length == n
  • 1 <= scores[i] <= 10^9
  • -1 <= managers[i] <= n - 1
  • Exactly one employee has managers[i] == -1. Every other employee has a manager other than themselves, and following managers from any employee reaches the top employee.
  • 0 <= t <= min(10, n)

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public long maxCompanyScore(int[] scores, int[] managers, int t) {
        // Write your code here.
    }
}
Checking account…