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:

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

name,email
Alice,[email protected]
Bob,[email protected]
Charlie,[email protected]

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:

giver_name,giver_email,receiver_name,receiver_email
Alice,[email protected],Bob,[email protected]
Bob,[email protected],Charlie,[email protected]
Charlie,[email protected],Alice,[email protected]

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:

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.