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

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:

  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.