Second Highest January Salary

Read this first - this is a programming question, not a SQL question. The data is described in database terms below because that is how the original assessment posed it, but no database is involved. The tables are handed to your program on standard input as pipe-delimited text (see Input Format), and you print the answer on standard output. Solve it in Python, C++ or Java by completing the solve function in the starter code. A SQL query submitted here will not run.

Description

A company keeps its payroll in five tables: dept, emp, designation, compensation and emp_dept. The employer wants to know the second-highest salary paid to an employee in the month of January 2021, together with the people who received it and the departments they work in today.

The Tables

The column types below describe the shape of each field; they are documentation only, and the values reach you as text on stdin.

emp(emp_no INT, dob DATE, first_name VARCHAR(14), last_name VARCHAR(16), gender VARCHAR(8), joining_date DATE)
dept(dept_no CHAR(4), dept_name VARCHAR(40))
emp_dept(emp_no INT, dept_no CHAR(4), from_date DATE, to_date DATE) - to_date is NULL for an employee's current department
compensation(emp_no INT, credited_date DATE, amount INT)
designation(emp_no INT, designation VARCHAR(50), from_date DATE, to_date DATE)

What to Return

Consider only compensation rows whose credited_date falls in January 2021, that is from 2021-01-01 to 2021-01-31 inclusive. Call these the January rows.
Collect the distinct amount values of the January rows and take the second-highest of them. This ranking is done over all January rows, before any join - a January row still contributes its amount to the ranking even if the employee cannot later be joined to a department.
If fewer than two distinct January amounts exist, the result is empty.
Otherwise report every January row whose amount equals that second-highest value. Two January rows with the same amount produce two output rows, even when they belong to the same employee.
Each reported row is joined to the employee's current department: the emp_dept row for that employee with to_date equal to NULL, and then to the matching dept row. A row is dropped from the result if the employee has no emp_dept row with to_date NULL, if the referenced dept_no does not appear in dept, or if the emp_no does not appear in emp.
Order the surviving rows by emp_no ascending, compared as a number.

Input Format

The four tables that matter are supplied on standard input as pipe-delimited plain text. Dates are given in ISO YYYY-MM-DD form.

The first line contains four integers E D ED C - the number of emp, dept, emp_dept and compensation rows that follow, in that order.

Then come E lines, one per employee:

<emp_no>|<first_name>|<last_name>|<gender>

Then D lines, one per department:

<dept_no>|<dept_name>

Then ED lines, one per employee/department assignment. The third field is either an ISO date or the literal word NULL:

<emp_no>|<dept_no>|<to_date or NULL>

Then C lines, one per compensation record:

<emp_no>|<credited_date>|<amount>

The designation table and the columns dob, joining_date and from_date are part of the schema but are not supplied and are not needed.

Output Format

Print one line per result row, comma-separated, in this column order:

emp_no,first_name,last_name,gender,dept_no,dept_name,amount

Print nothing at all when the result is empty.

Constraints

1 <= E <= 1500, 1 <= D <= 150, 0 <= ED <= 2000, 0 <= C <= 4000
The whole input is at most 200000 bytes.
1 <= emp_no <= 9999999, written without leading zeros; emp_no is unique within emp.
dept_no is 1 to 4 characters of letters and digits and is unique within dept.
first_name has at most 14 characters, last_name at most 16, gender at most 8, dept_name at most 40. None of these fields contains a comma or a vertical bar, and none is empty.
0 <= amount <= 2000000000.
Every credited_date and every non-NULL to_date is a valid ISO date.
An employee has at most one emp_dept row with to_date equal to NULL. An employee may have none, and may additionally have any number of closed rows.
An emp_dept or compensation row may reference an emp_no that is absent from emp, and an emp_dept row may reference a dept_no that is absent from dept.
The result contains at most 150 rows.

Examples

Example 1

4 3 4 12
1000|Amisha|Chopra|F
1001|Aditya|Parmar|M
1002|Manish|Rajput|M
1003|Suresh|Patil|M
1|Information Technology
2|Finance
3|Human Resource
1000|1|NULL
1001|1|NULL
1002|2|NULL
1003|1|NULL
1000|2021-01-01|20000
1000|2021-02-01|50000
1000|2021-03-01|40000
1001|2021-01-01|30000
1001|2021-02-01|20000
1001|2021-03-01|40000
1002|2021-01-01|30000
1002|2021-02-01|80000
1002|2021-03-01|20000
1003|2021-01-01|70000
1003|2021-02-01|60000
1003|2021-03-01|21000

1001,Aditya,Parmar,M,1,Information Technology,30000
1002,Manish,Rajput,M,2,Finance,30000

The amounts credited in January 2021 are 20000 (emp 1000), 30000 (emp 1001), 30000 (emp 1002) and 70000 (emp 1003). The distinct values are 20000, 30000 and 70000, so the second-highest is 30000. Employees 1001 and 1002 both received it, and they are reported with their current departments, ordered by emp_no.

Example 2

2 1 2 3
1|A|B|M
2|C|D|F
1|Finance
1|1|2020-05-05
2|1|NULL
1|2021-01-05|900
2|2021-01-05|500
2|2021-01-06|100

2,C,D,F,1,Finance,500

The January amounts are 900, 500 and 100, so the second-highest distinct value is 500. Employee 1's emp_dept row is closed (to_date is 2020-05-05), so employee 1 has no current department - yet the 900 still counts when the distinct amounts are ranked. Only employee 2's 500 row survives the join.

Example 3

2 1 2 3
1|A|B|M
2|C|D|F
1|Finance
1|1|NULL
2|1|NULL
1|2021-01-02|700
2|2021-01-03|400
2|2021-01-20|400

2,C,D,F,1,Finance,400
2,C,D,F,1,Finance,400

The distinct January amounts are 700 and 400, so the target is 400. Employee 2 has two January rows at 400, on the 3rd and on the 20th, so the employee is reported twice.

Example 4

2 1 2 2
1|A|B|M
2|C|D|F
1|Finance
1|1|NULL
2|1|NULL
1|2021-01-01|500
2|2021-01-02|500

The expected output is completely empty - zero bytes, not a blank line:

Only one distinct January amount exists, so there is no second-highest value and nothing is printed.

Example 5

1 1 1 4
7|Ira|Sen|F
HR1|Human Resource
7|HR1|NULL
7|2021-01-31|900
7|2021-01-05|1200
7|2020-12-31|5000
99|2021-01-31|900

7,Ira,Sen,F,HR1,Human Resource,900

A single employee. The January amounts are 900 (emp 7, on the 31st - the last day of January is inside the window), 1200 (emp 7) and 900 (emp 99), so the distinct values are 900 and 1200 and the target is 900. The 5000 row is dated 2020-12-31 and is outside January, so it never enters the ranking. Two January rows carry the target, but 99 does not appear in emp at all, so that row is dropped by the join and only employee 7's line is printed.