How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Point72.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Point72 during technical interviews.

Find kth missing integer and redundant operations

Quick Overview

This paired question evaluates array and algorithmic skills — specifically order-statistics and missing-number reasoning for the k-th missing positive, and time-window aggregation with frequency tracking for detecting redundant log events — within the coding & algorithms domain.

Company: Point72

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

You are given two independent coding tasks. ## Task 1: K-th missing number You are given an integer array `nums` (not necessarily sorted) containing **distinct** positive integers, and an integer `k`. Define the **missing numbers** as the positive integers that do **not** appear in `nums`. **Return the k-th smallest missing positive integer.** **Constraints (representative of an “optimal required” setting):** - `1 <= n <= 2e5` - `1 <= nums[i] <= 1e9` (distinct) - `1 <= k <= 1e9` **Example:** - `nums = [2, 3, 7, 11], k = 5` - Missing positives are `1, 4, 5, 6, 8, 9, 10, 12, ...` - Answer: `8` ## Task 2: Count redundant operations within a time window You are given two arrays of equal length `ops[]` and `times[]` describing a log of events, where: - `ops[i]` is a string operation name (e.g., `"login"`, `"refresh"`) - `times[i]` is the event time as an integer timestamp (seconds) You are also given an integer window size `W` (seconds). An event at index `i` is considered **redundant** if there exist **two earlier events** `j < k < i` such that: - `ops[j] == ops[k] == ops[i]` - `times[i] - times[j] <= W` (i.e., 3 occurrences of the same operation happen within a `W`-second window ending at `times[i]`) **Return the total number of redundant events in the log.** **Assumptions/notes:** - The input may not be sorted; you may sort by time if needed. - If multiple events share the same timestamp, treat earlier indices as earlier events. **Example:** - `ops = ["A","B","A","A","A"], times = [1,2,3,4,10], W = 5` - The event at time `4` is redundant because `A` occurred at times `1,3,4` within 5 seconds. - The event at time `10` is **not** redundant for window `W=5`. - Answer: `1`

Quick Answer: This paired question evaluates array and algorithmic skills — specifically order-statistics and missing-number reasoning for the k-th missing positive, and time-window aggregation with frequency tracking for detecting redundant log events — within the coding & algorithms domain.

Part 1: K-th Missing Positive Integer

You are given an array nums of distinct positive integers and an integer k. The array is not necessarily sorted. Consider all positive integers that do not appear in nums. Return the k-th smallest missing positive integer. Your solution should be efficient enough for large inputs, so avoid generating missing numbers one by one.

Constraints

1 <= len(nums) <= 2 * 10^5
1 <= nums[i] <= 10^9
All values in nums are distinct
1 <= k <= 10^9

Examples

Input: ([2, 3, 7, 11], 5)

Expected Output: 8

Explanation: After sorting, the missing positives are 1, 4, 5, 6, 8, 9, ... so the 5th missing value is 8.

Input: ([5], 3)

Expected Output: 3

Explanation: The missing positives begin as 1, 2, 3, 4, 6, ... so the 3rd missing value is 3.

Input: ([4, 1, 2, 10], 4)

Expected Output: 7

Explanation: Sorted nums = [1, 2, 4, 10]. Missing positives are 3, 5, 6, 7, 8, 9, ... so the 4th missing value is 7.

Input: ([1, 2, 3], 5)

Expected Output: 8

Explanation: No values are missing before 3, so the missing positives are 4, 5, 6, 7, 8, ... and the 5th one is 8.

Input: ([1000000000], 999999999)

Expected Output: 999999999

Explanation: All positive integers from 1 to 999999999 are missing, so the 999999999-th missing value is 999999999.

Solution

def solution(nums, k):
    if not nums:
        return k

    nums = sorted(nums)
    prev = 0

    for value in nums:
        gap = value - prev - 1
        if k <= gap:
            return prev + k
        k -= gap
        prev = value

    return prev + k

Time complexity: O(n log n). Space complexity: O(n).

Hints

Sort the numbers first so you can count how many positives are missing in each gap.
If there are gap = curr - prev - 1 missing values between two kept numbers, either the answer is inside that gap or you can skip the whole gap and reduce k.

Part 2: Count Redundant Operations Within a Time Window

You are given two arrays of equal length, ops and times, describing a log of events. ops[i] is the operation name and times[i] is its timestamp in seconds. An event is considered redundant if there exist two earlier events of the same operation such that all three occurrences lie within a window of W seconds ending at the current event. In other words, an event at position i is redundant if there are indices j < k < i with ops[j] == ops[k] == ops[i] and times[i] - times[j] <= W. The input may not be sorted by time. If multiple events have the same timestamp, the one with the smaller original index is considered earlier.

Constraints

1 <= len(ops) == len(times) <= 2 * 10^5
0 <= times[i] <= 10^9
0 <= W <= 10^9
ops[i] is a non-empty string

Examples

Input: (["A", "B", "A", "A", "A"], [1, 2, 3, 4, 10], 5)

Expected Output: 1

Explanation: The A at time 4 is redundant because A appears at times 1, 3, and 4 within 5 seconds. The A at time 10 is not.

Input: (["x", "x", "x", "x"], [5, 5, 5, 5], 0)

Expected Output: 2

Explanation: With the same timestamp and W = 0, the 3rd and 4th events each have two earlier matching events within the window.

Input: (["login", "refresh", "login", "login", "refresh", "login"], [10, 1, 4, 6, 5, 8], 5)

Expected Output: 2

Explanation: After sorting by time, login events occur at 4, 6, 8, and 10. The events at 8 and 10 are redundant.

Input: (["A", "A", "A"], [1, 7, 13], 5)

Expected Output: 0

Explanation: No three A events fit inside any 5-second window.

Input: (["B", "B", "B", "B", "B"], [1, 2, 10, 11, 12], 2)

Expected Output: 1

Explanation: Only the event at time 12 has two earlier B events at times 10 and 11 within the last 2 seconds.

Solution

def solution(ops, times, W):
    from collections import defaultdict, deque

    n = len(ops)
    if n == 0:
        return 0

    events = sorted((times[i], i, ops[i]) for i in range(n))
    history = defaultdict(deque)
    redundant = 0

    for t, idx, op in events:
        dq = history[op]

        while dq and t - dq[0] > W:
            dq.popleft()

        if len(dq) >= 2:
            redundant += 1

        dq.append(t)

    return redundant

Time complexity: O(n log n). Space complexity: O(n).

Hints

After ordering events by (time, original index), process them from earliest to latest.
For each operation name, keep only previous timestamps that are still within W seconds of the current event. The current event is redundant if at least two such timestamps remain.

Quick Overview