Company-10-Visa

Visa Interview Prep

Interview Profile

• Rounds: 4–5 (coding + system design for payment processing + behavioral)
• Tone: Correctness and reliability over cleverness. Visa processes 65,000 transactions per second — an off-by-one in a fraud detection window or a missed edge case in a cycle-detection algorithm is a production incident.
• Senior bar: Discuss consistency, idempotency, and exactly-once semantics alongside the algorithm. A correct solution with no reliability discussion reads as junior. Always ask: “What happens if this runs twice?” and “What happens at 65k TPS?”
• What Visa cares about: Payment network reliability (99.999% uptime — five-nines), fraud detection accuracy, transaction throughput, and regulatory compliance (PCI-DSS, SOX). These are not background details; weave them into every answer.

---

Pattern Frequency Breakdown

Pattern	Approximate Frequency	Notes
HashMap / Design	30%	Transaction lookup, fraud pattern tables, authorization caches
Dynamic Programming	20%	Fee optimization, currency routing, knapsack-style limits
Graphs	20%	Payment network topology, merchant clustering, routing algorithms
Greedy / Arrays	15%	Batch scheduling, circular flow analysis, interval problems
Sliding Window	15%	Real-time fraud scoring windows, velocity checks

---

Problems From This Repo

Problem	Session Link	Why Visa
Top K Frequent Elements (LC 347)	[[Session-04-HashMap|Session 4: HashMap]]	Top merchant categories by transaction volume; top fraud patterns by frequency; real-time leaderboard for dispute routing
Valid Sudoku (LC 36)	[[Session-04-HashMap|Session 4: HashMap]]	Transaction constraint validation — each transaction must satisfy uniqueness rules across row/column/box analogues (merchant, BIN range, time window)
Coin Change (LC 322)	[[Session-09-DP1D|Session 9: DP 1D]]	Currency denomination optimization for ATM cash loading; minimum number of currency units to dispense a target amount
Task Scheduler (LC 621)	[[Session-07-Heap|Session 7: Heap]]	Transaction batch scheduling with rate limits — payment processors impose per-merchant TPS caps; schedule transactions to maximize throughput with cooldown periods
Network Delay Time (LC 743)	[[Session-14-AdvancedGraphs|Session 14: Advanced Graphs]]	Payment network routing latency — Dijkstra on the payment rail graph to find minimum-latency authorization path between issuing bank and acquiring bank
Number of Connected Components (LC 323)	[[Session-14-AdvancedGraphs|Session 14: Advanced Graphs]]	Merchant network cluster analysis — identify distinct merchant groups with no cross-links for risk compartmentalization
Minimum Size Subarray Sum (LC 209)	[[Session-02-SlidingWindow|Session 2: Sliding Window]]	Transaction window analysis — find the shortest time window in which cumulative transaction amount exceeds a velocity threshold
Gas Station (LC 134)	[[Session-12-Greedy|Session 12: Greedy]]	Circular transaction flow analysis — determine if a cycle of fund transfers between accounts can complete without going net-negative
Time-Based Key-Value Store (LC 981)	[[Session-03-BinarySearch|Session 3: Binary Search]]	Versioned transaction record lookup — retrieve the state of a transaction at a specific timestamp for dispute resolution and audit trails
Course Schedule (LC 207)	[[Session-08-Graphs|Session 8: Graphs]]	Compliance rule dependency ordering — regulatory rules have prerequisites; detect circular dependencies in compliance workflows before deployment

---

New Problems (Visa-Specific)

These five problems extend beyond the core session files and directly map to Visa engineering challenges. For each, understand both approaches at the level of being able to articulate the tradeoff in a payment systems context — not just the algorithmic one.

---

Problem 1: Subarray Sum Equals K (LC 560) — Medium

Link: LeetCode 560

Quick Summary: Given an integer array nums and an integer k, return the total number of subarrays whose elements sum to k. Array may contain negative numbers.

Why Visa: Fraud ring detection and chargeback pattern identification. Given a sequence of transaction amounts (which can be negative for refunds), count how many contiguous time windows have a net amount exactly equal to a target value (e.g., a known fraud ring’s round-trip amount, or a regulatory reporting threshold). The prefix sum approach handles refunds (negative values) correctly — a brute-force positive-only sliding window does not.

---

Approach 1: Brute Force — all subarray sums

// Time: O(n²)  Space: O(1)
public int subarraySumBrute(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end < nums.length; end++) {
            sum += nums[end];
            if (sum == k) count++;
        }
    }
    return count;
}

• Time: O(n²) — O(n) starting positions, O(n) extension each
• Space: O(1)
• Tradeoff: Correct and simple. Fails completely for n = 65,000 transactions per second streaming into a detection window — O(n²) is not viable in real-time. Also does not generalize to streaming data without buffering the full window.

---

Approach 2: HashMap Prefix Sum (Optimal)

// Time: O(n)  Space: O(n)
public int subarraySum(int[] nums, int k) {
    // prefixCount[s] = how many times prefix sum 's' has been seen
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);   // empty prefix has sum 0, seen once
    int count = 0;
    int prefixSum = 0;
 
    for (int num : nums) {
        prefixSum += num;
        // If prefixSum - k has been seen before, those subarrays ending here sum to k
        count += prefixCount.getOrDefault(prefixSum - k, 0);
        prefixCount.merge(prefixSum, 1, Integer::sum);
    }
    return count;
}

• Time: O(n) — single pass; HashMap operations are O(1) amortized
• Space: O(n) — at most n distinct prefix sums stored
• Key Insight: For any subarray [i+1 .. j] to sum to k, we need prefixSum[j] - prefixSum[i] = k, equivalently prefixSum[i] = prefixSum[j] - k. The HashMap counts how many prior prefix sums equal prefixSum[j] - k — each such prior position defines a valid subarray ending at j. Initializing prefixCount.put(0, 1) handles subarrays starting from index 0 (where there is no prior prefix). This is O(n) and single-pass, making it viable for streaming transaction analysis with a bounded-size sliding prefix map.

Fraud Detection Context: In production, you would not count all windows — you would return the specific window boundaries for investigation. Extend by storing (prefixSum → list of indices) instead of just the count.

---

Problem 2: Min Cost to Connect All Points (LC 1584) — Medium

Link: LeetCode 1584

Quick Summary: Given n points on a 2D plane, return the minimum cost to connect all points where the cost between two points is their Manhattan distance. This is a Minimum Spanning Tree (MST) problem on a complete graph.

Why Visa: Minimum infrastructure cost to connect payment processing nodes — given the physical locations of payment terminals, issuing bank data centers, and acquiring bank endpoints, find the minimum total cable/network infrastructure cost to ensure every node can reach every other node. MST is not covered in the core session files; this is a pattern gap worth filling.

---

Approach 1: Kruskal’s Algorithm (Sort all edges + Union-Find)

// Time: O(n² log n)  Space: O(n²)
// n² because the complete graph has n*(n-1)/2 edges
public int minCostConnectPointsKruskal(int[][] points) {
    int n = points.length;
    // Build all edges
    List<int[]> edges = new ArrayList<>(); // [cost, i, j]
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int cost = Math.abs(points[i][0] - points[j][0])
                     + Math.abs(points[i][1] - points[j][1]);
            edges.add(new int[]{cost, i, j});
        }
    }
    edges.sort(Comparator.comparingInt(e -> e[0]));
 
    // Union-Find
    int[] parent = new int[n];
    int[] rank   = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
 
    int totalCost = 0;
    int edgesUsed = 0;
    for (int[] edge : edges) {
        int cost = edge[0], u = edge[1], v = edge[2];
        int pu = find(parent, u), pv = find(parent, v);
        if (pu != pv) {
            // Union by rank
            if (rank[pu] < rank[pv])      parent[pu] = pv;
            else if (rank[pu] > rank[pv]) parent[pv] = pu;
            else { parent[pv] = pu; rank[pu]++; }
            totalCost += cost;
            edgesUsed++;
            if (edgesUsed == n - 1) break; // MST complete
        }
    }
    return totalCost;
}
 
private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

• Time: O(n² log n) — n² edges to sort; Union-Find operations are near O(1)
• Space: O(n²) — storing all edges
• Tradeoff: Conceptually clean — sort all edges greedily, add cheapest non-cycle-forming edge. Memory intensive for large n because you materialize all n² edges upfront.

---

Approach 2: Prim’s Algorithm with Min-Heap (Optimal for Dense Graphs)

// Time: O(n² log n)  Space: O(n) — no need to store all edges
public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] inMST = new boolean[n];
    // Min-heap: [cost, point_index]
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[]{0, 0}); // start from point 0 with cost 0
 
    int totalCost = 0;
    int nodesAdded = 0;
 
    while (nodesAdded < n) {
        int[] curr = heap.poll();
        int cost = curr[0], u = curr[1];
        if (inMST[u]) continue;  // already in MST — skip
        inMST[u] = true;
        totalCost += cost;
        nodesAdded++;
 
        // Add all edges from u to not-yet-included points
        for (int v = 0; v < n; v++) {
            if (!inMST[v]) {
                int edgeCost = Math.abs(points[u][0] - points[v][0])
                             + Math.abs(points[u][1] - points[v][1]);
                heap.offer(new int[]{edgeCost, v});
            }
        }
    }
    return totalCost;
}

• Time: O(n² log n) — each of the n² edges is pushed to the heap at most once; heap operations are O(log n)
• Space: O(n) — inMST array only; heap holds at most O(n²) entries in the worst case but never stores all edges simultaneously
• Key Insight: Prim’s grows the MST from a single seed node, always adding the cheapest edge from the current MST frontier to an unvisited node. The inMST[u] skip guard handles stale heap entries (a common Prim’s implementation bug). For dense graphs (like this complete graph where every pair is connected), Prim’s and Kruskal’s have the same asymptotic complexity — bring up the trade-off: Kruskal’s is better for sparse graphs (fewer edges to sort), Prim’s avoids materializing all edges at once.

Payment Network Context: In practice, Visa’s network topology is not a complete graph — payment nodes only connect to their regional hubs. For sparse graphs, use an adjacency list with Prim’s + indexed priority queue (Dijkstra-style decrease-key) to get O((V+E) log V). Worth mentioning this generalization.

---

Problem 3: Max Points on a Line (LC 149) — Hard

Link: LeetCode 149

Quick Summary: Given an array of points on a 2D plane, return the maximum number of points that lie on the same straight line.

Why Visa: Collinear transaction detection for fraud analysis. Fraudulent merchants sometimes process transactions in amounts that follow a linear pattern (e.g., amounts increasing by a fixed delta correlated with transaction time, or merchant coordinates and amounts that are suspiciously collinear). Detecting these linear patterns in transaction data is structurally identical to this problem. The GCD + slope normalization trick is the key to handling floating-point precision — a critical concern in financial systems.

---

Approach 1: Brute Force — check all triples

// Time: O(n³)  Space: O(1)
public int maxPointsBrute(int[][] points) {
    int n = points.length;
    if (n <= 2) return n;
    int maxCount = 2;
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Line defined by points[i] and points[j]
            int count = 2;
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) continue;
                // Check if points[k] is collinear with points[i] and points[j]
                // Cross product: (j-i) x (k-i) == 0 means collinear
                long cross = (long)(points[j][0] - points[i][0]) * (points[k][1] - points[i][1])
                           - (long)(points[j][1] - points[i][1]) * (points[k][0] - points[i][0]);
                if (cross == 0) count++;
            }
            maxCount = Math.max(maxCount, count);
        }
    }
    return maxCount;
}

• Time: O(n³) — three nested loops
• Space: O(1)
• Tradeoff: Correct. Cross product check avoids floating-point — an important property. But O(n³) is completely infeasible for large transaction datasets.

---

Approach 2: HashMap with GCD-Reduced Slope (Optimal)

// Time: O(n²)  Space: O(n)
public int maxPoints(int[][] points) {
    int n = points.length;
    if (n <= 2) return n;
    int maxCount = 2;
 
    for (int i = 0; i < n; i++) {
        Map<String, Integer> slopeCount = new HashMap<>();
        int duplicates = 0;
 
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
 
            if (dx == 0 && dy == 0) {
                duplicates++;   // same point as i — count it for every line through i
                continue;
            }
 
            // Normalize slope to (dy/gcd, dx/gcd) with consistent sign
            int g = gcd(Math.abs(dx), Math.abs(dy));
            dx /= g;
            dy /= g;
            // Canonical form: keep dx positive (or dy positive if dx==0)
            if (dx < 0) { dx = -dx; dy = -dy; }
            // Vertical lines: dx=0, dy=1 after normalization
 
            String key = dy + "/" + dx;
            slopeCount.merge(key, 1, Integer::sum);
        }
 
        // Best line through point i: max slope group + duplicates + 1 (point i itself)
        int localMax = duplicates + 1;
        for (int cnt : slopeCount.values()) {
            localMax = Math.max(localMax, cnt + duplicates + 1);
        }
        maxCount = Math.max(maxCount, localMax);
    }
    return maxCount;
}
 
private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

• Time: O(n²) — outer loop O(n), inner loop O(n), HashMap operations O(1)
• Space: O(n) — slope HashMap reinitialized for each anchor point i; at most n-1 entries
• Key Insight: Slope as a floating-point number (dy/dx) introduces precision errors — two lines with the same true slope may hash to different buckets due to floating-point rounding. Using the GCD-reduced integer pair (dy/gcd, dx/gcd) as the key is exact. The sign canonicalization (if (dx < 0)) ensures that slope (2, 1) and slope (-2, -1) map to the same key. Handling duplicate points separately prevents them from inflating slope counts incorrectly. In financial fraud detection, this precision discipline is mandatory — a false negative (missing a fraud pattern) due to floating-point slop is a regulatory liability.

---

Problem 4: LRU Cache (LC 146) — Medium

Link: LeetCode 146

Quick Summary: Design a data structure supporting O(1) get(key) and put(key, value), evicting the least recently used entry when capacity is exceeded.

Why Visa: Payment authorization cache. When a transaction arrives, Visa looks up the cardholder’s authorization limit, spending velocity, and fraud score — these lookups are cached to avoid hitting the issuing bank’s authorization service on every transaction (which would add 50–100ms latency, unacceptable at 65,000 TPS). LRU eviction ensures hot cardholders stay cached while inactive accounts are evicted. The design discussion around concurrent access and TTL-based expiry for authorization holds is what makes this a senior-level question at Visa.

---

Approach 1: LinkedHashMap (Concise Java)

// Time: O(1) amortized  Space: O(capacity)
public class LRUCacheLinkedHashMap {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;
 
    public LRUCacheLinkedHashMap(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCacheLinkedHashMap.this.capacity;
            }
        };
    }
 
    // Time: O(1)
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
 
    // Time: O(1)
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

• Time: O(1) — LinkedHashMap with accessOrder=true maintains LRU order internally via get
• Space: O(capacity)
• Tradeoff: Three lines of real logic. Always follow this with “I can implement the underlying HashMap + DLL if you want me to show the mechanics.”

---

Approach 2: HashMap + Doubly Linked List (Expected Implementation)

// Time: O(1) for get and put  Space: O(capacity)
public class LRUCache {
    private final int capacity;
    private final Map<Integer, DLLNode> map = new HashMap<>();
    private final DLLNode head = new DLLNode(0, 0); // LRU sentinel
    private final DLLNode tail = new DLLNode(0, 0); // MRU sentinel
 
    private static class DLLNode {
        int key, val;
        DLLNode prev, next;
        DLLNode(int key, int val) { this.key = key; this.val = val; }
    }
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
 
    // Time: O(1)
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        DLLNode node = map.get(key);
        moveToTail(node);
        return node.val;
    }
 
    // Time: O(1)
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            DLLNode node = map.get(key);
            node.val = value;
            moveToTail(node);
        } else {
            if (map.size() == capacity) {
                DLLNode lru = head.next;
                removeNode(lru);
                map.remove(lru.key);   // key stored in node for O(1) removal
            }
            DLLNode newNode = new DLLNode(key, value);
            addToTail(newNode);
            map.put(key, newNode);
        }
    }
 
    private void removeNode(DLLNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    private void addToTail(DLLNode node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }
 
    private void moveToTail(DLLNode node) {
        removeNode(node);
        addToTail(node);
    }
}

• Time: O(1) for both get and put
• Space: O(capacity)
• Key Insight: The HashMap stores node references — enabling O(1) removal from the middle of the DLL. Sentinel nodes eliminate null-check clutter on boundary removes. Storing key inside the node is the non-obvious trick that allows O(1) map cleanup when evicting the LRU (head.next) without a reverse lookup.

Visa Senior Discussion — Authorization Cache Design:

At 65,000 TPS, the authorization cache must be:

• Concurrent: A single-JVM DLL is not thread-safe. In production, use a concurrent LRU backed by a ConcurrentHashMap + segmented LRU or delegate to Redis with maxmemory-policy allkeys-lru. Lock contention on a single DLL head/tail would be the bottleneck.
• TTL-enforced: Authorization holds expire (typically 7–30 days for card pre-authorizations). LRU alone doesn’t expire them — a separate TTL field or a background sweep is needed. Discuss lazy expiry on get vs. proactive background eviction.
• Idempotent puts: If the same authorization is written twice (retry after a timeout), put should be idempotent — same key, same value, just refresh the recency. The implementation above handles this correctly.
• Consistency: For exactly-once authorization semantics, the cache cannot be the source of truth — it’s a read-through cache backed by the issuing bank’s authoritative store. Discuss write-through vs. write-back caching and how each affects consistency guarantees under failure.

---

Problem 5: Minimum Window Substring (LC 76) — Hard

Link: LeetCode 76

Quick Summary: Given strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included. If no such window exists, return "". LC 567 (Permutation in String, covered in Session 2) checks for a fixed-size window; this problem requires a variable-size minimum window.

Why Visa: Pattern matching in transaction description fields for fraud detection. A fraud analyst defines a target pattern (set of keywords or character codes that must all appear in a transaction memo or merchant category descriptor). The minimum window over a transaction log that contains all pattern elements corresponds to the tightest time window flagging the fraud — smaller windows indicate tighter coordination and higher confidence in the fraud signal.

---

Approach 1: Brute Force — all substrings

// Time: O(n² · |t|)  Space: O(|t|)
public String minWindowBrute(String s, String t) {
    if (s.length() < t.length()) return "";
    String result = "";
    int minLen = Integer.MAX_VALUE;
 
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + t.length(); j <= s.length(); j++) {
            String sub = s.substring(i, j);
            if (containsAll(sub, t) && sub.length() < minLen) {
                minLen = sub.length();
                result = sub;
            }
        }
    }
    return result;
}
 
private boolean containsAll(String window, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    for (char c : window.toCharArray()) need[c]--;
    for (int count : need) if (count > 0) return false;
    return true;
}

• Time: O(n² · |t|) — O(n²) substrings, each checked in O(|t|)
• Space: O(|t|) for the frequency array
• Tradeoff: Correct. Completely infeasible for scanning transaction logs (n can be millions of records).

---

Approach 2: Sliding Window with Character Frequency (Optimal)

// Time: O(|s| + |t|)  Space: O(1) — frequency arrays bounded by charset size (128)
public String minWindow(String s, String t) {
    if (s.isEmpty() || t.isEmpty() || s.length() < t.length()) return "";
 
    int[] need = new int[128];    // characters still needed in window
    int[] have = new int[128];    // characters currently in window
 
    for (char c : t.toCharArray()) need[c]++;
 
    int required = 0;
    for (int freq : need) if (freq > 0) required++; // distinct chars needed
 
    int left = 0;
    int formed = 0;    // distinct chars in window satisfying their required count
    int minLeft = 0, minLen = Integer.MAX_VALUE;
 
    for (int right = 0; right < s.length(); right++) {
        char rc = s.charAt(right);
        have[rc]++;
        // Did this character's count in window just reach the required count?
        if (need[rc] > 0 && have[rc] == need[rc]) formed++;
 
        // Shrink window from left while all required characters are satisfied
        while (formed == required) {
            // Update minimum window
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }
            // Remove leftmost character
            char lc = s.charAt(left++);
            have[lc]--;
            if (need[lc] > 0 && have[lc] < need[lc]) formed--;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}

• Time: O(|s| + |t|) — each character in s is added and removed from the window at most once; t scanned once to build need
• Space: O(1) — the need and have arrays are fixed size 128 (ASCII charset); independent of input size
• Key Insight: The formed counter is what makes this efficient — instead of rescanning the window to check if all characters are satisfied on every expansion, formed tracks it in O(1) as characters enter and leave. When formed == required, the window is valid and we try to shrink it from the left. When formed < required, we expand from the right. This two-pointer, expand-then-shrink rhythm is the canonical hard sliding window template. Contrast with LC 567 (Session 2): that problem uses a fixed-size window because the target is a permutation (same length as t); this problem requires a variable window because the target is a subset — the minimum-window variant is strictly harder.

Fraud Detection Context: In production, you would not return a single minimum window — you would return all minimal windows above a confidence threshold, along with their byte offsets in the transaction log for audit trail purposes. The minLeft tracking already gives you the offset; extend to collect all minimal windows by continuing after the first valid window is found.

---

Payment Domain Connections

Algorithm	Visa Product / Use Case
Prefix Sum + HashMap (Subarray Sum = K)	Fraud ring detection — count transaction windows summing to a known round-trip amount
MST (Prim’s / Kruskal’s)	Payment node network infrastructure — minimum-cost backbone connecting all processing nodes
GCD Slope Normalization (Max Points on Line)	Collinear transaction pattern detection — exact integer arithmetic for financial data
LRU Cache (HashMap + DLL)	Authorization cache — O(1) lookup with TTL enforcement and concurrent-safe design
Sliding Window (Min Window Substring)	Real-time fraud scoring — minimum transaction window containing all fraud-signal keywords
Dijkstra (Network Delay Time)	Payment routing — minimum-latency path for authorization between issuing and acquiring banks
Prefix Sum / Velocity Check	Transaction velocity limits — count transactions in rolling windows for rate enforcement
DP (Coin Change)	ATM cash denomination optimization, currency routing

---

2-Week Sprint Plan

Day	Focus
Day 1	LC 560 (Subarray Sum = K) — prefix sum + HashMap; understand fraud ring framing
Day 2	LC 209 (Min Subarray Sum) + LC 76 (Min Window Substring) — sliding window spectrum
Day 3	LC 1584 (Min Cost Connect Points) — Prim’s MST with min-heap
Day 4	LC 1584 revisited — Kruskal’s + Union-Find; compare both approaches
Day 5	LC 743 (Network Delay Time) — Dijkstra; discuss payment routing latency
Day 6	LC 146 (LRU Cache) — full HashMap + DLL implementation; concurrent access discussion
Day 7	LC 149 (Max Points on Line) — GCD slope normalization; floating-point precision discussion
Day 8	LC 322 (Coin Change) + LC 621 (Task Scheduler) — DP and greedy scheduling
Day 9	LC 347 (Top K Frequent) + LC 134 (Gas Station)
Day 10	LC 207 (Course Schedule) + LC 323 (Connected Components)
Day 11	Mock: system design — real-time fraud detection pipeline at 65,000 TPS
Day 12	Mock: system design — payment authorization cache with exactly-once semantics
Day 13	Behavioral: reliability, compliance, “what happens when your system fails” stories
Day 14	Full mock interview simulation

---

Senior-Level Talking Points

The Always-Ask Questions at Visa

For every problem, ask: “What are the consistency and failure semantics at 65,000 TPS?” and “Is this idempotent?”

• Exactly-once semantics: A payment must be authorized exactly once. If your cache put is retried (due to a timeout), it must not double-charge. Discuss idempotency keys: the first put wins; subsequent puts with the same key are no-ops or updates.
• Idempotency: Every write operation (Union-Find merge, cache insert, account dedup) must be idempotent. Running a fraud detection job twice on the same data must produce the same result. Union-Find is inherently idempotent — merging the same two sets twice is a no-op. LRU put is idempotent for the same key-value pair. Make these observations explicit.
• Consistency under partial failure: In Dijkstra for payment routing, if a node goes down mid-computation, the partial SPT is stale. Discuss how Visa uses pre-computed routing tables (offline Dijkstra) rather than online computation per transaction.

Complexity Discipline at 65,000 TPS

At 65,000 transactions per second, O(log n) vs. O(1) matters:

• A single authorization lookup: O(1) HashMap = ~50ns; O(log n) TreeMap with n=1M = ~20μs. At 65k TPS, the TreeMap adds 1.3 seconds of latency per second — you’ve broken SLA.
• Sliding window O(n) over n transactions in a 1-second fraud window: n = 65,000. Brute-force O(n²) = 4.2 billion operations per second — impossible. O(n) sliding window = 65,000 operations — fine.
• MST is computed offline (pre-network-planning) not per-transaction — clarify when an algorithm runs at design time vs. runtime. Not everything needs to be O(1) per-transaction.

Financial Data Precision

Never use floating-point for financial calculations:

• Slopes (Max Points on Line): Use GCD-reduced integer pairs, not dy/dx as a double. Two transactions at amounts (3, 6) and (1, 2) have the same slope ratio — gcd(3,3)=3 reduces both to (1,2).
• Currency amounts: Always use long (cents) or BigDecimal for monetary values in Java. Never double. A double representation of $0.10 is not exactly 0.10 — in aggregate across billions of transactions, rounding errors become material.
• Prefix sums: Use long for prefix sums over transaction amounts to avoid integer overflow at high transaction volumes.

Reliability Vocabulary

Use these terms naturally in discussions to signal payment domain depth:

• Idempotency key: A unique identifier per transaction that prevents duplicate processing.
• Exactly-once delivery: The guarantee that a transaction is processed exactly once, even if the network retries the request.
• Two-phase commit (2PC): The protocol Visa uses to atomically update both the authorization record and the cardholder balance. Discuss its performance cost (blocking protocol) and alternatives (Saga pattern).
• Circuit breaker: When an upstream service (issuing bank) is unavailable, fall back to a cached authorization decision rather than blocking the transaction. The LRU cache is a component of this circuit breaker pattern.
• PCI-DSS compliance: Any system storing, processing, or transmitting cardholder data must comply. Cache keys must never include full PAN (primary account number) — use a tokenized form. Volunteer this constraint when discussing the authorization cache design.