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

What role is this question designed for?

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

Implement Sliding Windows and LRU Cache | Bytedance Coding Question

Implement Sliding Windows and LRU Cache

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two coding tasks. ### Task 1: Longest Subarray of Ones Given a binary array `nums` and an integer `k`, return the maximum length of a contiguous subarray that can be made entirely of `1`s by flipping at most `k` zeros to ones. **Example:** ```text nums = [1, 1, 0, 0, 1, 1, 1, 0, 1], k = 2 Output: 7 ``` One valid subarray is `[0, 0, 1, 1, 1, 0, 1]`, where flipping two zeros makes the entire subarray all ones. **Follow-up:** Extend the idea to a 2D binary matrix. Given a binary matrix `grid` and an integer `k`, find the largest-area axis-aligned rectangular submatrix that can be made entirely of `1`s by flipping at most `k` zeros. ### Task 2: LRU Cache Design and implement an LRU Cache with the following operations: - `LRUCache(int capacity)`: Initialize the cache with a positive capacity. - `int get(int key)`: Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key makes it the most recently used item. - `void put(int key, int value)`: Insert or update the value for `key`. If the cache exceeds capacity, evict the least recently used item. Both `get` and `put` must run in `O(1)` average time.

Quick Answer: This question evaluates algorithmic problem-solving and data-structure design, testing sliding-window and 2D submatrix reasoning for maximizing contiguous ones with bounded flips and the design of an LRU cache that enforces O(1) get/put semantics.

Part 1: Longest Subarray of Ones

Given a binary array nums and an integer k, return the maximum length of a contiguous subarray that can be turned into all 1s by flipping at most k zeros. If nums is empty, return 0.

Constraints

0 <= len(nums) <= 200000
nums[i] is either 0 or 1
0 <= k <= len(nums)

Examples

Input: ([1, 1, 0, 0, 1, 1, 1, 0, 1], 2)

Expected Output: 7

Explanation: The longest window with at most two zeros has length 7.

Input: ([], 3)

Expected Output: 0

Explanation: An empty array has no subarrays.

Input: ([0], 1)

Expected Output: 1

Explanation: The single zero can be flipped.

Input: ([1, 1, 1, 1], 0)

Expected Output: 4

Explanation: The whole array is already all ones.

Input: ([0, 0, 0], 0)

Expected Output: 0

Explanation: No flips are allowed, so no non-empty all-ones subarray exists.

Hints

Use a sliding window and track how many zeros are currently inside the window.
If the window contains more than k zeros, move the left pointer right until the window becomes valid again.

Part 2: Largest All-Ones Rectangular Submatrix with Up to k Flips

Given a binary matrix grid and an integer k, find the maximum area of an axis-aligned rectangular submatrix that can be turned into all 1s by flipping at most k zeros inside that rectangle. If the grid is empty, return 0.

Constraints

0 <= number of rows <= 150
0 <= number of columns <= 150
All rows in grid have the same length
grid[r][c] is either 0 or 1
0 <= k <= rows * columns

Examples

Input: ([[1, 0, 1], [1, 0, 1], [1, 1, 1]], 1)

Expected Output: 6

Explanation: The bottom two rows across all three columns contain exactly one zero, so area 6 is achievable.

Input: ([[1, 0, 0, 1, 1]], 1)

Expected Output: 3

Explanation: In a single row, the problem reduces to the 1D version. The best width with at most one zero is 3.

Input: ([[1, 1], [1, 1]], 0)

Expected Output: 4

Explanation: The whole matrix is already all ones.

Input: ([], 3)

Expected Output: 0

Explanation: An empty grid has no valid rectangle.

Input: ([[0, 0], [0, 0]], 2)

Expected Output: 2

Explanation: You can flip at most two cells, so the largest all-ones rectangle has area 2.

Hints

Fix a top row and a bottom row. For that row band, each column contributes how many zeros it contains between those two rows.
Once you compress a row band into column zero-counts, the problem becomes finding the longest contiguous column range whose sum is at most k.

Part 3: LRU Cache Simulation

Simulate an LRU cache with fixed capacity. Each operation is encoded as a list: [1, key, value] means put(key, value) and [0, key] means get(key). A get returns the stored value or -1 if the key is missing. Any successful get or put on an existing key makes that key the most recently used. If inserting a new key would exceed capacity, evict the least recently used key. Return the outputs of all get operations in order.

Constraints

1 <= capacity <= 100000
0 <= len(operations) <= 200000
For a put, the operation format is [1, key, value]
For a get, the operation format is [0, key]
Keys and values fit in 32-bit signed integers

Examples

Input: (2, [[1, 1, 1], [1, 2, 2], [0, 1], [1, 3, 3], [0, 2], [1, 4, 4], [0, 1], [0, 3], [0, 4]])

Expected Output: [1, -1, -1, 3, 4]

Explanation: This is the standard LRU behavior: keys are evicted in least-recently-used order.

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

Expected Output: [1, -1, 2]

Explanation: With capacity 1, inserting key 3 evicts key 2.

Input: (3, [])

Expected Output: []

Explanation: No operations means no get results.

Input: (2, [[1, 1, 10], [1, 2, 20], [1, 1, 15], [1, 3, 30], [0, 1], [0, 2], [0, 3]])

Expected Output: [15, -1, 30]

Explanation: Updating key 1 makes it most recent, so key 2 is evicted when key 3 is inserted.

Hints

A hash map gives O(1) lookup by key, but you still need O(1) updates to recency order.
A doubly linked list lets you move a node to the front and remove the least recently used node from the back in O(1).

Quick Overview

This question evaluates algorithmic problem-solving and data-structure design, testing sliding-window and 2D submatrix reasoning for maximizing contiguous ones with bounded flips and the design of an LRU cache that enforces O(1) get/put semantics.