Constraints

• 1 <= K <= 10^5
• 1 <= W <= 10^9
• 0 <= len(timestamps) <= 2 * 10^5
• 0 <= timestamps[i] <= 10^9
• timestamps is sorted in nondecreasing order

Examples

Solution

def solution(K, W, timestamps):
    from collections import deque

    q = deque()
    result = []

    for t in timestamps:
        while q and q[0] <= t - W:
            q.popleft()

        if len(q) < K:
            q.append(t)
            result.append(True)
        else:
            result.append(False)

    return result

Time complexity: O(n), where n is the number of timestamps. Each allowed timestamp is appended once and removed once.. Space complexity: O(K) in the worst case, because the queue never holds more than K active allowed requests..

Hints

1. Keep only allowed request timestamps that are still inside the current rolling window.
2. A deque is a natural fit because expired timestamps always leave from the front.

Constraints

• 1 <= Ku, Ke <= 10^5
• 1 <= W <= 10^9
• 0 <= len(requests) <= 2 * 10^5
• userId and experience are strings
• 0 <= timestamp <= 10^9
• request timestamps are sorted in nondecreasing order

Examples

Solution

def solution(Ku, Ke, W, requests):
    from collections import deque

    user_queues = {}
    exp_queues = {}
    result = []

    for user_id, experience, timestamp in requests:
        user_q = user_queues.get(user_id)
        if user_q is not None:
            while user_q and user_q[0] <= timestamp - W:
                user_q.popleft()
            if not user_q:
                del user_queues[user_id]
                user_q = None

        exp_q = exp_queues.get(experience)
        if exp_q is not None:
            while exp_q and exp_q[0] <= timestamp - W:
                exp_q.popleft()
            if not exp_q:
                del exp_queues[experience]
                exp_q = None

        user_count = 0 if user_q is None else len(user_q)
        exp_count = 0 if exp_q is None else len(exp_q)

        if user_count < Ku and exp_count < Ke:
            if user_q is None:
                user_q = deque()
                user_queues[user_id] = user_q
            if exp_q is None:
                exp_q = deque()
                exp_queues[experience] = exp_q

            user_q.append(timestamp)
            exp_q.append(timestamp)
            result.append(True)
        else:
            result.append(False)

    return result

Time complexity: O(n) amortized total time, where n is the number of requests. Each allowed timestamp is appended once and removed once from its user queue and once from its experience queue.. Space complexity: O(a + u + e) for active data, where a is the number of allowed requests still inside the window, and u and e are the numbers of active userId and experience keys. This is O(n) in the worst case. Deleting empty deques after pruning garbage-collects stale keys..

Hints

1. Maintain one hash map of deques for userId counts and another for experience counts.
2. Prune expired timestamps first, then check both limits, and append to both deques only if both checks pass.