FastPrep
Problem · Array

Query Type Frequency Window

● MediumIBMOA
See IBM hiring insights

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 threshold times.

Return:

  • All query types that meet this condition, sorted in increasing (lexicographical) order
  • An empty array if none qualify
Examples
01 · Example 1
timestamps = [100, 150, 200, 250, 700]
queryTypes = ["Q1", "Q1", "Q1", "Q2", "Q1"]
threshold = 2
return = ["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 WindowQuery TypeFrequency Count
[101, 700]Q13

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^5
  • 1 <= threshold <= 2 * 10^5
  • 1 <= length of queryTypes[i] <= 10
More IBM problems
drafts saved locally
public String[] findFrequentQueryTypes(int[] timestamps, String[] queryTypes, int threshold) {
  // write your code here
}
timestamps[100, 150, 200, 250, 700]
queryTypes["Q1", "Q1", "Q1", "Q2", "Q1"]
threshold2
expected["Q1"]
checking account