How should I practice Manager Direct-Report Salary Averages?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Manager Direct-Report Salary Averages associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Manager Direct-Report Salary Averages

Amazon● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given an organization of n employees with IDs 0 through n - 1. Employee i earns salaries[i] and has direct manager managers[i]. A value of -1 means the employee has no manager. These links form a valid forest: an employee has at most one manager, and following manager links never creates a cycle.

For this exercise, a manager’s salary average uses only employees who report directly to that manager:

Include employee i in manager m’s average exactly when managers[i] == m.
Exclude the manager’s own salary and the salaries of indirect descendants.
A direct report is included even if that employee also manages other employees.
Only employees with at least one direct report are eligible for the maximum-average selection. Zero salaries are valid and still count as reports.

Find the eligible manager with the greatest direct-report salary average. Compare exact averages, and break an exact tie by the smaller employee ID. If there is no eligible manager, use -1.

Also answer each manager ID in queries. Return its direct-report salary average as a reduced fraction numerator/denominator, with a positive denominator. Represent an integer as a fraction with denominator 1, including 0/1. Return NONE when that employee has no direct reports.

Return a string array with the selected manager ID in decimal at position 0, followed by one fraction or NONE for every query, in the given order. An empty query array still returns the first string. Repeated queries give repeated answers; queries do not modify the organization.

Function

managerSalaryAverages(managers: int[], salaries: int[], queries: int[]) → String[]

Examples

Example 1

managers = [-1,0,0,1,1]salaries = [999,100,200,40,60]queries = [0,1,2]return = ["0","150/1","50/1","NONE"]

Manager 0 has direct reports 1 and 2, whose average is (100 + 200) / 2 = 150. Manager 1 has direct reports 3 and 4, whose average is 50. Therefore manager 0 wins. Salary 999 is excluded from its own team, and indirect reports 3 and 4 do not enter its average. Employee 2 has no direct reports.

Example 2

managers = [-1,0,0,-1,3,3]salaries = [900,2,3,600,1,4]queries = [3,0,4]return = ["0","5/2","5/2","NONE"]

Managers 0 and 3 both have average 5/2, so the smaller ID 0 wins. Queries retain their given order. Employee 4 is a leaf and returns NONE.

Example 3

managers = [-1,-1]salaries = [10,20]queries = []return = ["-1"]

Both employees are roots with no direct reports, so no manager is eligible and the first result is -1. There are no average queries, so the returned array contains only that string.

Constraints

1 <= n == managers.length == salaries.length <= 2000.
managers[i] is -1 or a valid employee ID different from i; the manager relation is acyclic. There may be several roots, and a manager’s ID may be greater than a report’s ID.
0 <= salaries[i] <= 10^9.
0 <= queries.length <= 2000; every query is an employee ID in 0..n-1.
All salaries are integers. Sums are at most 2 * 10^12, and products used to compare two averages are at most 4 * 10^15; use signed 64-bit arithmetic.
Invalid manager links, cycles and unknown employee IDs are outside the accepted domain.