FastPrepFastPrep
Problem Brief

Find Idle Skills Query

NEW GRADOA
See Amazon online assessment and hiring insights

The Amazon Alexa development team needs to analyze request logs across numSkills different Alexa skills to understand their performance and user engagement.

The skills are indexed from 1 to numSkills, and the logs are provided as a 2D array requestLog of size m where requestLog[i] = [skill_ID, timeStamp] represents a request made at timeStamp to the skill with ID skill_ID.

You are given an integer numSkills, a 2D integer array requestLogs, an integer timeWindow (representing a lookback period), and an array of queryTimes containing q queries.

For each queryTime[i] determine the number of skills that did not receive a request in the time interval [queryTime[i] - timeWindow, queryTime[i]]. Return an array of length q containing the result of each of the query.

Note: If for some query in the numSkills received requestLog the given time interval for that query, then answer is 0.

Function Description

Complete the function findIdleSkillsQuery in the editor.

findIdleSkillsQuery has the following parameters:

  • 1. int numSkills: an integer denoting the number of skills
  • 2. int[][] requestLogs: 2D array denoting the request logs
  • 3. int[] queryTime: an integer array denoting the query times
  • 4. int timeWindow: an integer denoting the lookback period for queries

    • Returns

    int[]: an integer array denoting the answers to the queries

    🌷 A super special thanks to an old friend who kindly helped out! 🌷

    1Example 1

    Input
    numSkills = 3, requestLogs = [[1, 3], [2, 6], [1, 5]], queryTime = [10, 11], timeWindow = 5
    Output
    [1, 2]
    Explanation
    Example 1 illustration
    For queryTime[0] = 10, skills 1 and 2 had requests at timeStamps 5 and 6, respectively, which fall in the interval [5, 10]. Skill 3 did not receive any requests in the given interval. Thus, answer for this queryTime is 1. For queryTime[1] = 11, skill 2 requests at timeStamp6, respectively, which fall in the interval [6, 11]. Skill 1 and 3 did not receive any requests in the given interval. Thus, answer for this queryTime is 2. So, our answer turns out to be [1, 2].

    2Example 2

    Input
    numSkills = 6, requestLogs = [[3, 2], [4, 3], [2, 6], [6, 3]], queryTime = [3, 2, 6], timeWindow = 2
    Output
    [3, 5, 5]
    Explanation
    For queryTimes[0] = 3, in time interval [1, 3] skills [3, 4, 6] receives requests. For queryTime [1] = 2, in time interval [0, 2] skills [3] receives requests. For queryTime [2] = 6, in time interval [4, 6] skills [2] receives requests.

    3Example 3

    Input
    numSkills = 6, requestLogs = [[3, 2], [4, 3], [2, 6], [6, 3]], queryTime = [1, 2, 3, 4, 5, 6], timeWindow = 1
    Output
    [6, 5, 3, 4, 6, 5]
    Explanation
    ~o~

    Constraints

    Limits and guarantees your solution can rely on.

    • 1 ≤ numSkills ≤ 10^5
    • 1 ≤ m ≤ 10^5
    • 1 ≤ q ≤ 10^5
    • 1 ≤ requestLogs[i][0] ≤ n
    • 1 ≤ requestLogs[i][1] ≤ 10^5
    • 1 ≤ queryTime[i] ≤ 10^5
    • 1 ≤ timeWindow ≤ 10^5
    public int[] findIdleSkillsQuery(int numSkills, int[][] requestLogs, int[] queryTime, int timeWindow) {
  // write your code here
}
    Input

    numSkills

    3

    requestLogs

    [[1, 3], [2, 6], [1, 5]]

    queryTime

    [10, 11]

    timeWindow

    5

    Output

    [1, 2]

    Sign in to submit your solution.