← SoFi Interview Insights

SoFi·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Did a technical phone screen for a Software Engineer role at SoFi and it was genuinely one of the more frustrating interview experiences I've had. The interviewer barely engaged, kept the camera off, and the communication felt like pulling teeth the whole way through.

Questions Asked (1)

Q1

Implement an LRU cache (design a data structure that supports get and put operations in O(1) time, evicting the least recently used item when capacity is exceeded).

Algorithms & Data StructuresSystem Design
Author's notes

I'd never heard the term 'LinkedList + HashMap' used together as a named pattern before, so when the interviewer just dropped that phrase and stopped talking, I was genuinely lost for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: O(1) get and put, eviction of least recently used item when capacity is exceeded. Then explain that a hash map combined with a doubly linked list achieves O(1) for both operations, and walk through the design and implementation.

Pro tip: Mention that you would use a doubly linked list with sentinel head and tail nodes to simplify edge cases, and discuss how you would handle thread safety if needed in a concurrent environment.

1. Clarify requirements and constraints

Confirm that get and put must be O(1), capacity is fixed, and eviction policy is LRU. Ask about thread safety, null keys/values, and expected usage patterns.

2. Choose data structures

Explain that a hash map provides O(1) access to nodes, and a doubly linked list maintains recency order. Together they allow O(1) get, put, and eviction.

3. Design the operations

Detail how get moves the accessed node to the front (most recently used), and put inserts or updates a node, moving it to the front, and evicts the tail (least recently used) if capacity is exceeded.

4. Handle edge cases and optimizations

Discuss using sentinel nodes to avoid null checks, handling capacity 0 or 1, and updating existing keys. Mention potential thread safety with locks or concurrent data structures.

5. Analyze complexity and test

Confirm O(1) time for get and put, O(capacity) space. Walk through a simple example to verify correctness, and mention unit tests for eviction order and edge cases.

Key Points to Mention

  • Hash map for O(1) key lookup, mapping keys to nodes in the linked list.
  • Doubly linked list to maintain recency order, with most recently used at head and least recently used at tail.
  • Sentinel head and tail nodes to simplify insertion and removal logic.
  • Eviction policy: when capacity is exceeded, remove the tail node and delete its key from the hash map.
  • Thread safety considerations: use locks or ConcurrentHashMap with synchronization for concurrent access.
  • Time complexity: O(1) for both get and put; space complexity: O(capacity).

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