High-Access Employees

To solve this problem, you need to identify employees with at least three system accesses within one-hour windows. First, sort each employee's access times, then check for any one-hour period where an employee exceeds the threshold of accesses.

Problem Statement

You are given a list of system access logs represented as a 2D array, where each entry contains an employee's name and the corresponding access time in a 24-hour format. An employee is considered a high-access employee if they have accessed the system three or more times within any one-hour period on the same day.

Your task is to return a list of employee names who are classified as high-access. If multiple employees qualify, return them in the order they first appeared in the input list. The access times are guaranteed to be within the same day.

Examples

Example 1

Input: access_times = [["a","0549"],["b","0457"],["a","0532"],["a","0621"],["b","0540"]]

Output: ["a"]

"a" has three access times in the one-hour period of [05:32, 06:31] which are 05:32, 05:49, and 06:21. But "b" does not have more than two access times at all. So the answer is ["a"].

Example 2

Input: access_times = [["d","0002"],["c","0808"],["c","0829"],["e","0215"],["d","1508"],["d","1444"],["d","1410"],["c","0809"]]

Output: ["c","d"]

"c" has three access times in the one-hour period of [08:08, 09:07] which are 08:08, 08:09, and 08:29. "d" has also three access times in the one-hour period of [14:10, 15:09] which are 14:10, 14:44, and 15:08. However, "e" has just one access time, so it can not be in the answer and the final answer is ["c","d"].

Example 3

Input: access_times = [["cd","1025"],["ab","1025"],["cd","1046"],["cd","1055"],["ab","1124"],["ab","1120"]]

Output: ["ab","cd"]

"ab" has three access times in the one-hour period of [10:25, 11:24] which are 10:25, 11:20, and 11:24. "cd" has also three access times in the one-hour period of [10:25, 11:24] which are 10:25, 10:46, and 10:55. So the answer is ["ab","cd"].

Constraints

• 1 <= access_times.length <= 100
• access_times[i].length == 2
• 1 <= access_times[i][0].length <= 10
• access_times[i][0] consists only of English small letters.
• access_times[i][1].length == 4
• access_times[i][1] is in 24-hour time format.
• access_times[i][1] consists only of '0' to '9'.

Solution Approach

Sort and Scan Access Times

The key to solving this problem efficiently is to first sort each employee's access times. Once sorted, you can scan through each employee’s list of access times and check for any period where three or more accesses fall within a one-hour window.

Use Hash Map for Tracking Accesses

By using a hash map to store each employee’s access times, you can easily track and retrieve access times for specific employees, allowing you to evaluate each employee's activity in a more efficient manner.

Sliding Window Approach

Once the access times are sorted, a sliding window technique can be applied to check whether three or more access times fall within any one-hour period for each employee.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity primarily depends on sorting the access times for each employee. If there are n access records and m employees, sorting each employee’s access times takes O(n log n) time. The sliding window process runs in O(n) time per employee, so the total complexity is O(m * n log n). The space complexity is O(n) for storing the access records and hash map for each employee.

What Interviewers Usually Probe

• Candidates who suggest sorting followed by a sliding window approach demonstrate good problem-solving skills.
• If the candidate suggests inefficient brute force solutions without focusing on sorting or efficient lookups, it indicates a lack of optimization awareness.
• A strong candidate will mention using hash tables or maps for faster access time lookups.

Common Pitfalls or Variants

Common pitfalls

• Failing to sort the access times for each employee, leading to incorrect results.
• Not recognizing that access times need to be evaluated within a one-hour window for each employee.
• Not efficiently managing the access logs using appropriate data structures, which could lead to excessive time complexity.

Follow-up variants

• Consider scenarios where access logs are already sorted or partially sorted.
• Challenge with larger datasets where optimizing sorting and lookup times becomes crucial.
• Handle cases where multiple employees have similar access times, requiring precise detection of overlaps.

FAQ

What is the primary approach to solving the High-Access Employees problem?

The primary approach involves sorting the access times for each employee and then applying a sliding window technique to check for three or more accesses within a one-hour period.

How can I efficiently track access times for each employee?

Using a hash map to store each employee's access times allows for quick lookups and more efficient scanning of access logs.

What is the time complexity of the High-Access Employees problem?

The time complexity is O(m * n log n), where n is the number of access records and m is the number of employees. This is due to sorting each employee's access times.

Can this problem be solved without sorting the access times?

Sorting is essential to ensure that the access times are properly aligned for the sliding window check. Without sorting, the problem cannot be solved efficiently.

What is the sliding window approach in this problem?

The sliding window approach checks whether three or more access times fall within any one-hour period by moving through the sorted list of times.