Problem · Array
Query Type Frequency Window
Learn this problem● Medium
IBMOA
See IBM hiring insightsIBMOAProblem statement
You are given n query logs, where each log entry includes:
timestamps[i]: the time of the query in seconds (sorted in non-decreasing order)queryTypes[i]: the query type recorded at that time
A query type should be included in the result if:
- There exists at least one 600-second window in which that query type appears at least
thresholdtimes.
Return:
- All query types that meet this condition, sorted in increasing (lexicographical) order
- An empty array if none qualify
Function
findFrequentQueryTypes(timestamps: int[], queryTypes: String[], threshold: int) → String[]Examples
Example 1
timestamps = [100, 150, 200, 250, 700]queryTypes = ["Q1", "Q1", "Q1", "Q2", "Q1"]threshold = 2return = ["Q1"]The table below shows the time window during which the query type appeared at least threshold times, along with its corresponding frequency count:
Query Types Frequency Table
| Time Window | Query Type | Frequency Count |
|---|---|---|
[101, 700] | Q1 | 3 |
The query type "Q1" occurs 3 times between timestamps 101 and 700, which is within a 600-second window. Since threshold = 2, "Q1" exceeds the required frequency. Hence, the answer is ["Q1"].
Constraints
1 <= n <= 2 * 10^51 <= threshold <= 2 * 10^51 <= length of queryTypes[i] <= 10