← Goldman Sachs Interview Insights

Goldman Sachs·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Goldman Sachs SWE interview with a fraud systems coding problem. Pretty focused on the design choices behind the data structure, not just getting a working solution.

Questions Asked (1)

Q1

You're extending a fraud rules engine to support a sliding 60-minute window velocity check. Reject any transaction where the user's approved transaction total over the past hour plus the new transaction amount would exceed $5000. Walk through your data structure choice and the time complexity per check.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

I went with a per-user deque of (timestamp, amount) pairs.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and assumptions, then propose a sliding window approach using a deque (or circular buffer) to store (timestamp, amount) pairs of approved transactions within the last 60 minutes. Explain how you maintain a running sum to achieve O(1) amortized time per check, and discuss trade-offs like memory usage and handling out-of-order events.

Pro tip: Mention that in a real fraud system, you'd likely use a distributed cache like Redis with sorted sets or a time-series database to handle scale and persistence, but for the core algorithm, a deque with a running sum is optimal. Also, highlight the importance of idempotency and handling duplicate transactions.

1. Clarify requirements and assumptions

Confirm the definition of 'approved transaction total', whether timestamps are monotonic, and if the window is inclusive/exclusive. Ask about expected throughput and memory constraints.

2. Choose data structure

Propose a deque (double-ended queue) to store (timestamp, amount) pairs in chronological order, allowing O(1) append and popleft. Alternatively, mention a circular buffer if memory is fixed.

3. Maintain running sum and evict expired entries

Keep a running sum of amounts in the window. On each new transaction, evict from the front while the oldest timestamp is older than 60 minutes, subtracting its amount from the sum.

4. Check and update

If running sum + new amount > $5000, reject; otherwise, approve, add the new transaction to the back, and add its amount to the running sum.

5. Analyze complexity and discuss trade-offs

State that each check is O(1) amortized because each transaction is added and removed at most once. Discuss memory O(n) where n is number of transactions in window, and potential concurrency issues.

Key Points to Mention

  • Sliding window vs. fixed window: sliding window avoids boundary spikes.
  • Use of deque for O(1) append and popleft operations.
  • Running sum to avoid O(n) summation per check.
  • Time complexity: O(1) amortized per check, O(n) worst-case if many evictions at once.
  • Space complexity: O(n) where n is number of transactions in the 60-minute window.
  • Handling out-of-order timestamps: may need a priority queue or sorted structure, but assume monotonic for simplicity.
  • Scalability: consider sharding by user ID and using distributed cache for production.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.