You are given two independent programming problems.
Design a data structure that stores key–value pairs with the following behavior:
capacity
.
get(key)
: return the value associated with
key
if it exists; otherwise return
-1
.
put(key, value)
: insert or update the key–value pair.
get
or
put
on that key.
get(key)
or
put(key, value)
, that key becomes the most recently used.
get
and
put
) should run in
amortized O(1) time
.
Assume:
10^5
operations.
Define the class and methods in a language of your choice, for example:
Describe the data structures you use and implement the methods.
You are given a CSV-formatted list of people and their email addresses. Each row has the fields:
name
email
Example input (including header):
You need to write a program that assigns each person a recipient to whom they will give a gift, subject to these rules:
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:
Requirements and assumptions:
10^4
participants.
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.