Real PayPal Interview Experience

// Example:
//    [2]
//   [3,4]
//  [6,5,7]
// [4,1,8,3]
// Min path: 2 → 3 → 5 → 1 = 11

function minimumTotal(triangle) {
  const n = triangle.length;
  
  // Start from the BOTTOM and work up
  // dp[i] represents the min path sum from row i to bottom
  const dp = [...triangle[n - 1]]; // Start with last row
  
  // Work from second-to-last row upward
  for (let row = n - 2; row >= 0; row--) {
    for (let col = 0; col <= row; col++) {
      // At each cell, choose the smaller path from below
      dp[col] = triangle[row][col] + Math.min(dp[col], dp[col + 1]);
    }
  }
  
  return dp[0]; // Min path sum from top
}

// Test:
console.log(minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]])); // 11

// Time: O(n²) where n = number of rows
// Space: O(n) — single array reused bottom-up

// WHY BOTTOM-UP?
// Top-down requires tracking ALL paths (exponential without DP).
// Bottom-up: at each cell, the optimal choice from below is already computed.
// When we reach dp[0], it contains the global minimum.

• Bottom-up is cleaner: No recursion, no memoization table, O(n) space
• "Adjacent" constraint: From index i, can only go to index i or i+1 in next row
• In-place option: Can modify triangle directly for O(1) extra space (but mention it as a trade-off)
• Edge case: Single-element triangle → return that element

class MinStack {
  constructor() {
    this.stack = [];    // Main stack: stores values
    this.minStack = []; // Auxiliary stack: stores minimums
  }
  
  push(val) {
    this.stack.push(val);
    
    // Push to minStack if it's empty or val <= current min
    // Use <= (not <) to handle duplicate minimums
    if (this.minStack.length === 0 || val <= this.getMin()) {
      this.minStack.push(val);
    }
  }
  
  pop() {
    const val = this.stack.pop();
    
    // If popped value is the current min, pop from minStack too
    if (val === this.getMin()) {
      this.minStack.pop();
    }
    
    return val;
  }
  
  top() {
    return this.stack[this.stack.length - 1];
  }
  
  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

// Test:
const ms = new MinStack();
ms.push(-2);
ms.push(0);
ms.push(-3);
console.log(ms.getMin()); // -3
ms.pop();
console.log(ms.top());    // 0
console.log(ms.getMin()); // -2

// All operations: O(1) time, O(n) space


// === ALTERNATIVE: Single Stack (Space Optimized) ===
// Store encoded values: push (2*val - prevMin) when new min found
class MinStackOptimized {
  constructor() {
    this.stack = [];
    this.min = Infinity;
  }
  
  push(val) {
    if (this.stack.length === 0) {
      this.stack.push(0);
      this.min = val;
    } else {
      // Store difference from current min
      this.stack.push(val - this.min);
      if (val < this.min) this.min = val;
    }
  }
  
  pop() {
    const top = this.stack.pop();
    if (top < 0) {
      // This was a min-setter; restore previous min
      this.min = this.min - top;
    }
  }
  
  top() {
    const top = this.stack[this.stack.length - 1];
    return top < 0 ? this.min : this.min + top;
  }
  
  getMin() {
    return this.min;
  }
}

• <= not <: Must use <= when pushing to minStack to handle duplicate minimums
• Two approaches: Dual stack (simple, O(n) extra) vs single stack with encoding (O(1) extra but tricky)
• Trade-off: Dual stack is easier to debug; single stack is space-optimal but harder to maintain

function topologicalSort(numCourses, prerequisites) {
  // Build adjacency list
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }
  
  const visited = new Set();    // Fully processed
  const visiting = new Set();   // Currently in DFS path (cycle detection)
  const result = [];
  
  function dfs(node) {
    // Cycle detected — currently being explored
    if (visiting.has(node)) return false;
    // Already processed — skip
    if (visited.has(node)) return true;
    
    visiting.add(node); // Mark as "in progress"
    
    // Visit all neighbors
    for (const neighbor of graph[node]) {
      if (!dfs(neighbor)) return false; // Cycle propagates up
    }
    
    visiting.delete(node); // Remove from current path
    visited.add(node);     // Mark as fully processed
    result.push(node);     // Add to result (post-order)
    
    return true;
  }
  
  // Start DFS from every unvisited node
  for (let i = 0; i < numCourses; i++) {
    if (!visited.has(i)) {
      if (!dfs(i)) return []; // Cycle exists — impossible
    }
  }
  
  return result.reverse(); // Reverse post-order = topological order
}

// Test:
console.log(topologicalSort(4, [[1,0],[2,0],[3,1],[3,2]]));
// One valid output: [0, 1, 2, 3] or [0, 2, 1, 3]

// Time: O(V + E) — visit each vertex and edge once
// Space: O(V + E) — graph storage + recursion stack

• DFS vs BFS (Kahn's): DFS uses recursion + reverse post-order. BFS uses in-degree tracking + queue. Both O(V+E).
• Cycle detection: "visiting" set catches back edges — if we revisit a node still being explored, it's a cycle
• Why reverse post-order? Node is added AFTER all its dependencies are processed — reverse gives correct order
• Real-world: Package dependency resolution (npm), build systems (webpack), task scheduling

┌───────────────────────────────────────────────────────────────────┐
│ PAYMENT GATEWAY SYSTEM ARCHITECTURE                               │
├───────────────────────────────────────────────────────────────────┤
│                                                                   │
│  ┌──────────┐    ┌───────────────┐    ┌────────────────────┐    │
│  │ Merchant │───▸│ API Gateway   │───▸│ Payment Service    │    │
│  │ (Client) │    │ (Auth + Rate  │    │ (Orchestrator)     │    │
│  └──────────┘    │  Limiting)    │    └─────────┬──────────┘    │
│                  └───────────────┘              │               │
│                                                 │               │
│                    ┌────────────────────────────┼────────┐      │
│                    │                            ▼        │      │
│  ┌──────────────┐ │  ┌────────────┐  ┌──────────────┐  │      │
│  │ Fraud Engine │◀┼──│ Risk       │  │ Processor    │  │      │
│  │ (ML-based)   │ │  │ Assessment │  │ Router       │──┼──┐   │
│  └──────────────┘ │  └────────────┘  └──────────────┘  │  │   │
│                    │                                     │  │   │
│                    └─────────────────────────────────────┘  │   │
│                                                             │   │
│  ┌──────────────┐  ┌──────────────┐  ┌──────────────────┐ │   │
│  │ Visa/MC      │  │ Bank API     │  │ PayPal Wallet    │◀┘   │
│  │ Network      │  │ (NEFT/UPI)   │  │ (Internal)       │     │
│  └──────────────┘  └──────────────┘  └──────────────────┘     │
│                                                                 │
│  ┌──────────────────────────────────────────────────────────┐  │
│  │ Ledger Service (append-only, double-entry bookkeeping)    │  │
│  └──────────────────────────────────────────────────────────┘  │
│                                                                 │
│  ┌──────────────┐  ┌──────────────┐  ┌──────────────────┐    │
│  │ Notification │  │ Webhook      │  │ Retry/DLQ        │    │
│  │ Service      │  │ Dispatcher   │  │ (Dead Letter Q)  │    │
│  └──────────────┘  └──────────────┘  └──────────────────┘    │
└───────────────────────────────────────────────────────────────────┘

// Happy path payment flow:
// 
// 1. Merchant → API Gateway (authenticate + rate limit)
// 2. API Gateway → Payment Service (create payment intent)
// 3. Payment Service → Fraud Engine (risk score)
//    - If high risk → decline or require 3DS verification
//    - If low risk → proceed
// 4. Payment Service → Processor Router (select processor)
//    - Routes to: Visa, Mastercard, UPI, or PayPal wallet
// 5. Processor → Bank/Network (actual charge)
// 6. Response → Payment Service (success/failure)
// 7. Payment Service → Ledger (record transaction)
// 8. Payment Service → Webhook Dispatcher (notify merchant)
// 9. Return result to Merchant

// States of a payment:
const PaymentStates = {
  CREATED: 'created',       // Intent created
  PROCESSING: 'processing', // Sent to processor
  AUTHORIZED: 'authorized', // Funds reserved
  CAPTURED: 'captured',     // Funds transferred
  DECLINED: 'declined',     // Rejected by bank/fraud
  REFUNDED: 'refunded',     // Money returned
  FAILED: 'failed',         // System error
};

// State machine transitions:
// created → processing → authorized → captured
//                      → declined
//                      → failed
// captured → refunded

// IDEMPOTENCY — The most critical concept in payments
// 
// Problem: Network timeout. Merchant retries. Double charge.
// Solution: Idempotency key — same key always returns same result.

// How it works:
// 1. Merchant includes unique Idempotency-Key header in request
// 2. Server checks: "Have I seen this key before?"
//    - Yes → return stored result (don't process again)
//    - No → process and store result keyed by idempotency key

// Implementation concept:
async function processPayment(request) {
  const idempotencyKey = request.headers['Idempotency-Key'];
  
  // Check if we've already processed this
  const existing = await idempotencyStore.get(idempotencyKey);
  if (existing) {
    return existing.response; // Return cached result
  }
  
  // Lock to prevent concurrent duplicate processing
  const lock = await acquireLock(idempotencyKey, { ttl: 30000 });
  if (!lock) {
    return { status: 409, body: 'Request already in progress' };
  }
  
  try {
    // Process the payment
    const result = await chargePaymentProcessor(request.body);
    
    // Store result for future duplicate requests
    await idempotencyStore.set(idempotencyKey, {
      response: result,
      expiry: Date.now() + 24 * 60 * 60 * 1000 // 24h TTL
    });
    
    return result;
  } finally {
    await releaseLock(idempotencyKey);
  }
}

// KEY DESIGN DECISIONS:
// • Idempotency key TTL: 24 hours (merchant should generate unique key per intent)
// • Lock mechanism: Redis SETNX with TTL (prevents concurrent duplicates)
// • Storage: Redis for hot lookups + Postgres for persistence

// DOUBLE-ENTRY BOOKKEEPING
// Every transaction creates TWO entries that must balance:
//
// Payment of ₹1000 from Customer to Merchant:
// ┌──────────────┬─────────┬─────────┐
// │ Account      │ Debit   │ Credit  │
// ├──────────────┼─────────┼─────────┤
// │ Customer     │ ₹1000   │         │  (money leaves customer)
// │ Merchant     │         │ ₹1000   │  (money enters merchant)
// └──────────────┴─────────┴─────────┘
// 
// Sum of debits MUST equal sum of credits (always balanced)
//
// WHY APPEND-ONLY?
// • Never update or delete ledger entries (audit trail)
// • Corrections are made by adding reversal entries
// • Enables point-in-time balance reconstruction
// • Regulatory compliance (PCI, SOX)
//
// CONSISTENCY GUARANTEES:
// • Write to ledger and payment table in same database transaction
// • If ledger write fails → payment fails (atomic)
// • Eventual consistency for cross-region replication (acceptable for reads)

// Refund example — add reversal entries (don't delete original):
// ┌──────────────┬─────────┬─────────┐
// │ Account      │ Debit   │ Credit  │
// ├──────────────┼─────────┼─────────┤
// │ Merchant     │ ₹1000   │         │  (money leaves merchant)
// │ Customer     │         │ ₹1000   │  (money returns to customer)
// └──────────────┴─────────┴─────────┘

RELIABILITY:
─────────────
• Circuit breaker on processor calls (if Visa is down, route to fallback)
• Retry with exponential backoff for transient failures
• Dead Letter Queue for failed webhooks (retry up to 5x over 24h)
• Saga pattern for distributed transactions (compensating actions for rollback)
• Health checks on all downstream services
• Multi-region deployment (active-passive for disaster recovery)

SECURITY:
─────────
• PCI DSS compliance: card data never touches our servers
  → Use tokenization (Stripe/PayPal vault handles raw card numbers)
• TLS 1.3 for all communication
• API keys + OAuth 2.0 for merchant authentication
• Rate limiting per merchant (prevent abuse)
• 3D Secure for high-risk transactions (OTP verification)
• Encryption at rest for all PII data
• Audit logging for every state change

TRADE-OFFS TO DISCUSS:
──────────────────────
• Consistency vs Availability: Payment writes = strong consistency (CP).
  Read replicas = eventual consistency (AP) acceptable for dashboards.
  
• Latency vs Security: 3DS adds 5-10s friction but reduces fraud 80%.
  Use risk scoring to skip 3DS for trusted users (adaptive auth).
  
• Cost vs Reliability: Multi-processor routing costs more but provides
  failover. Route 80% to cheapest, 20% to backup for warmth.

function searchInsert(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  // When loop exits, left = insertion point
  return left;
}

// Test:
console.log(searchInsert([1, 3, 5, 6], 5)); // 2 (found)
console.log(searchInsert([1, 3, 5, 6], 2)); // 1 (insert between 1 and 3)
console.log(searchInsert([1, 3, 5, 6], 7)); // 4 (insert at end)
console.log(searchInsert([1, 3, 5, 6], 0)); // 0 (insert at beginning)

// Time: O(log n)
// Space: O(1)

// WHY left is the answer:
// When target is NOT found, the loop narrows to where target should be.
// left ends up at the first index where nums[left] > target.

// === VIRTUAL DOM ===
// A lightweight JS object tree mirroring the real DOM.
// React maintains TWO trees: current (on screen) and next (after state change).
// Diffing compares them and produces minimal DOM operations.

// Virtual DOM node structure:
// { type: 'div', props: { className: 'card' }, children: [...] }


// === RECONCILIATION: React's Heuristic Assumptions ===
// 
// Full tree diff is O(n³) — too slow for UI (60fps = 16ms budget).
// React uses TWO heuristics to achieve O(n):
//
// 1. Different TYPE → destroy old tree, build new tree from scratch
//    (e.g., 
 →  = full subtree rebuild)
//
// 2. Same TYPE → keep DOM node, update changed attributes only
//    Then recursively diff children.
//
// 3. KEYS in lists → identify which items moved/added/removed
//    Without keys: [A,B,C] → [B,A,C] = update all three
//    With keys: [A,B,C] → [B,A,C] = just reorder (move operations)


// === PSEUDOCODE: DIFFING ALGORITHM ===

function diff(oldNode, newNode) {
  const patches = [];
  
  // Case 1: Node removed
  if (!newNode) {
    patches.push({ type: 'REMOVE' });
    return patches;
  }
  
  // Case 2: Node added
  if (!oldNode) {
    patches.push({ type: 'CREATE', node: newNode });
    return patches;
  }
  
  // Case 3: Different type → replace entire subtree
  if (oldNode.type !== newNode.type) {
    patches.push({ type: 'REPLACE', node: newNode });
    return patches;
  }
  
  // Case 4: Same type → diff props + diff children
  if (oldNode.type === newNode.type) {
    // Diff props (attributes)
    const propPatches = diffProps(oldNode.props, newNode.props);
    if (propPatches.length > 0) {
      patches.push({ type: 'UPDATE_PROPS', patches: propPatches });
    }
    
    // Diff children (recursive)
    const childPatches = diffChildren(oldNode.children, newNode.children);
    patches.push(...childPatches);
  }
  
  return patches;
}

function diffProps(oldProps, newProps) {
  const patches = [];
  
  // Find changed or new props
  for (const key in newProps) {
    if (oldProps[key] !== newProps[key]) {
      patches.push({ type: 'SET_PROP', key, value: newProps[key] });
    }
  }
  
  // Find removed props
  for (const key in oldProps) {
    if (!(key in newProps)) {
      patches.push({ type: 'REMOVE_PROP', key });
    }
  }
  
  return patches;
}

function diffChildren(oldChildren, newChildren) {
  const patches = [];
  
  // If children have keys → use key-based reconciliation
  if (childrenHaveKeys(newChildren)) {
    return diffKeyedChildren(oldChildren, newChildren);
  }
  
  // Without keys: compare index-by-index
  const maxLen = Math.max(oldChildren.length, newChildren.length);
  for (let i = 0; i < maxLen; i++) {
    const childPatch = diff(oldChildren[i], newChildren[i]);
    patches.push({ index: i, patches: childPatch });
  }
  
  return patches;
}

function diffKeyedChildren(oldChildren, newChildren) {
  // Build map: key → old child
  const oldMap = new Map();
  oldChildren.forEach((child, i) => oldMap.set(child.key, { child, index: i }));
  
  const patches = [];
  
  newChildren.forEach((newChild, newIndex) => {
    const oldEntry = oldMap.get(newChild.key);
    
    if (!oldEntry) {
      // New item — INSERT
      patches.push({ type: 'INSERT', index: newIndex, node: newChild });
    } else {
      // Existing item — MOVE (if index changed) + UPDATE (if content changed)
      if (oldEntry.index !== newIndex) {
        patches.push({ type: 'MOVE', from: oldEntry.index, to: newIndex });
      }
      // Recursively diff the node content
      const contentPatch = diff(oldEntry.child, newChild);
      if (contentPatch.length > 0) {
        patches.push({ type: 'UPDATE', index: newIndex, patches: contentPatch });
      }
      oldMap.delete(newChild.key);
    }
  });
  
  // Remaining in oldMap = removed items
  for (const [key, { index }] of oldMap) {
    patches.push({ type: 'REMOVE', index });
  }
  
  return patches;
}


// === WHY KEYS MATTER ===
// Without keys: [A, B, C] → [C, A, B]
//   React sees: index 0 changed (A→C), index 1 changed (B→A), index 2 changed (C→B)
//   = 3 DOM updates (content replacement)
//
// With keys: [A, B, C] → [C, A, B]
//   React sees: C moved to front, A and B shifted
//   = 2 DOM moves (no content changes)
//
// For 1000 items: keys = 2 moves vs no-keys = 1000 updates

• O(n³) → O(n): React's heuristics (type change = rebuild, same type = patch) reduce complexity
• Fiber architecture: React 16+ uses Fiber to make reconciliation interruptible (time-slicing)
• Batching: Multiple setState calls are batched into one reconciliation pass
• Keys: Stable, unique identifiers that let React track identity across renders (not array index!)

import { useState, useEffect, useCallback } from 'react';

const CURRENCIES = ['USD', 'EUR', 'GBP', 'INR', 'JPY', 'AUD', 'CAD'];

function CurrencyConverter() {
  const [amount, setAmount] = useState(1);
  const [fromCurrency, setFromCurrency] = useState('USD');
  const [toCurrency, setToCurrency] = useState('INR');
  const [rates, setRates] = useState({});
  const [loading, setLoading] = useState(false);
  const [error, setError] = useState(null);
  
  // Fetch exchange rates when "from" currency changes
  useEffect(() => {
    let cancelled = false;
    
    async function fetchRates() {
      setLoading(true);
      setError(null);
      
      try {
        const response = await fetch(
          `https://api.exchangerate-api.com/v4/latest/${fromCurrency}`
        );
        
        if (!response.ok) throw new Error('Failed to fetch rates');
        
        const data = await response.json();
        
        if (!cancelled) {
          setRates(data.rates);
        }
      } catch (err) {
        if (!cancelled) {
          setError(err.message);
        }
      } finally {
        if (!cancelled) {
          setLoading(false);
        }
      }
    }
    
    fetchRates();
    
    return () => { cancelled = true; };
  }, [fromCurrency]);
  
  // Computed converted amount
  const convertedAmount = rates[toCurrency]
    ? (amount * rates[toCurrency]).toFixed(2)
    : '...';
  
  // Swap currencies
  const handleSwap = useCallback(() => {
    setFromCurrency(toCurrency);
    setToCurrency(fromCurrency);
  }, [fromCurrency, toCurrency]);
  
  return (
    <div className="converter">
      <h2>Currency Converter</h2>
      
      {error && <div className="error">{error}</div>}
      
      <div className="converter-row">
        <div className="input-group">
          <label htmlFor="amount">Amount</label>
          <input
            id="amount"
            type="number"
            value={amount}
            onChange={(e) => setAmount(Math.max(0, e.target.value))}
            min="0"
            step="0.01"
          />
        </div>
        
        <div className="input-group">
          <label htmlFor="from">From</label>
          <select
            id="from"
            value={fromCurrency}
            onChange={(e) => setFromCurrency(e.target.value)}
          >
            {CURRENCIES.map(c => (
              <option key={c} value={c}>{c}</option>
            ))}
          </select>
        </div>
        
        <button onClick={handleSwap} className="swap-btn" aria-label="Swap currencies">
          ⇄
        </button>
        
        <div className="input-group">
          <label htmlFor="to">To</label>
          <select
            id="to"
            value={toCurrency}
            onChange={(e) => setToCurrency(e.target.value)}
          >
            {CURRENCIES.map(c => (
              <option key={c} value={c}>{c}</option>
            ))}
          </select>
        </div>
      </div>
      
      <div className="result">
        {loading ? (
          <p>Fetching rates...</p>
        ) : (
          <p>
            <strong>{amount} {fromCurrency}</strong> ={' '}
            <strong>{convertedAmount} {toCurrency}</strong>
          </p>
        )}
        {rates[toCurrency] && (
          <p className="rate-info">
            1 {fromCurrency} = {rates[toCurrency].toFixed(4)} {toCurrency}
          </p>
        )}
      </div>
    </div>
  );
}

• Real-time updates: Conversion recalculates on EVERY input change (no submit button needed)
• Derived state: convertedAmount is COMPUTED, not stored — avoids sync bugs
• Effect cleanup: Cancelled flag prevents state update on unmounted component
• Swap: Simple but shows attention to UX
• Error + loading states: Always handle API failure gracefully
• Accessibility: Labels linked to inputs via htmlFor/id, aria-label on swap button