Design in-memory payment and friendship system
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Design and implement an **in-memory payment system** with simple social features. The system processes a sequence of **requests** that can:
1. **Register a user**
2. **Send a friend request** from one user to another
3. **Accept a friend request** (referencing a previous friend request by its request ID)
4. **Transfer money** between two users
### Rules and Requirements
1. **Users and balances**
- Each user has:
- A unique `user_id` (string)
- A `balance` (integer amount, e.g., cents)
- A list or set of **friends** (other user IDs)
2. **Friend requests**
- A friend request is initiated via a request that includes:
- A unique `req_id` for this friend request
- `user1` and `user2` (both must be existing users)
- An **accept-friend** request does *not* repeat the usernames; instead it contains:
- Its own `req_id` (unique for the accept request)
- The `req_id` of the original friend request to accept
- Only when an accept-friend request is processed successfully do `user1` and `user2` become friends.
3. **Transfers**
- Money can **only** be transferred between users who are **already friends**.
- A transfer request specifies:
- A unique `req_id`
- `from_user`
- `to_user`
- `amount` (> 0)
- A transfer must **fail** if:
- Either user does not exist, or
- The users are not friends, or
- `from_user` does not have enough balance.
- On success:
- Subtract `amount` from `from_user.balance`.
- Add `amount` to `to_user.balance`.
4. **Error handling**
- If a request is invalid (e.g., refers to unknown user, refers to a non-existent friend request ID, tries to accept a friend request twice, etc.), the system should indicate **failure** for that request.
- You can define reasonable behavior for repeated or conflicting requests, but document it in comments.
### Interface
Design classes and methods in an **object-oriented** way.
One possible interface (you can adjust names/signatures as long as behavior is clear):
```python
class PaymentSystem:
def register_user(self, user_id: str, initial_balance: int) -> bool:
"""Register a new user with given balance. Return False if user_id already exists."""
def send_friend_request(self, req_id: str, user1: str, user2: str) -> bool:
"""Store a friend request identified by req_id. Return False on invalid input or duplicate req_id."""
def accept_friend_request(self, req_id: str, original_req_id: str) -> bool:
"""Accept the previously stored friend request with ID original_req_id. Return False if original_req_id doesn't exist, is already accepted, or users are invalid."""
def transfer(self, req_id: str, from_user: str, to_user: str, amount: int) -> bool:
"""Transfer amount from from_user to to_user if they are friends and balance is sufficient. Return True on success, False otherwise."""
```
Your implementation should:
- Maintain all necessary internal state in memory (no external database required).
- Enforce the **friendship** and **balance** constraints for transfers.
- Correctly handle the indirection where a friend-accept request refers to an earlier friend-request by `req_id`.
You may ignore concurrency in the basic solution, but you can optionally comment on how you would make operations atomic under multiple threads.
Quick Answer: This question evaluates object-oriented design skills, stateful in-memory data structures, request processing, and correctness constraints such as friend relationships, unique request IDs, and atomic balance transfers.
Implement an in-memory payment system with simple social features. The system processes a sequence of **operations**; you implement `solution(operations)` which applies each operation in order and returns a list with one result per operation.
Each operation is a tuple whose first element is the op name:
| Operation | Meaning | Result |
|-----------|---------|--------|
| `('register', user_id, initial_balance)` | Register a new user with the given balance. | `True` on success, `False` if the user already exists or `initial_balance < 0`. |
| `('send', req_id, user1, user2)` | Store a friend request identified by `req_id` (the two are **not** friends yet). | `False` if `req_id` was already used, either user is unknown, or `user1 == user2`; else `True`. |
| `('accept', req_id, original_req_id)` | Accept the earlier friend request whose id is `original_req_id`. The accept op does **not** repeat the usernames — you must look them up by `original_req_id`. | `False` if `req_id` was already used, `original_req_id` does not exist, or it was already accepted; else `True` and the two users become friends. |
| `('transfer', req_id, from_user, to_user, amount)` | Move `amount` from `from_user` to `to_user`. | `True` only if `req_id` is fresh, `amount > 0`, both users exist, they are **friends**, and `from_user` has enough balance; else `False`. |
| `('balance', user_id)` | Query a balance. | The integer balance, or `None` if the user is unknown. |
| `('are_friends', user1, user2)` | Query friendship. | `True`/`False`. |
### Rules
- Money can only be transferred **between friends**, and only after a friend request has been **accepted** (the indirection: `send` stores the pair under a `req_id`, `accept` references that `req_id`).
- A transfer fails on unknown user, non-friendship, non-positive amount, or insufficient balance — and must leave balances unchanged on failure.
- Every `req_id` used by `send` / `accept` / `transfer` is globally unique; a reused `req_id` makes that operation fail.
- All state is held in memory — no external database.
Return the list of per-operation results in order.
Constraints
- User ids and req_ids are strings; every send/accept/transfer req_id is globally unique (a reused req_id fails).
- Balances and amounts are integers; initial_balance >= 0 and transfer amount > 0.
- Transfers are only allowed between users whose friend request has been accepted (they are friends).
- A failed transfer must leave both balances unchanged.
- Accepting an already-accepted or unknown original_req_id fails.
Examples
Input: ([('register','alice',100),('register','bob',50),('send','r1','alice','bob'),('accept','r2','r1'),('are_friends','alice','bob'),('transfer','r3','alice','bob',30),('balance','alice'),('balance','bob')],)
Expected Output: [True, True, True, True, True, True, 70, 80]
Explanation: Happy path: register two users, send + accept a friend request (now friends), then a 30-unit transfer succeeds, moving alice 100->70 and bob 50->80.
Input: ([('register','alice',100),('register','bob',50),('transfer','r1','alice','bob',10)],)
Expected Output: [True, True, False]
Explanation: Transfer fails because alice and bob were never made friends (no accepted friend request).
Hints
- Keep three maps: balances (user -> int), friends (user -> set of users), and pending (friend-request req_id -> the (user1, user2) pair). The accept op only carries an original_req_id, so you must look the pair up there.
- Track every consumed req_id in a single set so a reused id (across send/accept/transfer) deterministically fails, and a separate 'accepted' set so a friend request can't be accepted twice.
- Validate a transfer in order: fresh req_id, amount > 0, both users exist, they are friends, sufficient balance — and only mutate the two balances once all checks pass so failures leave state untouched.