Alert Using Same Key-Card Three or More Times in a One Hour Period

Medium

Wayfair

2 views

Topics:

ArraysStringsTwo PointersSliding Windows

LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person's name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format "HH:MM", such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" - "11:00" is considered to be within a one-hour period, while "22:51" - "23:52" is not considered to be within a one-hour period.

Example 1:

Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").

Example 2:

Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").

Constraints:

1 <= keyName.length, keyTime.length <= 10⁵
keyName.length == keyTime.length
keyTime[i] is in the format "HH:MM".
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.

Try coding it in LeetCode

Alert Using Same Key-Card Three or More Times in a One Hour Period

Medium

Wayfair

2 views

Topics:

ArraysStringsTwo PointersSliding Windows

LeetCode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker's name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person's name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format "HH:MM", such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" - "11:00" is considered to be within a one-hour period, while "22:51" - "23:52" is not considered to be within a one-hour period.

Example 1:

Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").

Example 2:

Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").

Constraints:

1 <= keyName.length, keyTime.length <= 10⁵
keyName.length == keyTime.length
keyTime[i] is in the format "HH:MM".
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the `keyName` and `keyTime` lists guaranteed to be the same length?
Can the input lists be empty or contain null values?
If an employee triggers the alert condition multiple times within the input, should their name appear multiple times in the output, or only once?
If multiple employees trigger the alert, in what order should their names be sorted in the returned list (lexicographical, order of appearance, etc.)?
How should the times in `keyTime` be handled if they are not in chronological order for a specific employee?

Brute Force Solution

Approach

The brute force method for this problem is like checking every possible combination of key-card uses to see if anyone triggered an alert. We will systematically explore all the options to find those who used their card multiple times within an hour. It's like manually going through security logs to find suspicious patterns.

Here's how the algorithm would work step-by-step:

First, we will look at each employee individually.
For each employee, we will consider every possible group of three or more times they used their key-card.
For each of these groups, we will check if all the key-card uses occurred within a one-hour period.
If we find a group of three or more key-card uses within one hour, we mark that employee as someone who triggered an alert.
After checking all possible groups for all employees, we will have a list of all employees who triggered an alert.
That's our answer!

Code Implementation

def find_alert_employees(key_card_records):
    alert_employees = []

    # Group key card records by employee.
    employee_records = {}
    for employee_name, time in key_card_records:
        if employee_name not in employee_records:
            employee_records[employee_name] = []
        employee_records[employee_name].append(time)

    for employee_name, times in employee_records.items():
        times.sort()
        employee_triggered_alert = False

        # Iterate through all possible groups of three or more times.
        for i in range(len(times) - 2):
            for j in range(i + 2, len(times)): 
                # Check if all key-card uses occurred within a one-hour period.
                if times[j] - times[i] <= 60:

                    # Flag if employee triggered alert.
                    employee_triggered_alert = True
                    break

            if employee_triggered_alert:
                break

        if employee_triggered_alert:
            alert_employees.append(employee_name)

    return sorted(alert_employees)

def alert_using_same_key_card(
        key_card_names,
        key_card_times
):
    key_card_records = list(zip(key_card_names, key_card_times))
    return find_alert_employees(key_card_records)

Big(O) Analysis

Time Complexity

O(n^3) – Let n be the total number of key-card uses across all employees. First, we group key-card uses by employee. In the worst case, one employee could have used their card n times. For that single employee, we iterate through all possible groups of three or more key-card uses. In the worst case, this involves combinations of size 3, 4, 5,... up to n, which contributes to a runtime of O(n^3) at least. Each of these combinations also require checking the one hour period constraint.

Space Complexity

O(1) – The brute force approach described primarily iterates through the input data without creating significant auxiliary data structures. While the algorithm checks combinations of key-card uses, it doesn't explicitly store all combinations in memory. It checks them one by one. Therefore, the additional space used is limited to a few variables for indexing and comparison, which remains constant regardless of the input size N (where N represents the total number of key-card uses).

Optimal Solution

Approach

The problem requires us to identify employees who use their key-cards excessively within a one-hour window. To do this efficiently, we need to organize the data and then focus on analyzing each employee's access times individually to find potential violations.

Here's how the algorithm would work step-by-step:

First, organize the data so that all the access times for each employee are grouped together.
For each employee, sort their access times from earliest to latest.
Then, go through each employee's sorted access times and check for any three or more entries that occur within a one-hour window.
To do this, consider a sliding window of one hour. If at any point, the number of access times within that window is three or more, that employee should be added to a list of those who triggered the alert.
Finally, return the list of employees who triggered the alert. Note that if an employee has multiple sets of accesses that meet the three-times-in-an-hour criteria, the problem asks that they only appear in the alert once.

Code Implementation

def alert_names(key_name, key_time):
    employee_to_times = {}
    for i in range(len(key_name)): 
        employee = key_name[i]
        time = int(key_time[i])
        if employee not in employee_to_times:
            employee_to_times[employee] = []
        employee_to_times[employee].append(time)

    alerted_employees = []

    # Iterate through each employee's access times.
    for employee, times in employee_to_times.items():
        times.sort()
        for i in range(len(times) - 2):
            # Check if at least 3 accesses happen within an hour.
            if times[i + 2] - times[i] <= 60:

                # Add to alert list, only if not already there.
                if employee not in alerted_employees:
                    alerted_employees.append(employee)

    # Sort the alerted names alphabetically.
    alerted_employees.sort()
    return alerted_employees

Big(O) Analysis

Time Complexity

O(n log n) – The first step involves grouping the key-card accesses by employee, which can be done in O(n) time, where n is the total number of key-card entries. The dominant cost arises when sorting each employee's access times. In the worst-case scenario, we could have a single employee with all 'n' access times, leading to a sorting operation that takes O(n log n) time. Subsequently, iterating through the sorted access times for each employee and applying the sliding window takes O(n) time in the worst case (for a single employee). Thus, the overall time complexity is dominated by the sorting step, giving us O(n log n).

Space Complexity

O(N) – The primary space complexity comes from organizing the key-card data into a hash map (or dictionary) where each employee's name is a key and the value is a list of their access times. In the worst case, each employee has a different name, and all access times are unique, requiring storage proportional to the total number of key-card entries. Therefore, the space used by this hash map and the lists of access times grows linearly with N, where N is the total number of key-card entries. Sorting the access times for each employee is done in place and does not add to space complexity.

Edge Cases

Case	How to Handle
keyName or keyTime is null or empty	Return an empty list if either input is null or empty, as there are no employees or times to process.
keyName and keyTime have different lengths	Throw an IllegalArgumentException or return an empty list, because the input is invalid.
Input with only one or two entries for a single employee	No employee can trigger the alert condition; so return an empty list if no employee has at least three entries.
Large input size, potentially exceeding memory limits if not handled efficiently.	Use a hash map and sort only the times for each employee, avoiding sorting the entire input at once, for better space complexity.
All access times for an employee are identical	The algorithm should correctly identify the employee as an alert case if there are three or more identical times within the one-hour window.
Access times are not in chronological order within each employee's access records	Sort the access times for each employee to correctly identify accesses within a one-hour period.
Invalid time format (e.g., HH > 23, MM > 59, or non-numeric characters).	Validate the time format and throw an exception or skip the entry if invalid.
Multiple alert employees exist.	The algorithm should correctly identify and return a sorted list of all alert employees.