Implement cache and gift assignment system

You are given two independent programming problems. --- ### Problem 1: Implement a bounded key–value cache Design a data structure that stores key–value pairs with the following behavior: - The cache is initialized with a positive integer `capacity`. - It supports two operations: - `get(key)`: return the value associated with `key` if it exists; otherwise return `-1`. - `put(key, value)`: insert or update the key–value pair. - When inserting a new key and the cache is at full capacity, it must evict **one** existing entry. - The entry to evict must be the **least recently used** (LRU) key. "Use" means any successful `get` or `put` on that key. - After a `get(key)` or `put(key, value)`, that key becomes the most recently used. - All operations (`get` and `put`) should run in **amortized O(1) time**. Assume: - Keys and values are integers. - There can be up to `10^5` operations. Define the class and methods in a language of your choice, for example: ```python\ nclass Cache: def __init__(self, capacity: int): pass def get(self, key: int) -> int: pass def put(self, key: int, value: int) -> None: pass ``` Describe the data structures you use and implement the methods. --- ### Problem 2: Assign secret gift givers (Secret Santa) You are given a CSV-formatted list of people and their email addresses. Each row has the fields: - `name` - `email` Example input (including header): ```csv name,email Alice,alice@example.com Bob,bob@example.com Charlie,charlie@example.com ``` You need to write a program that assigns each person a recipient to whom they will give a gift, subject to these rules: 1. **No one can be assigned to give a gift to themselves.** 2. Each person must give a gift to **exactly one** person. 3. Each person must receive a gift from **exactly one** person. In other words, the assignment is a **random permutation** of all participants such that there are **no fixed points** (a derangement). The program should output a CSV with the assignments. One reasonable format is: ```csv giver_name,giver_email,receiver_name,receiver_email Alice,alice@example.com,Bob,bob@example.com Bob,bob@example.com,Charlie,charlie@example.com Charlie,charlie@example.com,Alice,alice@example.com ``` Requirements and assumptions: - You may assume the input CSV fits in memory and contains **at least 2** participants; handle the case of fewer than 2 participants by reporting an error. - Names and emails are non-empty strings; emails may be assumed unique per person. - The algorithm should run efficiently for up to `10^4` participants. - The assignment should be randomized; there should not be a simple, obvious pattern like always shifting by one position unless you can argue it is valid and avoids self-assignments. - You can implement the interface in a way that is natural for your language. For example, in Python: ```python def assign_gifts(input_csv_path: str, output_csv_path: str) -> None: """Read participants from input_csv_path and write assignments to output_csv_path.""" pass ``` Explain any design choices and how your algorithm guarantees that no one is assigned themselves and that everyone both gives and receives exactly one gift.