Katkat
Back

Solve substring and top‑K pair problems

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to solve a sliding window string problem followed by a heap-based retrieval task for ranked items.

Part 1: Minimum Window Substring

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such window exists, return an empty string.

Signature

def min_window(s: str, t: str) -> str:

Constraints

  • 1 <= s.length, t.length <= 10^5
  • s and t consist of uppercase and lowercase English letters.

Example

  • Input: s = "ADOBECODEBANC", t = "ABC"
  • Output: "BANC"
  • Explanation: The minimum window is "BANC" which includes 'A', 'B', and 'C'.

Part 2: Top-K Frequent Pairs

Given a list of product pairs (product_a, product_b) and their co-occurrence frequency, return the top-K pairs with the highest frequencies. If two pairs have the same frequency, order them lexicographically by the first product, then the second.

Signature

def top_k_pairs(pairs: List[Tuple[str, str, int]], k: int) -> List[Tuple[str, str]]:

Constraints

  • 1 <= k <= number of pairs
  • 1 <= pairs.length <= 10^5

Example

  • Input: pairs = [("apple", "banana", 10), ("orange", "apple", 20), ("banana", "orange", 10)], k = 2
  • Output: [('orange', 'apple'), ('apple', 'banana')]
  • Explanation: "orange-apple" has 20. "apple-banana" and "banana-orange" both have 10, but "apple-banana" is lexicographically smaller.

Hints

Hint 1

For Part 1, use a frequency map and two pointers to expand and shrink your search window.

Hint 2

For Part 2, a min-heap of size K can efficiently maintain the top elements while keeping the space complexity low.

Hint 3

In Part 2, ensure your comparison logic in the heap handles the tie-breaking rules for frequency and lexicographical order.

Follow-up questions

  • How would you modify the sliding window approach if you needed to find the longest substring instead of the minimum?
  • How would you optimize the top-K retrieval if the number of pairs was massive and didn't fit in memory?
  • In a multi-threaded environment, what locking strategy would you suggest if the product frequency data is being updated concurrently?