I did this OA on the HackerRank platform.
Two questions, 75 minutes.
Q2: You're given n employees' office hours as intervals [startTime[i], endTime[i]]. You need to build a team that includes at least one "core employee" whose working hours overlap with every other member's working hours. Find the maximum number of employees the team can include.
For example:
Input: startTime = [2, 5, 6, 8], endTime = [5, 6, 10, 9]
Output: 3
There's a time limit! An O(n^2) approach can't pass all the test cases.
Since the problem requires at least one "core employee" whose working hours overlap with every other team member's, that means all the employees on the team must share some common office-hours region — they all pass through a common point. Where do you find this point? At an interval endpoint.
So the problem reduces to: find the point that is covered by the most intervals.
Approach: sweep line.
Q3: Grace Hopper is famously recognized as the "First Lady of Software." She played a significant role in the creation of the first all-electrical digital computer, UNIVAC (Universal Automatic Computer).
Hopper's responsibilities included developing a process synchronization solution to ensure that never-ending processes experience a bounded wait, i.e., one that never completes. She designed an algorithm where one process cannot occupy consecutive time slots.
To evaluate the performance of this algorithm, Hopper needed to determine the number of ways to allocate n_processes in n_intervals different time intervals according to this rule. Since the number of ways can be very large, return the result modulo (10^9 + 7).
Approach:
Solution 1: DFS
Let n = the number of n_processes, m = the number of n_intervals.
DFS goes m levels deep.
At the first level there are n cases.
At the second level... up to the m-th level there are n - 1 cases each.
Since we just need the count, we can compute it directly with math: result = (n * (n - 1) ^ (m - 1)) % (10^9 + 7).
Solution 2: DP
Building on the DFS idea above, treat each interval as one level.
Every level has the same structure, and the rule between levels is the same too — meaning how many valid configurations exist at level i only depends on level i - 1.
You can set dp[i][j] = the number of valid ways where slot i picks process j, and solve from there.
Discussion
Loading comments…