Solve Cache, Window, and Heap Problems

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.