The Pay Ladder

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citi

Problem

An HR analytics export hands you a list of employee records, each carrying a salary, together with a cutoff n. Return the n highest distinct salaries, largest first, building the selection yourself without sorted, .sort, nlargest, or any similar helper. When there are fewer than n distinct salaries, return every one you have.

Climb the ladder the hard way. No shortcuts allowed.

Example

Input:

employees = [{"name":"Alice","salary":90000},{"name":"Bob","salary":75000},{"name":"Charlie","salary":90000},{"name":"Dave","salary":60000}], n = 2

Output:

[90000,75000]

Worked solution and explanation

What this really tests

Behind the payroll framing this is a hand-rolled top-N selection: pull the n largest values out of a collection when the one tool that would make it trivial, sorted(salaries, reverse=True)[:n], is off the table. Anyone can call a sort. The skill being probed is whether you can run your own repeated-maximum passes and, first, collapse duplicate salaries to distinct values. Miss that dedup and a salary three people share eats three of your n slots, so the answer comes back padded with repeats and short on the distinct values that were asked for.

How to get there

Step 1: Collapse to distinct salaries

Walk the records and add each emp['salary'] to a set. The set does the deduplication for free, so two people on the same pay count once toward n.

Step 2: Take the maximum, then take it out

Copy the set into a remaining list you can shrink. Scan it for the largest value with a running highest, append that to result, then remove it from remaining so the next scan finds the new maximum.

Step 3: Stop at n or when you run out

Repeat the max-and-remove while remaining is non-empty and result holds fewer than n values. That second guard is what returns everything gracefully when there are fewer than n distinct salaries.

The solution

Repeated max-selection over distinct salaries
def top_n_salaries(employees, n):
    unique_salaries = set()
    for emp in employees:
        unique_salaries.add(emp['salary'])
    remaining = list(unique_salaries)
    result = []
    while remaining and len(result) < n:
        highest = remaining[0]
        for salary in remaining:
            if salary > highest:
                highest = salary
        result.append(highest)
        remaining.remove(highest)
    return result

Common follow-up questions