Implement cache and gift assignment system
Company: Shopify
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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.
Overview: This two-part exercise evaluates a candidate's competence in designing efficient in-memory data structures with correct eviction semantics (bounded LRU cache with amortized O(1) operations) and in implementing randomized permutation algorithms and input/output handling for derangement-based Secret Santa assignments from CSV input.
Read the full Shopify Software Engineer interview experience this question came from
Community answers
Answer by nirav.shingala
class Node:
def init(self, key: int, val: int):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def init(self, capacity):
self.capacity = capacity
self.cache = {}
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_front(node)
return node.val
def put(self, key, value):
if key in self.cache:
node = self.cache[key]
node.val = value
self._remove(node)
self._add_front(node)
return
node = Node(key, value)
self.cache[key] = node
self._add_front(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
