Trees & Graphs

Once your directory walk runs, Datadog interviewers usually change the tree. First, a path might arrive as a loose string from a config file that has to resolve to a node before you walk it. Then the directory turns shallow and extremely wide, and soon the list of paths you were building no longer fits in memory. The basic walk is in Recursion & Pattern Matching, and these problems pick up where it ends.

Two of the problems leave the filesystem behind but use the same skill. An APM trace reaches the backend as flat span records that point at their parents, so you rebuild the tree before you can score anything. A service map is a weighted graph. To find the quickest route between two hosts, you run Dijkstra and save a parent pointer on every update. In all of them, the decision that matters most comes early, and it's about where you keep the work you haven't done yet.

Why hierarchies keep coming back

Datadog's reported coding problems use hierarchies a lot because the product is full of them. A host's directory tree, a trace's spans and a service map's call graph are all structures the Agent or the backend reads every day. The base version is easy on purpose. The difference between candidates is how the code holds up once the input gets harder, such as a path that may not exist or a queue with millions of entries in it.

The Datadog angle

Each problem here maps to something Datadog runs. The Agent resolves configured paths and crawls /var/log on hosts where one folder holds years of rotated files. The trace view rebuilds span trees from parent ids before it can draw a flame graph, and the service map is a latency-weighted graph of which service calls which. All of that code runs on a customer's host or inside a busy backend, where a walk that holds every path at once is the failure that matters. So the follow-ups ask about memory and depth long before anyone wants a cleverer algorithm.

Where the pending work lives

Every problem below is a traversal, and the choice that matters is the container holding the work you have not done yet. The call stack is fine for ten levels and falls over at ten thousand. An explicit stack survives any depth. A queue drains one level before it starts the next, which suits a shallow tree with a huge fan-out. A generator keeps one root-to-leaf path in memory and hands results back as it finds them, and the min-heap in Dijkstra is the same idea ordered by distance.

deep tree, small fan-out     -> explicit stack of (node, path)
shallow tree, huge fan-out   -> queue, drained one level at a time
result too big to return     -> generator, one root-to-leaf path held
weighted graph, fastest path -> min-heap keyed by time so far

Asked at Datadog

Five problems, ordered by how often each shape comes up. The path-string size walk leads, followed by the wide directory and the streaming delete order. The span tree and the service map close the set. Work each one in the editor before you open the walkthrough.

1

Directory Size by Path: Parse It, Then Walk It

MediumSignature problem

Problem

The Datadog Agent holds a snapshot of a host's directory tree, and a check configured with a path string wants the total bytes under that path, the number du -sh /var/log would print. The path comes out of a config file, so expect it written loosely.

A node is either a file, {"type": "file", "size": }, or a directory, {"type": "dir", "children": {: , ...}}. file_system is the root directory.

Write total_size(file_system, path). Split path on / and resolve the names from the root. Empty pieces from a leading, trailing or doubled slash are ignored, so "/var/log/", "var/log" and "//var//log" name the same directory and "/" names the root itself. Names are case-sensitive.

When the path resolves to a directory, return the total size of every file at any depth below it, with 0 for an empty directory. A path that resolves to a file returns that file's size. A missing name, or a step into a file partway along, means the path does not exist. Return -1.

Inputfile_system = {"type": "dir", "children": {"var": {"type": "dir", "children": {"log": {"type": "dir", "children": {"dmesg": {"type": "file", "size": 1783894}, "wifi.log": {"type": "file", "size": 924818}}}}}}} path = "var/"Output2708712

The missing leading slash and the trailing slash add no names, so the path resolves to var, and its two files sum to 1783894 + 924818 = 2708712.

Inputfile_system = {"type": "dir", "children": {"var": {"type": "dir", "children": {"log": {"type": "dir", "children": {"dmesg": {"type": "file", "size": 1783894}, "wifi.log": {"type": "file", "size": 924818}}}}}}} path = "/var/log/wifi.log/old"Output-1

wifi.log is a file, so nothing named old can sit beneath it and the path does not exist.

How this uses the pattern

Two phases. Turn the path into a list of names by splitting on the slash and dropping the empty pieces, then walk down from the root one name at a time, looking each one up in the current directory's children. Sum every file under the node you land on with the same walk you would use for a plain directory size. A file is its own total.

Directory Size by Path: Parse It, Then Walk It

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (10)

Need a hint? (3 available)

The Datadog angle

A Datadog Agent check gets its paths as strings out of a YAML file, so before it can report anything like du -sh /var/log it has to turn that string into a node. The size walk is the directory problem Datadog asks most, and the path parameter is its most reported follow-up. One candidate ran out of screen time on the parse, which makes it the half to rehearse. Before writing code, say out loud how you treat a leading slash, a trailing slash, a path that names a file, and a path that does not exist. Pick the sentinel for that last case early. A return of 0 would look identical to an empty directory.

Take it further

The path parameter tends to arrive after the plain directory-size walk, worded something like "add a path parameter and return only the size underneath the specified path", sometimes with an explicit ask to check that the path exists first. Once it works, the base walk's follow-ups apply to the subtree. Keep the sum on an explicit stack so a deep tree cannot overflow the call stack, and expect the wide-directory and memory questions next. If they hand you many paths for one tree, a single pass that records every node's size under its normalized path turns each lookup into a dictionary get. A senior-level follow-up streams file sizes from a generator so a huge subtree never sits in memory.

Show solution & walkthrough

2

Million-Wide Directory: Walk It Without Recursion

MediumFrequently asked

Problem

The Datadog Agent crawls a host's log directories to find files worth tailing. On this host the tree is shallow, ten levels at most, but a single directory can hold millions of rotated files. Use the same nested-dictionary model as the problems above. A file is {"type": "file", "size": } and a directory is {"type": "dir", "children": {: , ...}}.

Write level_order_paths(node, path) without recursion. path is the path of node itself, and a child's path is its parent's path, a /, then the child's name.

Return the paths at or below node grouped by level, as a list of lists. The first list is [path], the second holds every path one level down, the third every path two levels down, and so on until the deepest level. Inside a level, keep paths grouped by parent in the order those parents appear one level up, and list a directory's children in ascending name order by plain string comparison, so syslog.10 comes before syslog.2 and README comes before aux.

Inputnode = {"type": "dir", "children": {"nginx": {"type": "dir", "children": {"error.log": {"type": "file", "size": 3}, "access.log": {"type": "file", "size": 8}}}, "syslog": {"type": "file", "size": 5}, "app": {"type": "dir", "children": {"app.log": {"type": "file", "size": 2}}}}} path = "/var/log"Output[["/var/log"], ["/var/log/app", "/var/log/nginx", "/var/log/syslog"], ["/var/log/app/app.log", "/var/log/nginx/access.log", "/var/log/nginx/error.log"]]

The three entries directly under /var/log form level one in name order, and the files inside app and nginx form level two.

Inputnode = {"type": "file", "size": 10} path = "/var/log/syslog"Output[["/var/log/syslog"]]

A lone file has nothing below it, so the only level holds its own path.

How this uses the pattern

Keep a first-in, first-out queue of (node, path) pairs, seeded with the starting node. At the top of each round, the queue holds exactly one level, so read its length, pop that many entries into a fresh list, and enqueue each directory's children in sorted name order as you go. When the round ends, the list you built is a finished level and the queue holds the next one.

Million-Wide Directory: Walk It Without Recursion

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (7)

Need a hint? (3 available)

The Datadog angle

Ten levels deep with millions of rotated files in one folder is what the Agent finds in /var/log on a busy host. In one screen the candidate wrote a recursive DFS, was asked to rework it so it would stop running out of memory, and then the interviewer changed the tree to shallow and very wide. Ten levels means ten frames, which the call stack handles easily. Memory runs out when millions of paths sit in one list, so say that before you type. Then explain why a queue suits this tree: it finishes the top levels first and keeps a single frontier you can stream or spill to disk.

Take it further

The follow-ups start before this problem does: a recursive walk comes first, then the push to "update the code to avoid OOM", then the changed tree that makes a queue the better fit. Once the level walk runs, expect "you cannot hand back millions of paths in one list", which turns the function into a generator that yields each path as it leaves the queue. The ladder can go one rung further. When the pending work itself gets too large, save it to disk, using a queue with a memory cap whose overflow is appended to a file and read back in the same order. Describe the disk queue and sketch it, since few interviewers will expect it to run.

Show solution & walkthrough

3

Streaming Walk: Yield Paths Instead of Collecting Them

MediumCommonly asked

Problem

A cleanup job on a host has to clear a date-partitioned log archive, and the filesystem API it gets deletes a file or an empty directory and nothing else. A big archive holds more paths than memory can, so the walk has to hand paths over one at a time, each one safe to delete the moment it arrives.

The archive is regular, so it comes as a layout instead of a nested dictionary. layout[d] lists the entries of every directory at depth d, where root sits at depth 0 and any directory deeper than the layout is empty. An entry ending in / is a subdirectory, named without the slash; any other entry is a file. A child's path is its parent's path, a /, then the child's name.

Write first_k_deletes(layout, root, k). Walk in delete order: inside a directory, take entries in listed order, emit a file's path when you reach it, finish a subdirectory completely before moving on, and emit the directory's own path only after everything inside it. Some layouts describe over a hundred million paths, so generate them lazily and stop as soon as you have k.

Return the first k paths of that stream, in order, or all of them if the tree has fewer.

Inputlayout = [["a.log", "sub/", "b.log"], ["x.log"]] root = "/d" k = 10Output["/d/a.log", "/d/sub/x.log", "/d/sub", "/d/b.log", "/d"]

The subdirectory sub holds x.log, so x.log comes out before sub itself, and /d is last because it only empties once b.log is gone.

Inputlayout = [["a/"], ["b/"], ["c/"], ["f.txt"]] root = "/r" k = 2Output["/r/a/b/c/f.txt", "/r/a/b/c"]

The walk goes three levels down to the only file, emits it, then emits the now-empty c, and k = 2 stops it there.

How this uses the pattern

A post-order depth-first walk written as a generator. Each directory yields its files and the full stream of each subdirectory in listed order, then yields its own path. The caller pulls from the generator and stops after k paths, so the work tracks k plus the depth of the tree and never the size of the archive.

Streaming Walk: Yield Paths Instead of Collecting Them

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (8)

Need a hint? (3 available)

The Datadog angle

Datadog's rm -rf round moves through a series of memory follow-ups, and at the end one interviewer pushed for a generator that yields each path, beyond both the collected list and a stack saved to disk. Offer it as a strong senior option and let the interviewer decide whether to go there. It helps because Delete in the reported API removes only a file or an empty directory, so children have to come out before their parent. A caller can then issue one Delete per yielded path and never hold the millions of paths the out-of-memory question is about. Before you code, say the order out loud: entries go in listed order, and every directory comes after its contents.

Take it further

The follow-up before this one is the classic "how do you code it in a way that prevents out of memory?", usually answered with an explicit stack. Past the generator, expect a port to Java or Go. Neither has yield, so the walk becomes an iterator that owns a stack of (path, depth, next entry) frames, or a Go callback that returns false to stop. Then comes "one directory has millions of files", where a single listing no longer fits in a frame; a paged listing lets each frame hold a cursor. Spilling the stack to disk stops mattering once the stack holds one root-to-leaf path.

Show solution & walkthrough

4

Max Root-to-Leaf Sum: Score Every Path Down the Tree

MediumSometimes asked

Problem

An APM trace is a tree of spans, yet it reaches the backend flat. Each span is a record [span_id, parent_id, delta], where delta is the change in that span's self time, in milliseconds, against the previous deploy. A negative delta means the span got faster. The root span has a parent_id of -1. Records arrive in any order, and ids are arbitrary integers.

Write max_root_to_leaf(spans). A call chain runs from the root down to a leaf, meaning a span with no children. Its score is the sum of delta over every span on the chain, root and leaf included. There is at least one span and exactly one root.

Return the highest score over all root-to-leaf chains.

Inputspans = [[1, -1, 3], [2, 1, 2], [3, 1, 4], [4, 2, 5], [5, 2, -1], [6, 3, 1]]Output10

The three chains score 3 + 2 + 5 = 10, 3 + 2 - 1 = 4 and 3 + 4 + 1 = 8, so the best is 10.

Inputspans = [[1, -1, 4], [2, 1, -3]]Output1

The root has one child and every chain must end at a leaf, so the only chain scores 4 - 3 = 1.

How this uses the pattern

Rebuild the tree first. One pass over the records fills a map from each parent id to its child ids and spots the root by its parent of -1. Then walk down from the root carrying a running sum. At a leaf the running sum is a finished chain score, and the answer is the largest of those.

Max Root-to-Leaf Sum: Score Every Path Down the Tree

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (7)

Need a hint? (3 available)

The Datadog angle

Datadog traces are trees, but they don't arrive as trees. Spans reach the backend as flat records pointing at their parents, and every flame graph starts by rebuilding the hierarchy from those pointers. The reported phone-screen version hid its tree behind an unfamiliar class instead, and either way the first job is noticing the tree before you solve anything. Spend your first minute on the shape: build a children map from parent ids, find the root, then carry a running sum down each branch. Before coding, ask about a lone root span, a span with one child, and whether a chain must end at a leaf. Here it must, so a negative leaf still counts.

Take it further

Expect the same follow-ups the directory walk gets. If the trace runs thousands of spans deep, the recursive walk hits Python's recursion limit, so move the pending work onto an explicit stack of (span, running sum) pairs. Next comes the question of which chain won, answered with a parent map and a walk back up from the best leaf to return the span ids in order. A harder follow-up drops both endpoint rules and lets the best chain start and end at any span. Then each span returns its best downward branch to its parent, and the global best is updated with the span plus its two strongest children, clamping negative branches to zero.

Show solution & walkthrough

5

Service Graph: Fastest Path Between Two Hosts

MediumSometimes asked

Problem

A service map draws every server as a node and every call between two servers as an edge, labeled with how long data takes to cross it. Each server here is known by its IP address, and you need the quickest way to get data from one of them to another.

Write fastest_path(servers, times, start_ip, end_ip). servers is a list of IP address strings. times is a square matrix of the same size where times[i][j] is the time in milliseconds to send data from servers[i] directly to servers[j], or -1 when there is no direct link.

Links are one-way, so times[i][j] and times[j][i] can differ. The diagonal is 0 and every real link takes a positive time. Both start_ip and end_ip appear in servers, and the inputs guarantee that the fastest route, when one exists, is unique.

Return the fastest route as the list of IP addresses it passes through, from start_ip to end_ip with both ends included. Return [start_ip] when the two are the same server, and an empty list when end_ip cannot be reached.

Inputservers = ["10.0.0.1", "10.0.0.2", "10.0.0.3", "10.0.0.4"] times = [[0, 2, -1, 10], [-1, 0, 3, 7], [-1, -1, 0, 1], [-1, -1, -1, 0]] start_ip = "10.0.0.1" end_ip = "10.0.0.4"Output["10.0.0.1", "10.0.0.2", "10.0.0.3", "10.0.0.4"]

The direct link costs 10 ms and the detour through .2 alone costs 2 + 7 = 9, but going .1 to .2 to .3 to .4 costs 2 + 3 + 1 = 6.

Inputservers = ["10.0.0.1", "10.0.0.2", "10.0.0.3", "10.0.0.4"] times = [[0, 2, -1, 10], [-1, 0, 3, 7], [-1, -1, 0, 1], [-1, -1, -1, 0]] start_ip = "10.0.0.4" end_ip = "10.0.0.1"Output[]

Every link points toward .4 and none leaves it, so .1 cannot be reached in this direction.

How this uses the pattern

Weighted edges mean breadth-first search no longer works, because the fewest hops can be the slowest route. Run Dijkstra: keep the best known time to every server and repeatedly settle the cheapest unsettled one, relaxing its outgoing links. Each time a link improves a server, record which server you came from. Walking those parent pointers back from the end and reversing gives the route.

Service Graph: Fastest Path Between Two Hosts

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (7)

Need a hint? (3 available)

The Datadog angle

Reports place it in an intern phone screen, so senior readers can treat it as the easier end of the interviews. The graph is a service map, and each weight is the latency of one hop between services, the same picture APM draws for customers. Getting the minimum time is the easy half. The prompt also says to show the path, so keep a parent pointer for every server you improve and walk it back from the end once the search finishes. Before you code, say out loud that links are one-way, that -1 means no link, and what you return for an unreachable end. Then run the first example and an unreachable case yourself.

Take it further

Expect the map to get more realistic. A real service map is sparse, so the matrix turns into a list of links and the scan over every column becomes a walk over each server's neighbors. Then a host goes unhealthy and the route has to avoid it, which costs one membership check before each relax. If the total time comes up, it is already sitting in the distance array for the end server. The senior-level follow-up is scale: a map with thousands of services, where you stop the search the moment the end server leaves the heap and can explain why that first pop is already final.

Show solution & walkthrough

Where candidates lose it