2933. High-Access Employees
Problem Description
The goal is to identify employees who have accessed a system frequently within short periods of time. Assuming we have each employee's access records for a single day, we are to determine which of them have accessed the system three or more times within any one-hour period.
To clarify, the period must be less than or equal to 60 minutes, but cannot span across the start and end of the day. For example, times such as "0815" and "0915" are not considered within the same hour, and neither are times like "0005" and "2350" since they are at the start and end of the day, respectively.
We are presented with a 2D array access_times
, where each entry contains an employee's name and their access time. The access time is given in 24-hour format without a colon, so "0800" represents 8:00 AM and "2250" represents 10:50 PM. We need to return a list of names of employees who are considered high-access, without any specific order of the names.
Intuition
To solve this problem, we use a hashmap (or in Python, a defaultdict
) to group all access times by the employeeβs name. The keys in this hashmap are the names of the employees, and the corresponding values are lists containing all their access times converted to minutes since midnight. This conversion simplifies the comparison of times by translating all access times into a single numerical format.
Once we've grouped all the access times for each employee, the next step is to sort these times in ascending order to easily check for any instances where three or more accesses occurred within a 60-minute window.
After sorting, we iterate over the access times for each employee. If at any point we find three consecutive times t1
, t2
, and t3
such that t3 - t1
is less than 60 minutes, it implies that those accesses happened within the same one-hour period, and we can conclude that the employee is a 'high-access' employee.
The intuition behind this approach is that if an employee has accessed the system three or more times in any one-hour period, sorting the times makes it straightforward to check for a 60-minute window containing at least three timestamps.
In summary, the solution involves:
- Grouping and converting all access times to a numerical format.
- Sorting the access times to identify potential one-hour periods.
- Checking for the presence of three accesses within these periods for each employee.
- Collecting the names of employees who meet the 'high-access' criteria.
Learn more about Sorting patterns.
Solution Approach
The solution uses a hash table (specifically a defaultdict
from Python's collections
module), which is an ideal data structure for grouping elements based on a key. In this implementation, the key for the hash table is the employee's name, and the value is a list of their access times in minutes.
The first step is iterating over the access_times
array to build the hash table with the employees and their respective access times. Within this loop, we convert the access time to minutes by taking the first two characters of the access time string as hours, converting them to an integer and multiplying by 60 to obtain the equivalent minutes, and adding the minutes, which are obtained by converting the last two characters of the access time string to an integer.
Now, the key aspect of this solution is to sort the times to make the checks for the one-hour period straightforward. Sorting ensures that we can look at each consecutive triplet of access times to check if they are within 60 minutes of each other.
After sorting each employee's access times, we loop through the sorted times and use a sliding window approach to check for consecutive triplets. The sliding window comprises three consecutive elements at a time because we are interested in periods where there are at least three accesses.
We check if the difference between the first and the third access time in the sliding window is less than 60 minutes. If this condition is true for any triplet, the employee's name is added to the ans
list which records the names of high-access employees.
The final step is to return the list ans
, containing all the high-access employee names identified by the algorithm.
Here's the approach translated into pseudo code:
- Initialize hash table
d
for grouping access times by employee names. - For each name and time in
access_times
:- Calculate total minutes from
00:00
and group it under the equivalent employee name ind
.
- Calculate total minutes from
- Initialize
ans
as an empty list to store results. - For each employee name and its access times in
d
:- Sort the list of times.
- For
i
from 2 to the length of the list of times:- If the time at index
i
minus time at indexi - 2
is less than 60:- Add employee name to
ans
.
- Add employee name to
- If the time at index
- Return the
ans
list.
By combining the hash table for organization, the sorting for temporal ordering, and a simple iteration with conditional checks, we elegantly solve the problem without the need for complex algorithms. This approach is efficient as it takes advantage of the easily sortable nature of times and the straightforward conditions set by the problem to identify high-access employees.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example access records data:
1Alice 0800 2Bob 0830 3Alice 0835 4Carol 0855 5Alice 0900 6Bob 0840 7Carol 0905 8Bob 0920 9Carol 0950 10Alice 0915
Following the solution approach, we'll process the records:
-
Initialize hash table
d
for grouping access times by employee names.d
would look like this after processing:1{ 2 "Alice": [], 3 "Bob": [], 4 "Carol": [] 5}
-
For each name and time in
access_times
: We convert access times for Alice, Bob, and Carol to minutes: Alice's times: [480, 515, 540, 555] (8:00 AM, 8:35 AM, 9:00 AM, 9:15 AM) Bob's times: [510, 540, 560] (8:30 AM, 9:00 AM, 9:20 AM) Carol's times: [535, 545, 590] (8:55 AM, 9:05 AM, 9:50 AM)Now,
d
would look like this:1{ 2 "Alice": [480, 515, 540, 555], 3 "Bob": [510, 540, 560], 4 "Carol": [535, 545, 590] 5}
-
Initialize
ans
as an empty list to store results.ans = []
-
For each employee name and its access times in
d
:- Sort the list of times. (In our case, times are already sorted)
- Loop through each employee's times checking for a window where three accesses are within 60 minutes.
For Alice:
- We check at index 2 (540) - index 0 (480) = 60 minutes, but we need less than 60.
- Move to next window and check index 3 (555) - index 1 (515) = 40 minutes. It's within 60 minutes, so we identify Alice as a high-access employee and add her to
ans
.
For Bob:
- We check at index 2 (560) - index 0 (510) = 50 minutes. It's within 60 minutes, so we add Bob to
ans
.
For Carol:
- Since there are only three records and the difference between the last and first is greater than 60 minutes (590 - 535 = 55 minutes), Carol is not added.
So the ans
list after the checks:
1["Alice", "Bob"]
- Return the
ans
list. The returned result is the list of employees who accessed the system three or more times in any one-hour period. For our example, the final output is:1["Alice", "Bob"]
Through this example, we've illustrated how the solution approach effectively identifies 'high-access' employees by leveraging a hash table, sorting, and a sliding window check.
Solution Implementation
1from collections import defaultdict # required for defaultdict usage
2
3class Solution:
4 def findHighAccessEmployees(self, access_times):
5 """
6 Identifies employees with high access frequency within any one-hour window.
7
8 :param access_times: List of lists containing employee names and corresponding access times
9 :type access_times: List[List[str]]
10 :return: List of employee names with high access frequency
11 """
12 access_dict = defaultdict(list) # Create a default dictionary to hold access times for each employee
13
14 # Convert access times to minutes and store in the dictionary
15 for name, time_str in access_times:
16 # Convert timestamp 'HHMM' to total minutes since 00:00
17 total_minutes = int(time_str[:2]) * 60 + int(time_str[2:])
18 access_dict[name].append(total_minutes)
19
20 high_access_employees = [] # List to hold the names of high access frequency employees
21
22 # Iterate over each employee's access times to detect high frequency
23 for name, timestamps in access_dict.items():
24 timestamps.sort() # Sort timestamps for each employee
25 # Check for any three consecutive timestamps within a 60-minute window
26 for i in range(2, len(timestamps)):
27 if timestamps[i] - timestamps[i - 2] < 60:
28 high_access_employees.append(name)
29 break # We already know this employee has high access, no need to check further
30
31 return high_access_employees # Return the list of names
32
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.HashMap;
4import java.util.List;
5import java.util.Map;
6
7class Solution {
8
9 // Method to find employees who have accessed a system frequently in a short time frame
10 public List<String> findHighAccessEmployees(List<List<String>> accessTimes) {
11 // Create a map to track the access times for each employee
12 Map<String, List<Integer>> employeeAccessMap = new HashMap<>();
13
14 // Loop through all provided access times
15 for (List<String> entry : accessTimes) {
16 String employeeName = entry.get(0);
17 String time = entry.get(1);
18
19 // Convert access time from String to minutes as Integer
20 int timeInMinutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(2));
21
22 // Add the access time to the list for the corresponding employee in the map
23 // If no list exists yet for the employee, create it
24 employeeAccessMap.computeIfAbsent(employeeName, k -> new ArrayList<>()).add(timeInMinutes);
25 }
26
27 // List to hold the names of employees with frequent accesses
28 List<String> frequentAccessEmployees = new ArrayList<>();
29
30 // Iterate through each employee's entry in the map
31 for (Map.Entry<String, List<Integer>> entry : employeeAccessMap.entrySet()) {
32 String employeeName = entry.getKey();
33 List<Integer> accessTimesList = entry.getValue();
34
35 // Sort the access times in ascending order to check for three consecutive accesses within a 60-minute window
36 Collections.sort(accessTimesList);
37
38 // Check for three or more consecutive accesses within a 60-minute window
39 for (int i = 2; i < accessTimesList.size(); ++i) {
40 if (accessTimesList.get(i) - accessTimesList.get(i - 2) < 60) {
41 // If such a pattern is found, add the employee's name to the result list
42 frequentAccessEmployees.add(employeeName);
43 break; // No need to check the rest of the times for this employee
44 }
45 }
46 }
47 // Return the list of employees with frequent access patterns
48 return frequentAccessEmployees;
49 }
50}
51
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 // Method to find employees with high access frequency within any 1-hour period
10 vector<string> findHighAccessEmployees(vector<vector<string>>& accessTimes) {
11 // Map to store access times for each employee
12 unordered_map<string, vector<int>> employeeAccessMap;
13
14 // Iterate over each access record
15 for (const auto& record : accessTimes) {
16 const string& employeeName = record[0];
17 const string& timeStr = record[1];
18
19 // Convert HHMM format string to total minutes
20 int timeMinutes = stoi(timeStr.substr(0, 2)) * 60 + stoi(timeStr.substr(3, 2));
21
22 // Add this time to the list of times for this employee
23 employeeAccessMap[employeeName].emplace_back(timeMinutes);
24 }
25
26 // Vector to store the names of high access frequency employees
27 vector<string> highFrequencyEmployees;
28
29 // Iterate over each employee's access records
30 for (auto& [employeeName, times] : employeeAccessMap) {
31 // Sort the access times in ascending order
32 sort(times.begin(), times.end());
33
34 // Look for three consecutive times within a 60 minute period
35 for (int i = 2; i < times.size(); ++i) {
36 if (times[i] - times[i - 2] < 60) { // Found 3 accesses within a 60-min window
37 highFrequencyEmployees.emplace_back(employeeName);
38 break; // No need to check further for this employee
39 }
40 }
41 }
42
43 // Return the list of employees with high access frequency
44 return highFrequencyEmployees;
45 }
46};
47
1function findHighAccessEmployees(accessTimes: string[][]): string[] {
2 // Create a map to hold employee names as keys and an array of
3 // access times in minutes as values.
4 const employeeAccessMap: Map<string, number[]> = new Map();
5
6 // Loop over each access record in the input array.
7 for (const [name, timeString] of accessTimes) {
8 // Convert hour part of the time string to minutes.
9 const hours = parseInt(timeString.slice(0, 2), 10);
10 // Convert minute part of the time string to integer.
11 const minutes = parseInt(timeString.slice(2), 10);
12 // Calculate the total minutes since midnight.
13 const totalTime = hours * 60 + minutes;
14
15 // If the employee name does not exist in the map, add it.
16 if (!employeeAccessMap.has(name)) {
17 employeeAccessMap.set(name, []);
18 }
19
20 // Append the access time to the employee's list of access times.
21 employeeAccessMap.get(name)!.push(totalTime);
22 }
23
24 // Initialize an array to hold the names of employees with high access frequency.
25 const highAccessEmployees: string[] = [];
26
27 // Iterate over each employee and their corresponding access times.
28 for (const [name, accessTimes] of employeeAccessMap) {
29 // Sort the access times in ascending order.
30 accessTimes.sort((a, b) => a - b);
31
32 // Go through the sorted access times to find employees who accessed 3 times within a 60-minute window.
33 for (let i = 2; i < accessTimes.length; ++i) {
34 // Check if there is a 60-minute window between the current and two prior access times.
35 if (accessTimes[i] - accessTimes[i - 2] < 60) {
36 // Add employee name to the result list and break out of the loop as we have found a valid access pattern.
37 highAccessEmployees.push(name);
38 break;
39 }
40 }
41 }
42
43 // Return the names of employees with high access frequency.
44 return highAccessEmployees;
45}
46
Time and Space Complexity
Time Complexity
The time complexity of the algorithm is composed of several parts:
-
Creating the defaultdict for employees' access times β This takes
O(n)
time wheren
is the number of access records, as we loop through theaccess_times
list once. -
Casting times to minutes and appending to the list in the dictionary β Each conversion takes constant time, so with
n
access records this part is alsoO(n)
. -
Sorting the timestamps for each employee β Sorting is commonly
O(k \times log(k))
wherek
is the number of timestamps for an employee. As we need to perform this for all employees, the total time isO(m \times k \times log(k))
wherem
is the number of unique employees. In the worst case, where all timestamps belong to the same employee, this is equivalent toO(n \log n)
. -
Checking within each sorted list for the violation condition β We iterate over sorted timestamps for each employee which could be at worst
O(n)
if all timestamps are for a single employee. However, since the comparison is a constant time operation, it does not change the sorting time complexity we calculated earlier.
Hence, we combine the time complexities: O(n) + O(n \log n)
which simplifies to O(n \log n)
because O(n \log n)
is the dominant term.
Space Complexity
The space complexity can be analyzed as follows:
-
The dictionary storing employee names and their access times β If
m
is the number of unique employees andk
is the average number of access timestamps per employee, the space complexity would beO(m \times k)
. However, asm \times k
is essentiallyn
, we getO(n)
space complexity. -
The sorted list of timestamps β This doesn't take additional space beyond what is used in the dictionary as it sorts the timestamps in place.
-
The answer list β In the worst case, where every employee name is added to the answer list, the space complexity would again be
O(m)
, which is a subset ofO(n)
.
Combining all parts, the space complexity of this algorithm is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question?Β Ask the Monster AssistantΒ anything you don't understand.
Still not clear? Β SubmitΒ the part you don't understand to our editors. Or join ourΒ Discord and ask the community.