Katkat
Back

Implement Sliding Windows and LRU Cache

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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 1s by flipping at most k zeros to ones.

Example:

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 1s 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.