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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Solve Throughput, Rate Limiting, and LFU | Microsoft Coding Question

Solve Throughput, Rate Limiting, and LFU

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

The interview included the following coding tasks: 1. **Minimum processing speed**: You are given an array `piles`, where `piles[i]` is the size of the `i`th pile, and an integer `h`. In one hour, you may choose exactly one pile and process up to `k` items from it. If a pile has fewer than `k` items remaining, you finish it and the rest of that hour is unused. Return the minimum integer `k` such that all piles can be finished within `h` hours. 2. **Implement a rate limiter**: Design and implement a rate limiter that enforces a rule such as allowing at most `limit` requests per user within any rolling `windowSeconds` interval. Provide an API like `allow(userId, timestamp) -> bool`. Explain how you store request history, how expired requests are removed efficiently, and what the time and space complexity is. 3. **Implement an LFU eviction structure**: Design a key-value cache with a fixed capacity. Support `get(key)` and `put(key, value)` in O(1) average time. When the cache is full, evict the key with the lowest access frequency. If multiple keys have the same frequency, evict the least recently used among them.

Quick Answer: This set of tasks evaluates algorithmic problem-solving, data structure design, and systems-oriented reasoning by testing throughput calculation, rolling-window rate limiting, and LFU cache eviction with O(1) access constraints.

Part 1: Minimum Processing Speed

You are given an array piles where piles[i] is the size of the ith pile and an integer h. In one hour, you may choose exactly one pile and process up to k items from it. If a pile has fewer than k items left, you finish it and the rest of that hour is unused. Return the minimum integer k such that all piles can be finished within h hours.

Constraints

1 <= len(piles) <= 100000
1 <= piles[i] <= 1000000000
1 <= h <= 1000000000
h >= len(piles)

Examples

Input: ([3, 6, 7, 11], 8)

Expected Output: 4

Explanation: At k = 4, the hours needed are 1 + 2 + 2 + 3 = 8. Any smaller speed needs more than 8 hours.

Input: ([30, 11, 23, 4, 20], 5)

Expected Output: 30

Explanation: There are 5 piles and only 5 hours, so every pile must finish in one hour. The speed must be at least the largest pile.

Input: ([30, 11, 23, 4, 20], 6)

Expected Output: 23

Explanation: With k = 23, the hours needed are 2 + 1 + 1 + 1 + 1 = 6.

Input: ([1000000000], 2)

Expected Output: 500000000

Explanation: A single pile of 1,000,000,000 items completed over 2 hours needs ceiling(1000000000 / 2).

Hints

If you fix a speed k, you can compute the hours needed for each pile independently using ceiling division.
As k increases, the total hours needed never increases. That monotonic behavior suggests binary search.

Part 2: Rolling Window Rate Limiter

The original API is allow(userId, timestamp) -> bool. In this problem, write a batch simulator: given parallel arrays user_ids and timestamps for consecutive allow calls, return whether each call is allowed. A request at time t is allowed only if that user has fewer than limit previously allowed requests with timestamps in the interval (t - window_seconds, t]. Rejected requests do not consume quota. Timestamps are non-decreasing.

Constraints

0 <= limit <= 100000
1 <= window_seconds <= 1000000000
0 <= len(user_ids) == len(timestamps) <= 200000
timestamps is non-decreasing
user_ids[i] is a non-empty string

Examples

Input: (2, 5, ['alice', 'alice', 'alice', 'alice'], [1, 2, 3, 7])

Expected Output: [True, True, False, True]

Explanation: The first two requests are allowed. The third is blocked because two allowed requests still fall inside the last 5 seconds. By time 7, the earlier allowed requests have expired.

Input: (2, 3, ['a', 'b', 'a', 'a', 'b'], [1, 1, 2, 3, 4])

Expected Output: [True, True, True, False, True]

Explanation: Each user is tracked independently. User 'a' is blocked on the fourth call, while user 'b' is allowed again once the earlier request falls out of the window.

Input: (1, 10, ['x', 'x', 'x'], [5, 15, 16])

Expected Output: [True, True, False]

Explanation: The request at time 5 expires exactly when the timestamp reaches 15 because the window is (t - 10, t].

Input: (3, 60, [], [])

Expected Output: []

Explanation: No calls means no output.

Input: (0, 10, ['u', 'u'], [1, 2])

Expected Output: [False, False]

Explanation: If the limit is 0, no request can ever be accepted.

Hints

Store request history separately for each user.
Because timestamps are non-decreasing, expired timestamps can be removed from the front of a queue.

Part 3: LFU Cache with LRU Tie-Breaking

Implement an LFU (Least Frequently Used) cache with a fixed capacity. Write a batch simulator that processes operations in order. Each operation is either 'put' or 'get'. Return the results of all 'get' operations in the order they occur. If the cache is full, evict the key with the lowest access frequency; if multiple keys tie, evict the least recently used among that frequency group. Updating an existing key with 'put' counts as an access and increases its frequency.

Constraints

0 <= capacity <= 200000
0 <= len(operations) == len(keys) == len(values) <= 200000
operations[i] is either 'put' or 'get'
-1000000000 <= keys[i], values[i] <= 1000000000

Examples

Input: (2, ['put', 'put', 'get', 'put', 'get', 'get'], [1, 2, 1, 3, 2, 3], [1, 2, 0, 3, 0, 0])

Expected Output: [1, -1, 3]

Explanation: After key 1 is accessed, key 2 has the lower frequency and is evicted when key 3 is inserted.

Input: (2, ['put', 'put', 'put', 'get', 'get'], [1, 2, 3, 1, 3], [10, 20, 30, 0, 0])

Expected Output: [-1, 30]

Explanation: Keys 1 and 2 both have frequency 1 when key 3 is inserted, so the least recently used among them, key 1, is evicted.

Input: (2, ['put', 'put', 'put', 'get', 'get'], [1, 2, 2, 1, 2], [1, 2, 20, 0, 0])

Expected Output: [1, 20]

Explanation: Updating key 2 changes its value to 20 and also increases its frequency.

Input: (0, ['put', 'get'], [1, 1], [1, 0])

Expected Output: [-1]

Explanation: A zero-capacity cache cannot store any entries.

Hints

You need fast lookup by key and fast eviction by frequency.
Group keys by frequency, and within each frequency group keep keys in least-recently-used order.

Quick Overview

This set of tasks evaluates algorithmic problem-solving, data structure design, and systems-oriented reasoning by testing throughput calculation, rolling-window rate limiting, and LFU cache eviction with O(1) access constraints.