FastPrep
Problem · Hash Table

Count Repeated Request IDs

Learn this problem
● EasyMcKinsey & CompanyOA

Problem statement

Arrays requestIDs and timestamps are given, along with an integer timeWindow.

  • requestIDs[i] represents the ID of a request.
  • timestamps[i] represents the time, in seconds, when that request occurred.

A request ID is considered repeated within the window if:

  • it appears at least twice, and
  • there exist two occurrences whose time difference is less than or equal to timeWindow.

Your task is to count how many distinct request IDs satisfy this condition.

Return the count.

Function

countRepeatedRequestIds(requestIDs: String[], timestamps: int[], timeWindow: int) → int

Examples

Example 1

requestIDs = ["authreq001", "authreq002", "authreq001", "authreq002"]timestamps = [10, 25, 20, 15]timeWindow = 10return = 2

Summary of each unique request ID based on the time window condition:

  • "authreq001" appears at 10 and 20. Since 20 - 10 = 10 <= 10, it satisfies the condition.
  • "authreq002" appears at 15 and 25. Since 25 - 15 = 10 <= 10, it satisfies the condition.

Hence, the answer is 2.

Constraints

  • 1 <= n <= 2 * 10^5
  • 1 <= length of requestIDs[i] <= 2 * 10^5, and the sum of their lengths over all i does not exceed 2 * 10^5.
  • 1 <= timestamps[i], timeWindow <= 10^9

More McKinsey & Company problems

drafts saved locally
public int countRepeatedRequestIds(String[] requestIDs, int[] timestamps, int timeWindow) {
  // write your code here
}
requestIDs["authreq001", "authreq002", "authreq001", "authreq002"]
timestamps[10, 25, 20, 15]
timeWindow10
expected2
checking account