Problem

Table: Candidates

+-------------+------+
| Column Name | Type |
+-------------+------+
| employee_id | int  |
| experience  | enum |
| salary      | int  |
+-------------+------+
employee_id is the column with unique values for this table.
experience is an ENUM (category) of types ('Senior', 'Junior').
Each row of this table indicates the id of a candidate, their monthly salary, and their experience.
The salary of each candidate is guaranteed to be **unique**.

A company wants to hire new employees. The budget of the company for the salaries is $70000. The company’s criteria for hiring are:

  1. Keep hiring the senior with the smallest salary until you cannot hire any more seniors.
  2. Use the remaining budget to hire the junior with the smallest salary.
  3. Keep hiring the junior with the smallest salary until you cannot hire any more juniors.

Write a solution to find the ids of seniors and juniors hired under the mentioned criteria.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Input:
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 10000  |
| 9           | Junior     | 15000  |
| 2           | Senior     | 20000  |
| 11          | Senior     | 16000  |
| 13          | Senior     | 50000  |
| 4           | Junior     | 40000  |
+-------------+------------+--------+
Output: 
+-------------+
| employee_id |
+-------------+
| 11          |
| 2           |
| 1           |
| 9           |
+-------------+
Explanation: 
We can hire 2 seniors with IDs (11, 2). Since the budget is $70000 and the sum of their salaries is $36000, we still have $34000 but they are not enough to hire the senior candidate with ID 13.
We can hire 2 juniors with IDs (1, 9). Since the remaining budget is $34000 and the sum of their salaries is $25000, we still have $9000 but they are not enough to hire the junior candidate with ID 4.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Input:
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 25000  |
| 9           | Junior     | 10000  |
| 2           | Senior     | 85000  |
| 11          | Senior     | 80000  |
| 13          | Senior     | 90000  |
| 4           | Junior     | 30000  |
+-------------+------------+--------+
Output: 
+-------------+
| employee_id |
+-------------+
| 9           |
| 1           |
| 4           |
+-------------+
Explanation: 
We cannot hire any seniors with the current budget as we need at least $80000 to hire one senior.
We can hire all three juniors with the remaining budget.

Solution

Method 1 - Greedy with Window Functions and Unique Salaries

We sort seniors and hire as many as possible, then use the remaining budget to hire juniors, all by salary ascending. Since salaries are unique, we can use window functions to track cumulative sums and select the correct employees.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

WITH seniors AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY salary) rn, SUM(salary) OVER (ORDER BY salary) sm
  FROM Candidates WHERE experience = 'Senior'
),
max_senior AS (
  SELECT IFNULL(MAX(rn), 0) AS cnt, IFNULL(MAX(sm), 0) AS cost FROM seniors WHERE sm <= 70000
),
selected_seniors AS (
  SELECT employee_id FROM seniors, max_senior WHERE rn <= max_senior.cnt
),
juniors AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY salary) rn, SUM(salary) OVER (ORDER BY salary) sm
  FROM Candidates WHERE experience = 'Junior'
),
max_junior AS (
  SELECT IFNULL(MAX(rn), 0) AS cnt, IFNULL(MAX(sm), 0) AS cost FROM juniors, max_senior WHERE sm <= 70000 - max_senior.cost
),
selected_juniors AS (
  SELECT employee_id FROM juniors, max_junior WHERE rn <= max_junior.cnt
)
SELECT employee_id FROM selected_seniors
UNION ALL
SELECT employee_id FROM selected_juniors;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

WITH seniors AS (
  SELECT employee_id, salary, ROW_NUMBER() OVER (ORDER BY salary) rn, SUM(salary) OVER (ORDER BY salary) sm
  FROM Candidates WHERE experience = 'Senior'
),
max_senior AS (
  SELECT NVL(MAX(rn), 0) AS cnt, NVL(MAX(sm), 0) AS cost FROM seniors WHERE sm <= 70000
),
selected_seniors AS (
  SELECT employee_id FROM seniors, max_senior WHERE rn <= max_senior.cnt
),
juniors AS (
  SELECT employee_id, salary, ROW_NUMBER() OVER (ORDER BY salary) rn, SUM(salary) OVER (ORDER BY salary) sm
  FROM Candidates WHERE experience = 'Junior'
),
max_junior AS (
  SELECT NVL(MAX(rn), 0) AS cnt, NVL(MAX(sm), 0) AS cost FROM juniors, max_senior WHERE sm <= 70000 - max_senior.cost
),
selected_juniors AS (
  SELECT employee_id FROM juniors, max_junior WHERE rn <= max_junior.cnt
)
SELECT employee_id FROM selected_seniors
UNION ALL
SELECT employee_id FROM selected_juniors;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

WITH seniors AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY salary) rn, SUM(salary) OVER (ORDER BY salary) sm
  FROM Candidates WHERE experience = 'Senior'
),
max_senior AS (
  SELECT COALESCE(MAX(rn), 0) AS cnt, COALESCE(MAX(sm), 0) AS cost FROM seniors WHERE sm <= 70000
),
selected_seniors AS (
  SELECT employee_id FROM seniors, max_senior WHERE rn <= max_senior.cnt
),
juniors AS (
  SELECT *, ROW_NUMBER() OVER (ORDER BY salary) rn, SUM(salary) OVER (ORDER BY salary) sm
  FROM Candidates WHERE experience = 'Junior'
),
max_junior AS (
  SELECT COALESCE(MAX(rn), 0) AS cnt, COALESCE(MAX(sm), 0) AS cost FROM juniors, max_senior WHERE sm <= 70000 - max_senior.cost
),
selected_juniors AS (
  SELECT employee_id FROM juniors, max_junior WHERE rn <= max_junior.cnt
)
SELECT employee_id FROM selected_seniors
UNION ALL
SELECT employee_id FROM selected_juniors;

Complexity

  • ⏰ Time complexity: O(N log N) (for sorting)
  • 🧺 Space complexity: O(N)