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 LinkedIn.

What role is this question designed for?

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

Solve Cache, Window, and Heap Problems | LinkedIn Coding Question

Quick Overview

This question evaluates competency in advanced data structures and algorithmic techniques—specifically frequency-based cache design, sliding-window substring search, and heap-driven k-pair generation—along with time and space complexity analysis and robust edge-case handling.

Solve Cache, Window, and Heap Problems

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You may be asked to solve multiple algorithmic problems in coding rounds: 1. **Frequency-based cache**: Implement a cache with `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. 2. **Shortest covering substring**: Given two strings `s` and `t`, return the shortest contiguous substring of `s` that contains every character in `t` with the required multiplicities. If no such substring exists, return an empty string. 3. **Smallest-sum pair generation**: Given two non-decreasing integer arrays `nums1` and `nums2`, and an integer `k`, return the `k` pairs `(nums1[i], nums2[j])` with the smallest sums. If fewer than `k` pairs exist, return all possible pairs. Discuss the expected time and space complexity for each problem and handle edge cases such as duplicates, empty input, and large `k`.

Quick Answer: This question evaluates competency in advanced data structures and algorithmic techniques—specifically frequency-based cache design, sliding-window substring search, and heap-driven k-pair generation—along with time and space complexity analysis and robust edge-case handling.

Part 1: Frequency-Based Cache Simulator

Design a function that simulates an LFU (Least Frequently Used) cache. The cache supports two operations: `put(key, value)` and `get(key)`. When the cache reaches capacity and a new key must be inserted, evict the key with the lowest access frequency. If multiple keys have the same frequency, evict the least recently used among them. Updating an existing key replaces its value and also counts as an access. Instead of implementing a class-based API, write a function that receives the cache capacity and a list of operations, then returns the results of all `get` operations in order.

Constraints

0 <= capacity <= 10^5
1 <= len(operations) <= 2 * 10^5
Keys and values are integers
Expected average time per operation: O(1)

Examples

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

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

Explanation: Standard LFU behavior. On the second eviction, keys 1 and 3 have the same frequency, so the least recently used among them is removed.

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

Expected Output: [-1]

Explanation: A cache with capacity 0 cannot store anything.

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

Expected Output: [-1, 20, 30]

Explanation: Before inserting key 3, keys 1 and 2 both have frequency 1. Key 1 is least recently used, so it is evicted.

Input: (2, [("put", 1, 1), ("put", 2, 2), ("put", 2, 20), ("put", 3, 3), ("get", 1), ("get", 2), ("get", 3)])

Expected Output: [-1, 20, 3]

Explanation: Updating key 2 counts as an access, so key 1 becomes the eviction target.

Hints

Track each key's current value and frequency in a hash map.
To break ties by recency among keys with the same frequency, maintain keys of each frequency in insertion order.

Part 2: Shortest Covering Substring

Given two strings `s` and `t`, return the shortest contiguous substring of `s` that contains every character from `t` with the required multiplicities. If no such substring exists, return an empty string. For example, if `t = "AABC"`, a valid window must contain two `'A'` characters, one `'B'`, and one `'C'`.

Constraints

0 <= len(s), len(t) <= 2 * 10^5
Strings may contain repeated characters
An O(len(s) + len(t)) sliding-window solution is expected

Examples

Input: ("ADOBECODEBANC", "ABC")

Expected Output: "BANC"

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

Input: ("AAABBC", "AABC")

Expected Output: "AABBC"

Explanation: The target requires two As, one B, and one C, so `AABBC` is the shortest valid window.

Input: ("a", "aa")

Expected Output: ""

Explanation: The source does not contain enough copies of `a`.

Input: ("anything", "")

Expected Output: ""

Explanation: An empty target is covered by the empty substring.

Hints

Count how many of each character are still needed from `t`.
Expand the right pointer until the window is valid, then shrink from the left while keeping it valid.

Part 3: K Smallest-Sum Pairs

You are given two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order, and an integer `k`. Return the `k` pairs `(nums1[i], nums2[j])` with the smallest sums. If fewer than `k` pairs exist, return all possible pairs. The result should be ordered by the sequence in which the next smallest pair is extracted. A heap-based best-first search is expected.

Constraints

0 <= len(nums1), len(nums2) <= 10^5
Arrays are sorted in non-decreasing order
0 <= k <= 10^5
Values may be negative or duplicated

Examples

Input: ([1, 7, 11], [2, 4, 6], 3)

Expected Output: [[1, 2], [1, 4], [1, 6]]

Explanation: These are the three pairs with the smallest sums.

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

Expected Output: [[1, 1], [1, 1], [1, 2], [1, 2], [2, 1], [1, 3], [1, 3], [2, 2], [2, 3]]

Explanation: There are only 9 total pairs, so return all of them. Duplicates are allowed.

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

Expected Output: []

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

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

Expected Output: []

Explanation: Requesting zero pairs should return an empty list.

Hints

Think of each index `i` in `nums1` as starting a sorted row of pair sums with `nums2`.
A min-heap can always tell you the next smallest unseen pair without generating all pairs.

Quick Overview