Solve Cache, Window, and Heap Problems

This is a multi-part coding exercise. For each part, design an algorithm, state its expected time and space complexity, and explain how it handles repeated values, empty inputs, and very large parameters. Part 1: Cache with Least-Frequent Eviction Write a function that simulates a cache using the least-frequently-used eviction rule. The function receives an integer capacity and a list of operations. Each operation is either ("put", key, value) or ("get", key). Return a list…