The Number of Seniors and Juniors to Join the Company

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) type of values ('Senior', 'Junior').
Each row of this table indicates the id of a candidate, their monthly salary, and their experience.

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

Hiring the largest number of seniors.
After hiring the maximum number of seniors, use the remaining budget to hire the largest number of juniors.

Write a solution to find the number 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


Input: 
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 10000  |
| 9           | Junior     | 10000  |
| 2           | Senior     | 20000  |
| 11          | Senior     | 20000  |
| 13          | Senior     | 50000  |
| 4           | Junior     | 40000  |
+-------------+------------+--------+
Output: 
+------------+---------------------+
| experience | accepted_candidates |
+------------+---------------------+
| Senior     | 2                   |
| Junior     | 2                   |
+------------+---------------------+
Explanation: 
We can hire 2 seniors with IDs (2, 11). Since the budget is $70000 and the sum of their salaries is $40000, we still have $30000 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 $30000 and the sum of their salaries is $20000, we still have $10000 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


Input: 
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 10000  |
| 9           | Junior     | 10000  |
| 2           | Senior     | 80000  |
| 11          | Senior     | 80000  |
| 13          | Senior     | 80000  |
| 4           | Junior     | 40000  |
+-------------+------------+--------+
Output: 
+------------+---------------------+
| experience | accepted_candidates |
+------------+---------------------+
| Senior     | 0                   |
| Junior     | 3                   |
+------------+---------------------+
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 Selection with Window Functions

We sort seniors and juniors by salary ascending, select as many seniors as possible within the budget, then use the remaining budget for juniors. This is best done with window functions and variables in SQL.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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
),
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 FROM juniors, max_senior WHERE sm <= 70000 - max_senior.cost
)
SELECT 'Senior' AS experience, cnt AS accepted_candidates FROM max_senior
UNION ALL
SELECT 'Junior', cnt FROM max_junior;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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
),
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 FROM juniors, max_senior WHERE sm <= 70000 - max_senior.cost
)
SELECT 'Senior' AS experience, cnt AS accepted_candidates FROM max_senior
UNION ALL
SELECT 'Junior', cnt FROM max_junior;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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
),
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 FROM juniors, max_senior WHERE sm <= 70000 - max_senior.cost
)
SELECT 'Senior' AS experience, cnt AS accepted_candidates FROM max_senior
UNION ALL
SELECT 'Junior', cnt FROM max_junior;

Complexity

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

Problem#

Examples#

Solution#

Method 1 - Greedy Selection with Window Functions#

Code#

Complexity#