What is file-system flavoured coding, and how do you solve it?

In this article

1. Before you start
2. Why interviewers ask this
3. File-system flavoured coding from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the machine coding rounds guide, which covers the wider family of applied coding rounds.

Why interviewers ask this

A path function that passes the easy example and fails on /../ costs the point, and these problems are built to expose exactly that. Candidates report four versions: implementing a cd command, simplifying or validating a path, building a trie for a file system and scanning for duplicate files. These are candidate reports, not confirmed by a public source for any one company.

The problems look small, yet they test whether you can turn a written rule into a data structure and then list the edge cases without being asked. A weak answer replaces text with a regular expression and hopes. A strong answer names the rule for each kind of component, uses a stack, states that the work is on the string and not on the disk, and tests the root, repeated slashes and a trailing slash. A Staff-level answer also says what changes when symbolic links exist.

File-system flavoured coding from first principles

File-system flavoured coding

File-system flavoured coding is a family of interview problems that reproduce the rules of a file system, such as path resolution, directory trees and file scanning, as ordinary data-structure code, usually on strings and in-memory structures rather than on a real disk.

Canonical path

A canonical path is the one shortest absolute spelling of a location, in the lexical sense: it starts with a slash, holds no . or .. components, no empty components and no trailing slash, except that the root directory is a single slash.

Lexical normalisation

Lexical normalisation is the rewriting of a path as plain text, by removing redundant separators and dot references, without looking at the disk, so it can change the meaning of a path that contains symbolic links.

In plain words

Picture walking through a building while keeping a list of the rooms you passed through. Entering a room adds its name to the list. "Go back" crosses off the last name. Standing at the front door, "go back" does nothing, because there is nothing behind the entrance. Your final location is the list read from the front door.

The analogy breaks in one place. In a real building a shortcut door can drop you somewhere unrelated. A file system's symbolic links do the same, so the text-only version is a deliberate simplification.

In one precise sentence: file-system flavoured path problems are a left-to-right walk over the parts of a path. The walk keeps a stack of names and returns the stack joined by slashes.

Step 1: Split the path into components

A path is resolved component by component: each name is looked up in the directory named by the one before it, and a leading slash means start at the root directory (Portable Operating System Interface (POSIX) pathname resolution). Splitting the string on the slash character gives the components.

Input: one string. Output: a list of parts, each one of four kinds: an empty part, a single dot, a double dot, or a name. Empty parts appear because repeated slashes count as one slash (problem statement of LeetCode 71), and Python's normpath collapses A//B to A/B (Python os.path documentation). Empty and dot components are skipped. A part made only of three or more dots is an ordinary name, because the same problem statement treats any other run of periods as a valid directory or file name. You now have a clean list of parts to walk through.

Step 2: Dot-dot pops the stack, never past the root

A double-dot component removes the previous name from the stack, and at the root it removes nothing. This is where many first attempts break.

POSIX uses the same deletion rule, and also checks that each popped component is a directory: for each dot-dot, the preceding component and the dot-dot are deleted only if that component exists and is neither the root nor another dot-dot, and in logical mode cd reports an error if that component is not a directory (POSIX cd, via the man7 copy). A leading /.. is left as text for the system to resolve, while the interview versions simply stay at the root. In code the check is one line, and a dot-dot pops the stack only when it is not empty.

A name is pushed, a dot-dot pops if it can, and everything else is ignored. A solution that pops without checking crashes on /.., and one that treats the root like a folder produces a path that climbs above it. You now know every rule the walk needs.

Step 3: Join the stack into one canonical path

The final path is a slash followed by the stack's names joined with slashes, and an empty stack joins to the root slash. That rule also removes trailing slashes, which a canonical path does not have except for the root (LeetCode 71).

A trailing slash is not decoration in the real system: a pathname with a trailing slash resolves as if a dot were appended, so it names a directory (POSIX pathname resolution). A normaliser drops it because the canonical form needs no marker.

def simplify(path):
    stack = []
    for part in path.split("/"):
        if part in ("", "."):
            continue
        if part == "..":
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return "/" + "/".join(stack)

Each part is pushed at most once and popped at most once, so time and space are linear in the length of the path.

Step 4: cd adds the working directory, then walks the same way

A relative cd joins the working directory, a slash and the operand, then normalises the result; an absolute operand skips the join. POSIX states both: an operand beginning with a slash is used as it is, and otherwise the value of the present working directory (PWD) variable is placed in front (POSIX cd). The final step is the same canonical-form walk as before. A real shell may also search the change-directory search path (CDPATH), an environment variable holding a list of directories, for a relative operand that does not start with a dot; the interview version ignores it unless the prompt asks for it.

def cd(pwd, operand):
    if operand.startswith("/"):
        return simplify(operand)
    return simplify(pwd + "/" + operand)

The function never checks that the directory exists, and that is the intended reading of the interview prompt: behave like cd followed by pwd and return the normalised absolute path. Doubled slashes from the join disappear in the walk, so the code needs no special case for a working directory that already ends in a slash. Python's normpath is likewise a string operation only (Python documentation).

1 · Split2 · Walk3 · Join4 · cdReplay

Step-by-step description

1. Split the path on slashes.
2. Dot-dot pops, never past the root.
3. Join the stack with slashes.
4. cd adds the working directory first.

• Empty and dot components are skipped.
• A dot-dot pops the stack only when it is not empty.
• An empty stack joins to the root slash.
• A relative cd joins the working directory first, then runs the same walk.

Worked example

Take the path /a/./b/../../c/. Splitting gives the parts a, a dot, b, a double dot, a second double dot and c, plus empty parts at the two ends. The stack is a, then a and b, then a, then empty, then c, so the result is /c.¹ The second double dot meets a stack holding only a, empties it, and the name c is then pushed onto an empty stack.

Text description of the diagram

• The stack depth after each non-empty part is 1, 1, 2, 1, 0 and 1.
• The dot leaves the depth at 1 because it is skipped.

The stack depth after each non-empty part is 1, 1, 2, 1, 0 and 1.¹ The dot leaves the depth at 1 because it is skipped.

All six rows were produced by the code above.¹ The same script also shows that three paths in a directory tree, /a/b/c, /a/b/d and /a/e, hold 8 components in total but need only 5 trie nodes besides the root, because the shared prefixes are stored once.¹

For the duplicate scan, the illustrative file sizes 100, 100, 100, 200, 300 and 300 bytes leave 5 files that share a size with another file, so only those need hashing and the file of 200 bytes is skipped.¹ A 10-gibibyte (GiB) file read in chunks of 1 mebibyte (MiB) takes 10,240 reads, and a Secure Hash Algorithm (SHA) 256 digest is 32 bytes, or 64 hexadecimal characters.¹

Trade-offs and edge cases

The textbook answer assumes the text-only meaning of the double dot, and that assumption must be said aloud. The sections below cover the four places it matters.

Which dot-dot do you mean: logical or physical?

The default mode of cd handles a double dot logically, without resolving symbolic links first, and cd -P resolves them first (POSIX cd). Python warns that string normalisation may change the meaning of a path that contains symbolic links (Python documentation). Both real modes check the disk: logical cd checks that each popped component is a directory and then calls chdir, and physical cd resolves links first. The interview version uses the logical dot-dot rule without those checks, so it works on the string alone.

Text description of the diagram

• The default cd mode handles dot-dot logically, without resolving symbolic links first.
• The physical mode resolves symbolic links before dot-dot.
• The interview version works on the string alone.

How do you validate a path?

No standard defines a valid path in the interview sense, so ask for the rules. The pathname-resolution text does say that a component longer than NAME_MAX is an error (POSIX pathname resolution). Two leading slashes may be treated in an implementation-defined way, while more than two count as one (Python documentation). Write down the rule list the interviewer accepts, then check each component against it. An illustrative rule set: the path must start with /; no component may be longer than NAME_MAX; no component may contain the null character (NUL); and the allowed character set is whatever you agree with the interviewer.

How does a trie model a file system?

A trie is a tree in which each edge is labelled with one piece of a key, so keys that share a prefix share a path. For a file system each edge is one directory or file name, and a node can hold file contents or a flag. Creating /a/b/c walks from the root and adds missing nodes; listing a directory reads the names on the node's edges. The worked example shows the saving from shared prefixes. Walk the path with the same component rules as step 1.

class Node:
    def __init__(self):
        self.children = {}   # name -> Node
        self.content = None  # None for a directory, text for a file

class FileSystem:
    def __init__(self):
        self.root = Node()

    def _walk(self, path, create=False):
        node = self.root
        for part in simplify(path).split("/"):  # simplify from step 3
            if part == "":
                continue
            if part not in node.children:
                if not create:
                    raise FileNotFoundError(path)
                node.children[part] = Node()
            node = node.children[part]
        return node

    def mkdir(self, path):
        self._walk(path, create=True)

    def ls(self, path):
        node = self._walk(path)
        if node.content is not None:        # a file: return its own name
            return [simplify(path).split("/")[-1]]
        return sorted(node.children)

    def write(self, path, text):
        node = self._walk(path, create=True)
        node.content = (node.content or "") + text

    def read(self, path):
        return self._walk(path).content

Each call costs time proportional to the number of components in the path. ls returns the sorted child names, or the file's own name for a file. The script was run: after creating /a/b/c, /a/b/d and /a/e and writing hi then ! to /a/b/c/f.txt, ls /a gave ['b', 'e'], read /a/b/c/f.txt gave hi! and ls /a/b/../e gave [].¹

How do you find duplicate files?

A common engineering approach, not one taken from a standard, narrows candidates in stages: group files by size, hash a prefix of each group, hash the full content of what remains, then compare bytes if a collision matters. A hash is a fixed-size fingerprint computed from the bytes of a file, and equal files always give equal fingerprints. Hashing in chunks is valid because repeated update calls equal one call on the concatenation, and Python 3.11 added hashlib.file_digest for this (hashlib documentation). Unequal sizes rule out equality without reading a byte.

import hashlib, os, stat

def find_duplicates(root):
    seen = set()      # (st_dev, st_ino): one entry per real file
    by_size = {}
    for dirpath, _, names in os.walk(root, followlinks=False):
        for name in names:
            path = os.path.join(dirpath, name)
            try:
                st = os.lstat(path)           # lstat: do not follow links
            except PermissionError:
                continue
            if not stat.S_ISREG(st.st_mode):  # regular files only
                continue
            key = (st.st_dev, st.st_ino)
            if key in seen:                   # a hard link to a file already seen
                continue
            seen.add(key)
            by_size.setdefault(st.st_size, []).append(path)

    groups = {}
    for size, paths in by_size.items():
        if len(paths) < 2:                    # a unique size cannot be a duplicate
            continue
        for path in paths:
            h = hashlib.sha256()
            try:
                with open(path, "rb") as f:
                    while chunk := f.read(1 << 20):   # one mebibyte at a time
                        h.update(chunk)
            except PermissionError:
                continue
            groups.setdefault((size, h.hexdigest()), []).append(path)
    return [g for g in groups.values() if len(g) > 1]

Hard links to one inode are one file, so the seen set skips them. The size and hard-link grouping was run on illustrative records: it skipped 1 hard link, left 4 files to hash and skipped 1 file with a unique size.¹ The disk-reading part (os.walk, os.lstat, open) is not run in the data script.

Related applied rounds are covered in the CodeSignal in-memory database walkthrough and the least recently used cache in Python.

How to answer it in an interview

The spoken structure: say it is lexical, state the join rule, give the four component rules, then name the root case, the complexity and the symbolic-link caveat.

Common mistakes

• "A double dot just removes the previous folder." (wrong) That fails at the root and, with symbolic links, in the physical mode. (right) "It pops only if the stack is not empty, and I am working on text."
• "Three dots mean something special." (wrong) In the LeetCode statement a run of periods other than one or two is an ordinary name. (right) "... is pushed as a name."
• "Double slashes are an error." (wrong) Repeated slashes count as one; exactly two leading slashes are the implementation-defined exception. (right) "I skip empty parts."
• "A trailing slash stays in the answer." (wrong) The canonical form has none except for the root. (right) "I rebuild the path from the stack."
• "Equal hashes prove equal files." (wrong) Collisions are possible in principle. (right) "I confirm with a byte comparison, or I state the hash assumption."

Follow-up questions

How do you implement cd() so it returns the final normalised absolute path?

Join the working directory and the operand when the operand is relative, split on slashes, walk the parts with a stack and return a slash plus the joined stack. The event and log processing problems use the same split-and-fold habit on lines instead of path parts.

How do you check whether a file path with slashes and dots is valid?

Ask which rules apply, because there is no single standard. Then check each component against them, for example the component length limit and which characters are banned, after splitting with the same four component kinds.

How do you implement a trie for a file system?

Store one node per name, with a map from child name to child node, and walk each path component by component, creating missing nodes on writes. The low level design interview questions show where this fits in a larger class design.

How do you find duplicate files in a file system?

Group by size, hash a prefix or a chunk of each group, then hash the full content of the survivors and optionally compare bytes. Only files that share a size can be equal.

What chunk size and hashing algorithm should a duplicate finder use?

Pick a chunk size such as one mebibyte (illustrative) and justify it by memory use and read count, then say you would measure alternatives. Use a strong hash such as SHA-256 and say whether you verify bytes after a match.

How do you tell whether a duplicate finder is I/O-bound or CPU-bound?

Measure it: time the reads alone against the reads plus hashing, and watch whether the central processing unit (CPU) or the disk is saturated. If reading alone takes about as long as the whole run, the input/output (I/O) side is the limit. Run the timing twice or drop the page cache first, because a warm cache hides disk cost; if hashing dominates, a faster hash such as blake2b, which hashlib provides, is one option to measure. For another structure-walking problem, see nested list weight sum; for expiring entries, see time-based key-value stores.

Sources

1. cd - change the working directory (POSIX.1-2017, Shell and Utilities) — The Open Group, 1 Jan 2018
2. cd(1p) POSIX Programmer's Manual — man7.org (Linux man-pages), 9 Sep 2026
3. Pathname Resolution (Base Definitions, Issue 6) — The Open Group, 1 Jan 2004
4. os.path - Common pathname manipulations — Python Software Foundation, 14 Oct 2026
5. 71. Simplify Path (problem statement, mirror) — LeetCode via the doocs/leetcode repository, 26 Oct 2026
6. hashlib - Secure hashes and message digests — Python Software Foundation, 2 Sep 2026