PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

This multi-part question evaluates algorithm design and data-structure proficiency across string processing (minimum window substring), pair-selection for top‑k products, and LRU cache design with concurrency considerations, situating it in the Coding & Algorithms and Systems/Concurrency domains.

  • medium
  • LinkedIn
  • Coding & Algorithms
  • Software Engineer

Solve substring and top‑K pair problems

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem A: Smallest window containing all characters Given two strings `s` and `t`, find the shortest substring of `s` that contains **all characters of `t` with multiplicity** (i.e., if `t` has two `'a'`s, the window must contain at least two `'a'`s). - **Input:** strings `s`, `t` - **Output:** the minimum window substring; return an empty string if no such window exists - **Constraints (typical):** `1 <= |s| <= 2e5`, `1 <= |t| <= 2e5`, ASCII letters ## Problem B: Find k pairs with smallest product Given two integer arrays `A` and `B` (not necessarily the same length) and an integer `k`, return the `k` pairs `(A[i], B[j])` with the **smallest products** `A[i] * B[j]`. - If fewer than `k` pairs exist, return all pairs. - Define an output format (any is acceptable): e.g., list of pairs. - Clarify how to break ties (any consistent order is acceptable). **Assumptions to state in interview (choose as needed):** - Arrays may contain negatives/zeros (if so, explain how your approach handles them). - If arrays are guaranteed non-decreasing and non-negative, you may use a heap-based best-first search approach. ## Problem C: Design an LRU cache (with concurrency follow-up) Design an in-memory LRU (Least Recently Used) cache that supports: - `get(key) -> value | -1` - `put(key, value)` Requirements: - Target **O(1)** average time per operation. - Capacity `C`: when adding beyond capacity, evict the least-recently-used entry. **Follow-up:** Make the cache safe for multi-threaded access (explain locking strategy and potential contention).

Quick Answer: This multi-part question evaluates algorithm design and data-structure proficiency across string processing (minimum window substring), pair-selection for top‑k products, and LRU cache design with concurrency considerations, situating it in the Coding & Algorithms and Systems/Concurrency domains.

Part 1: Smallest window containing all characters

Given two strings s and t, return the shortest contiguous substring of s that contains every character from t with multiplicity. For example, if t contains two 'a' characters, the window must also contain at least two 'a' characters. If no such substring exists, return an empty string. If multiple minimum-length answers exist, return the leftmost one.

Constraints

  • 0 <= len(s) <= 2 * 10^5
  • 0 <= len(t) <= 2 * 10^5
  • s and t contain ASCII letters
  • For robustness, empty strings may appear in tests

Examples

Input: ('ADOBECODEBANC', 'ABC')

Expected Output: 'BANC'

Explanation: The shortest substring containing A, B, and C is 'BANC'.

Input: ('a', 'a')

Expected Output: 'a'

Explanation: The whole string is the only valid window.

Input: ('a', 'aa')

Expected Output: ''

Explanation: s does not contain enough 'a' characters.

Input: ('', 'a')

Expected Output: ''

Explanation: An empty source string cannot contain any non-empty target.

Input: ('bbaa', 'aba')

Expected Output: 'baa'

Explanation: The target needs two 'a' characters and one 'b'; 'baa' is the shortest valid window.

Hints

  1. Use a sliding window with two pointers instead of checking every substring.
  2. Track how many required characters are still missing; when the window becomes valid, try shrinking it from the left.

Part 2: Find k pairs with smallest product

You are given two integer arrays A and B, both sorted in non-decreasing order and containing only non-negative integers, along with an integer k. Return the k pairs (A[i], B[j]) with the smallest products A[i] * B[j]. If fewer than k pairs exist, return all of them. Break ties by smaller index i first, then smaller index j.

Constraints

  • 0 <= len(A), len(B) <= 10^5
  • 0 <= A[i], B[j] <= 10^9
  • 0 <= k <= 10^5
  • A and B are sorted in non-decreasing order

Examples

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

Expected Output: [(1, 3), (1, 4), (2, 3)]

Explanation: The products are 3, 4, 6, and 8; the three smallest pairs are returned.

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

Expected Output: [(0, 0), (0, 3), (1, 0), (2, 0)]

Explanation: Several pairs have product 0; tie-breaking uses smaller i, then smaller j.

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

Expected Output: [(1, 1), (1, 1)]

Explanation: Only two total pairs exist, so both are returned.

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

Expected Output: []

Explanation: If one array is empty, no pairs can be formed.

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

Expected Output: []

Explanation: Requesting zero pairs should return an empty list.

Hints

  1. Treat each A[i] as the start of a sorted row of products A[i] * B[0], A[i] * B[1], ...
  2. A min-heap can always tell you the next smallest unseen pair and lets you expand only one step at a time.

Part 3: Design an LRU cache

Implement an in-memory LRU (Least Recently Used) cache. The cache has a fixed capacity. It must support get(key) and put(key, value) in O(1) average time. When the cache exceeds its capacity, evict the least recently used key. For this coding version, you are given a capacity and a list of operations; return the outputs of all get operations in order.

Constraints

  • 0 <= capacity <= 10^5
  • 1 <= number of operations <= 2 * 10^5
  • Keys and values are integers
  • Average O(1) time per get/put is required

Examples

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

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

Explanation: This is the classic LRU example with evictions of keys 2 and then 1.

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

Expected Output: [-1, 2]

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

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

Expected Output: [10, -1, 3]

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

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

Expected Output: [-1]

Explanation: A cache with capacity 0 can never store anything.

Hints

  1. A hash map gives O(1) access to nodes by key, but you still need a structure that can move nodes to the front in O(1).
  2. A doubly linked list is a natural fit for tracking most-recently-used and least-recently-used entries.

Part 4: Make the LRU cache safe for multi-threaded access

Implement a thread-safe LRU cache and execute scheduled operations from multiple threads. You are given a cache capacity and a list of per-thread operation batches. Each operation has a unique global step number from 0 to m - 1. Start one worker thread per batch, and make all threads use one shared cache. An operation may execute only when its step equals the next global step. This makes the final result deterministic while still requiring proper synchronization. Use a coarse-grained lock around the cache internals. Return both the results of all get operations in step order and the final cache state from most-recently-used to least-recently-used.

Constraints

  • 0 <= capacity <= 10^4
  • 0 <= total number of operations across all threads <= 2 * 10^5
  • Keys and values are integers
  • Each step is unique and all steps together form 0..m-1
  • Use O(1) average-time cache operations with proper locking

Examples

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

Expected Output: ([-1, 2, 3], [(3, 3), (2, 2)])

Explanation: Key 1 is evicted when key 3 is inserted. The later gets for 2 and 3 both succeed.

Input: (2, [[(0, 'put', 1, 1), (2, 'get', 1), (4, 'put', 3, 3)], [(1, 'put', 2, 2), (3, 'put', 4, 4), (5, 'get', 2), (6, 'get', 1), (7, 'get', 4), (8, 'get', 3)]])

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

Explanation: The get at step 2 refreshes key 1, so key 2 is evicted first, then key 1.

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

Expected Output: ([-1, -1], [])

Explanation: Capacity 0 means every put is ignored.

Input: (1, [[], [(0, 'put', 5, 50), (1, 'get', 5), (2, 'put', 6, 60), (3, 'get', 5), (4, 'get', 6)]])

Expected Output: ([50, -1, 60], [(6, 60)])

Explanation: An empty thread batch is allowed. With capacity 1, key 5 is evicted when key 6 is inserted.

Hints

  1. Inside the cache, protect the hash map and linked list with one mutex so each get or put is atomic.
  2. A condition variable plus a shared next_step counter can enforce the provided global schedule across worker threads.
Last updated: May 9, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Count Trips From Vehicle Logs - LinkedIn (easy)
  • Design O(1) Randomized Multiset - LinkedIn (easy)
  • Process Mutable Matrix Sum Queries - LinkedIn (medium)
  • Design a Randomized Multiset - LinkedIn (medium)
  • Can You Place N Objects? - LinkedIn (medium)