Katkat
Back

Parse Requests and Compute Balances

RobinhoodSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to parse structured text commands, manage relational state between users, and implement transactional logic with integrity constraints.

Problem Statement

You are building a simple accounting system that tracks balances for users and their friend relationships. Implement a class AccountSystem to process a list of request strings.

Request Types

  1. DEPOSIT : Add to's balance. If the user does not exist, create the account with an initial balance of 0 before depositing.
  2. TRANSFER : Transfer from to ``.
    • Constraints: This is only successful if sender and receiver are friends (see FRIEND command) AND the sender has a balance >= amount. If the transfer fails, the balances remain unchanged.
  3. FRIEND : Create a friendship between user1 and user2. Friendships are bidirectional.

Implementation

Implement the following method: process_requests(requests: List[str]) -> List[str]

  • The output should be a list of strings representing the final balances of all users, formatted as ":", sorted alphabetically by username.
  • If a TRANSFER command fails due to insufficient funds or lack of friendship, ignore the transaction.

Examples

# Input
requests = [
  "DEPOSIT Alice 100", 
  "DEPOSIT Bob 50", 
  "FRIEND Alice Bob", 
  "TRANSFER Alice Bob 30"
]
# Output
# ["Alice:70", "Bob:80"]

Constraints

  • Number of requests: 1 to 1000.
  • Usernames: alphanumeric strings.
  • Amounts: positive integers.
  • Ensure you handle cases where users are referenced in TRANSFER or FRIEND commands before they have been explicitly created via DEPOSIT (assume they start with 0 balance).

Edge Cases

  • Transferring money to oneself.
  • Transferring between users who are not friends.
  • Commands involving non-existent users.

Hints

Hint 1

Use a hash map (dictionary) to store balances and an adjacency list (or set of frozensets) to track the bidirectional friendship graph.

Hint 2

For the `TRANSFER` command, perform validation checks for both the friendship status and the balance before updating the state variables.

Hint 3

Since the final output requires alphabetical ordering, extract the keys from your balance map and sort them before formatting the return strings.

Follow-up questions

  • How would you modify the system to support a 'history' of all successful transactions for audit purposes?
  • If the number of users grows to millions, how would you optimize the storage of friendship relationships?
  • How would you handle concurrency if multiple threads were attempting to transfer money from the same account simultaneously?