This seemed like a fairly easy question in today's Daily Coding Challenge, that involved determining employee bonuses based on employees seated next to them
MegaCorp wants to give bonuses to its employees based on how many lines of codes they have written. They would like to give the smallest positive amount to each worker consistent with the constraint that if a developer has written more lines of code than their neighbor, they should receive more money.
Given an array representing a line of seats of employees at MegaCorp, determine how much each one should get paid.
For example, given
[10, 40, 200, 1000, 60, 30], you should return[1, 2, 3, 4, 2, 1].
Understanding the problem
Everyone gets a bonus. Employees that wrote code are getting at least 1.
Employee bonuses may increase by 1 if they have produced more code compared to either employee seated next to them. The company is also trying to minimize bonuses. Bonuses may only increase relative to the employees seated next to them and are in no way proportional to the number of lines of code.
In the example below, employee C's bonus is affected if the person seated next to them switched seats.
First approach
The first approach I took was to use a sliding window of 3 employees at a time. With the example provided in the problem, it is easy to do a single pass, and recalibrate the bonuses of each set of employees within the window. Since bonuses are neighbor dependent this is straight forward.
However, expanding the example to include more employees makes it evident that we would need to do some backtracking to adjust the bonuses of prior employees in the list
The runtime with this solution can get exponential if all the employees have lines of code sorted in descending order. We do not need any extra memory in this algorithm.
Use a Min Heap
To improve our solution, we can use a min heap or a PriorityQueue.
With one pass of our list we can build the PriorityQueue in nlogN runtime. The heap will contain all employees -
- sorted on the bonus metric - lines of code.
- and will also store the position of the employee
The next steps are
- Pick an employee from the heap. The heap will return the employee with the least lines of code
- Using the employee's position, we can now traverse the list in opposite directions
- Assign bonuses in increasing order starting from 1
We stop when
- There are no more employees or,
- We have reached an employee with peak LOC. This can be ascertained by keeping track of LOC in a prev variable.
We should also keep track of the employee we have assigned bonuses to either
- through a separate set,
- or via the solution array that is initially populated with -1
We repeat the process by picking the next employee from the heap until our heap is empty.
Recalibration
Since we terminate the nested traversal when we reach an employee with peak LOC, it is also possible to recalibrate the bonuses that may have been previously assigned, as seen in the following diagram
Runtimes And Memory
If we compare the "worst case" scenarios of both back tracking and the min heap, the solution with the min heap takes less time but uses more memory.
