Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

Why graphs: data that a list cannot hold

Lesson · 8 min read · Graphs · Introduction to graphs

Arrays and trees hold one-to-one and one-to-many relationships. Many-to-many data, like which currencies convert into which, needs a graph.

The problem

Arrays, linked lists, stacks and queues store items in a line: each item has at most one item before it and one after. A tree relaxes that a little, since a node can have many children, but it still has one parent. Plenty of data has neither shape. Take currencies. Pounds convert directly into dollars and euros; dollars convert into yen, Hong Kong dollars and euros; the Singapore dollar is reached from the euro or the Hong Kong dollar. Every currency is related to several others, and the relationship runs both ways.

Suppose you store those relationships the obvious way, as a list of pairs:

pairs = [("GBP","USD"), ("GBP","EUR"), ("EUR","USD"), ("USD","JPY"), ("EUR","CHF"),
         ("USD","HKD"), ("HKD","SGD"), ("EUR","SGD"), ("JPY","HKD")]

Now answer three questions a desk might ask:

  • Which currencies can sterling be converted into directly?
  • What is the fewest number of conversions from GBP to SGD?
  • If each conversion has a cost, what is the cheapest route from GBP to SGD?

The first needs a scan of every pair. The second needs that scan once for each currency you reach, and the third needs every route compared. With nine pairs this is easy. With every listed instrument on an exchange, or every account in a payments network, a scan of all pairs at every step is the difference between a millisecond and a minute.

The solution: nodes and edges

A graph stores the items as nodes (also called vertices) and the relationships as edges between them. What makes it useful is that each node knows its own neighbours, so "where can I go from here?" costs time proportional to the answer, not to the size of the data.

  1. Step 1 / 2
    GBPEURUSDCHFJPYHKDSGD

    Seven currencies as nodes; an edge joins two currencies that convert directly.

  2. Step 2 / 2
    1112224155GBPEURUSDCHFJPYHKDSGD

    The same graph with a cost in basis points on each edge (illustrative figures).

An edge can carry a number, its weight. Here the weight is the cost of the conversion. The figures are made up for the example, but the point is general: once edges have weights, "fewest steps" and "cheapest route" are different questions.

Answering the questions on a graph

Direct conversions. Read the neighbours of GBP: USD and EUR. No scan.

Fewest conversions. Start at GBP and work outwards in rings. Everything one conversion away is a neighbour of GBP; everything two away is a neighbour of those and has not been seen yet; and so on. The first ring that contains SGD gives the answer. This is breadth-first search, and it is the subject of a whole module later in the chapter.

Fewest conversions from GBP. The number above each node is how many conversions it takes to reach it.

  1. Step 1 / 3
    GBP0EURUSDCHFJPYHKDSGD
    ring0reached1

    Start at GBP: zero conversions.

  2. Step 2 / 3
    GBP0EUR1USD1CHFJPYHKDSGD
    ring1reached3

    Ring 1: EUR, USD are reached in 1 conversion. Each was found by looking only at the neighbours of the previous ring.

  3. Step 3 / 3
    GBP0EUR1USD1CHF2JPY2HKD2SGD2
    ring2reached7

    Ring 2: CHF, SGD, HKD, JPY are reached in 2 conversions. Each was found by looking only at the neighbours of the previous ring. Nothing new can be reached, so every currency now has its fewest-conversions count.

reached in this ringreached earlieredge that first reached a node

The cheapest route. The fewest-conversions route is GBP → EUR → SGD, two conversions costing 1 + 15 = 16. The route GBP → USD → HKD → SGD takes three conversions but costs 1 + 2 + 4 = 7. Rings cannot see this, because they count edges rather than add weights. Dijkstra's algorithm, which settles the cheapest node first instead of the nearest ring, is the tool for it.

1112224155GBPEURUSDCHFJPYHKDSGD
Dashed: the fewest conversions (cost 16). Solid: the cheapest route (cost 7).

Most graph interview problems are one of these three questions in disguise: who is connected to whom, how few steps does it take, and what is the cheapest way. Naming the nodes and the edges is usually the hard part; the algorithm follows from the question.

What this chapter covers

The chapter builds the tools in the order you need them: how to store a graph in memory, how to visit every node, how to do the same on a grid, how to find cycles and orderings, how to compute shortest paths with and without weights, how to keep track of groups as edges arrive, and how to push the most flow through a network. The last five modules are patterns: the families of interview problems those tools solve, with the signals that tell you which tool a problem is asking for.