We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

High-Access Employees

Difficulty: Medium

Problem Description

You are given a 2D 0-indexed array of strings, access_times, with size n. For each i where 0 <= i <= n - 1, access_times[i][0] represents the name of an employee, and access_times[i][1] represents the access time of that employee. An employee is said to be high-access if he has accessed the system three or more times within a one-hour period. Return a list that contains the names of high-access employees with any order you want.

Key Insights

  • Each access time is a four-digit number in 24-hour format.
  • An employee must have three or more access times within a one-hour window (not including the edges).
  • Sorting access times for each employee allows for efficient checking of the number of accesses within any one-hour period.
  • Use a dictionary to group access times by employee names.

Space and Time Complexity

Time Complexity: O(n log n) for sorting the access times, where n is the total number of access records. Each employee's access list is processed in linear time.

Space Complexity: O(n) for storing the access times of each employee.

Solution

To solve the problem, we will:

  1. Use a dictionary to group access times by employee names.
  2. Sort the access times for each employee.
  3. For each employee, iterate through the sorted times and count how many access times fall within any one-hour period.
  4. If an employee meets the high-access criteria (three or more accesses in an hour), add their name to the result list.

Code Solutions

def high_access_employees(access_times):
    from collections import defaultdict
    
    # Step 1: Group access times by employee
    employee_access = defaultdict(list)
    for name, time in access_times:
        employee_access[name].append(int(time))
    
    # Step 2: Check each employee for high-access status
    high_access_list = []
    for name, times in employee_access.items():
        # Step 3: Sort access times
        times.sort()
        count = 0
        
        # Step 4: Use a sliding window to count accesses within one hour
        for i in range(len(times)):
            count = 1  # Start counting the current access
            for j in range(i + 1, len(times)):
                if times[j] - times[i] < 100:  # less than an hour
                    count += 1
                else:
                    break  # No need to check further, as times are sorted
            if count >= 3:
                high_access_list.append(name)
                break  # No need to check further for this employee
            
    return high_access_list
← Back to All Questions