Alert Using Same Key-Card More than Two Times in a One Hour Period

Easy
0/40
Average time to solve is 20m
2 upvotes
Asked in companies
AdobeOracleExpedia Group

Problem statement

The office doors can only be open by using the ‘key-cards’ given to the workers. Whenever a worker uses their ‘key-card’ to unlock the door, the office’s security system saves his name and the time when he used it in ‘any order’. The security system programmed in such a way that, if any worker uses the ‘key-card’ strictly “more than two times in one hour”, then the system emits an ‘alert’.

You are given two string arrays ‘keyName’, and ‘keyTime’, denoting the ‘name’ and the ‘time’ of the worker when he used his ‘key-card’ in a “single day”. Your task is to find the list of “unique worker” names who received an ‘alert’.

Note:

1. The ‘keyName’ contains only the lower-case English alphabets.

2. The ‘keyTime’ is given in the 24-hour format “HH:MM”, such as “00:00”, “13:35”, and “23:59” are some of the valid times.

3. “08:05 - 09:05” is considered to be within a ‘one-hour’, whereas “12:05 - 13:06” is not considered to be within a ‘one-hour’ period.

4. The system saves the ‘name’ and the ‘time’ of the workers in ‘any order’.

5. Each pair of [‘keyName’, ‘keyTime’] is ‘unique’.

6. Print the output in ‘increasing’ order alphabetically.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains a single positive integer, ‘N’, denoting the total number of workers in the office.

The second line of each test case contains ‘N’ space-separated string, ‘keyName[i]’, representing the ith worker’s name.

The third line of each test case contains ‘N’ space-separated string, ‘keyTime[i]’, representing the ith worker’s time.
Output Format: 
For each test case, print a single line containing space-separated integers denoting elements of the list of the “unique worker” names sorted in “increasing order alphabetically”, as described in the problem statement.

The output for each test case will be printed in a separate line.
Note: 
1. You do not need to print anything. It has already been taken care of. Just implement the given function.

2. If the list is ‘empty’, then you have to return an “empty list”.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘keyName[i].length’ <= 10
“00:00” <= ‘keyTime[i]’ <= “23:59”
keyName.length == keyTime.length  == ‘N’

Where ‘T’ is the number of test cases, ‘N’ is the number of workers, ‘keyName[i]’  is the name of the ith worker,  and ‘keyTime[i]’ is the time of the ith worker.

Time Limit: 1 sec.
Sample Input 1:
1
5 
ninja ninja kevin ninja kevin
09:00 09:30 10:10 09:59 10:00
Sample Output 1:
ninja
Explanation for sample input 1:
“ninja” uses the ‘key-card’ more than two times in a one-hour period, i.e., at [“09:00”, “09:30”, “09:59”].
Sample Input 2:
1
3
ninja ninja ninja
14:00 14:02 16:00
Sample Output 2:
Explanation for sample input 2:
“ninja” did not use his ‘key-card’ more than two times in a one-hour. So, the output is the blank line.
Hint

Think of sorting based on keyName.

Approaches (1)
Sorting and Sliding Window
  • The idea here is to do the sorting on the basis of keyName, and then use the sliding window technique to solve the problem.
  • First, we create a 2-D array named accessData[N][2] to store the system’s data, where the 1st element of the ith row is the keyName[i], and the 2nd element of the ith row is the keyTime[i] converted “HH : MM” format into the minutes, where “00 : 00” considered as the 0 minutes.
  • Since the system’s data is in random order, we have to sort the array accessData in increasing order based on keyName, and if keyName is the same, then based on keyTime, which is in the minutes now.
  • So, the ‘one-hour’ period is nothing but the “60 min window”? Isn’t it?
  • Create an empty list named ans to store the ans.
  • Now, use the sliding window technique. We require the window of size 3. So, run a loop from i = 0 to i < ‘N - 2’, in each iteration do:
    • If accessData[i + 2][1] - accessData[i][1] <= 60, and accessData[i + 2][0] == accessData[i][0], then:
      • If ans is empty or ans doesn’t contain the current worker’s name, accessData[i][0], then insert it into the ans.
  • Finally, return the ans.
Time Complexity

O(N * logN), where N is the number of workers.
 

We are storing the system’s data based on the worker’s ‘name’ and ‘time’, which will take O(N * logN). Hence, the time complexity will be O(N * logN).

Space Complexity

O(N), where N is the number of workers.
 

As we are using an array to store the system’s data, that is the size of ‘N’. Hence, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Alert Using Same Key-Card More than Two Times in a One Hour Period
Full screen
Console