Solve substring and top‑K pair problems

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