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.

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.

Hints

  1. Use a sliding window and track how many zeros are currently inside the window.
  2. 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.

Hints

  1. Fix a top row and a bottom row. For that row band, each column contributes how many zeros it contains between those two rows.
  2. 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.

Hints

  1. A hash map gives O(1) lookup by key, but you still need O(1) updates to recency order.
  2. 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).

Loading coding console...