Stitch Fix Engineering Blog

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Low-Level Design Practice · 11 minSplitwise (expense sharing)Shared expenses, balances and simplifying debts: equal, exact and percentage splits behind one interface, and a simple settle-up algorithm.Read hereClose

  The problem

  Friends add shared expenses ("I paid 60 for dinner, split among four of us") and the app tracks who owes whom. Users can see balances and settle up.

  Entities

  100%

  Figure SDA-LLD-10-1 · Expense sharing classes · © forcsguy.com

  An Expense records who paid and a list of Split shares (who owes how much). Balances are derived from expenses, so the history stays auditable.

  Splits as a strategy

  type Share = { user: string; cents: number };
  interface SplitStrategy { split(totalCents: number, who: string[], extra?: number[]): Share[] }
  
  const equal: SplitStrategy = {
    split(total, who) {
      const base = Math.floor(total / who.length), rest = total - base * who.length;
      return who.map((u, i) => ({ user: u, cents: base + (i < rest ? 1 : 0) }));  // leftovers spread one cent each
    },
  };
  const percent: SplitStrategy = {
    split(total, who, pct = []) {
      if (pct.reduce((a, b) => a + b, 0) !== 100) throw new Error("percentages must add to 100");
      const shares = who.map((u, i) => ({ user: u, cents: Math.floor(total * pct[i] / 100) }));
      shares[0].cents += total - shares.reduce((a, s) => a + s.cents, 0);          // fix rounding
      return shares;
    },
  };
  

  Always validate that the shares sum to the total; decide a fixed rule for leftover cents.

  Net balances and settling up

  100%

  Figure SDA-LLD-10-2 · Settle-up idea · © forcsguy.com

  function settle(net: Map<string, number>) {          // positive = is owed, negative = owes
    const debtors = [...net].filter(([, v]) => v < 0).sort((a, b) => a[1] - b[1]);
    const creditors = [...net].filter(([, v]) => v > 0).sort((a, b) => b[1] - a[1]);
    const pays: { from: string; to: string; cents: number }[] = [];
    let i = 0, j = 0;
    while (i < debtors.length && j < creditors.length) {
      const amt = Math.min(-debtors[i][1], creditors[j][1]);
      pays.push({ from: debtors[i][0], to: creditors[j][0], cents: amt });
      debtors[i][1] += amt; creditors[j][1] -= amt;
      if (debtors[i][1] === 0) i++; if (creditors[j][1] === 0) j++;
    }
    return pays;   // at most (people - 1) payments
  }
  

  This greedy approach is simple and gives at most n - 1 payments. Finding the true minimum number of payments is a harder problem; say so in an interview and explain why greedy is acceptable.

  Design notes

  • Integer money everywhere; convert to a display string at the edge.
  • Edits and deletes: store expenses, recompute balances; never keep only running totals.
  • Currencies: store the currency on each expense; convert at a recorded rate when settling.
  • Concurrency: two people adding expenses at once is fine as long as each expense is an append; balances are recomputed.
  • Extensions: recurring expenses, reminders, groups with different default splits.

  Real-world reading

  Related reading

  • Nubank BlogNubank engineers · NubankBlogs
  • Kraken BlogKraken engineers · KrakenBlogs
  • Capital One BlogCapital One engineers · Capital OneBlogs
  • Monzo: How Peer-To-Peer Payments WorkMonzo engineers · MonzoBlogs

  Show 6 moreShow fewer

  • Optimizing Payments with Machine Learning at DropboxDropbox engineers · DropboxCase Studies
  • Architectures of Finance, Banking, and Payment SystemsRedhat engineers · RedhatCase Studies
  • Payment Transaction Management in Microservices at MercariMercari engineers · MercariCase Studies
  • Billing and Payment Platform at GrammarlyGrammarly engineers · GrammarlyCase Studies
  • Architecture of NubankInfoQ engineers · InfoQCase Studies
  • Stitch Fix Engineering BlogStitch Fix engineers · Stitch FixBlogs

  Open this lesson with its quiz and exercise