DevOps NetworkDevOpsNetwork
Join Free
Practical infra coding

Directory sizes like du, in one pass

mediumFiles and filesystem

Problem statement

Write a small du -d 1: for every directory directly under a root, print the total size of everything inside it at any depth, largest first, followed by the root's total. An empty directory is still listed with 0 B. Optionally accept a larger depth.

Count regular files only, do not follow symlinks, and keep going past directories you cannot read. The main requirement is efficiency: walk the tree once. Do not re-walk each subtree to total it.

Sample tree (size in bytes)

Bash
var/
log/nginx/access.log 8000
log/nginx/error.log 1000
log/syslog 3000
lib/docker/overlay/l1 20000
lib/docker/overlay/l2 15000
lib/apt/lists 2000
cache/apt/pkg.deb 5000
tmp/ (empty)

Examples

Example 1

Input: `python solution.py` (the demo builds the tree above in a temporary directory)

Output: 36.1 KiB lib 11.7 KiB log 4.9 KiB cache 0 B tmp 52.7 KiB (total)

Explanation: lib is 20000 + 15000 + 2000 = 37000 bytes = 36.1 KiB. The total is 54000 bytes.

Hints

Approach

A post-order traversal done by os.walk.

  1. Walk with topdown=False. For each directory, lstat its files and add up the regular ones.
  2. Add totals[child] for each subdirectory. Because the walk is bottom-up, every child is final before its parent is visited. A symlinked directory appears in dirnames but is never walked, so it contributes 0 through .get(..., 0).
  3. Store totals[dirpath].
  4. Print directories whose relative depth is within max_depth, sorted by (-size, path), then the root.

Every file is stat-ed exactly once, whatever the depth. Memory is one integer per directory (n), which is small compared with the number of files.

ComplexityTime O(f + r log r)Space O(n)
Python
import os
import stat
import sys
import tempfile
from collections import defaultdict
from pathlib import Path
def human(n):
for unit in ("B", "KiB", "MiB", "GiB"):
if n < 1024 or unit == "GiB":
return f"{n} {unit}" if unit == "B" else f"{n:.1f} {unit}"
n /= 1024
def dir_sizes(root):
"""Total bytes under every directory, in one bottom-up pass."""
totals = defaultdict(int)
# topdown=False yields children before parents, so a child's total is
# final by the time we add it to its parent
for dirpath, dirnames, filenames in os.walk(root, topdown=False,
onerror=lambda e: print(f"warning: {e}", file=sys.stderr)):
total = 0
for name in filenames:
try:
st = os.lstat(os.path.join(dirpath, name))
except OSError:
continue
if stat.S_ISREG(st.st_mode):
total += st.st_size
for d in dirnames:
total += totals.get(os.path.join(dirpath, d), 0) # symlinked dirs were never walked: 0
totals[dirpath] = total
return totals
def report(root, max_depth=1):
root = os.path.normpath(root)
totals = dir_sizes(root)
rows = []
for path, size in totals.items():
rel = os.path.relpath(path, root)
if rel != "." and rel.count(os.sep) < max_depth:
rows.append((size, Path(rel).as_posix()))
for size, rel in sorted(rows, key=lambda r: (-r[0], r[1])):
print(f"{human(size):>8} {rel}")
print(f"{human(totals[root]):>8} (total)")
SAMPLE = {
"log/nginx/access.log": 8000, "log/nginx/error.log": 1000, "log/syslog": 3000,
"lib/docker/overlay/l1": 20000, "lib/docker/overlay/l2": 15000, "lib/apt/lists": 2000,
"cache/apt/pkg.deb": 5000,
}
def build_sample(base):
for rel, size in SAMPLE.items():
p = Path(base, rel)
p.parent.mkdir(parents=True, exist_ok=True)
p.write_bytes(b"x" * size)
Path(base, "tmp").mkdir() # an empty directory still gets a row
if __name__ == "__main__":
if len(sys.argv) > 1:
report(sys.argv[1], int(sys.argv[2]) if len(sys.argv) > 2 else 1)
else:
with tempfile.TemporaryDirectory() as tmp:
build_sample(tmp)
report(tmp)

Follow-up questions

  • Add -x: stay on one filesystem, so a mounted NFS share under the root is not counted (compare st_dev).
  • Print a tree view with indentation, children sorted by size, like ncdu.
  • Make the walk resumable across runs on a 100 TB filesystem.

Frequently asked questions

du reports disk usage: allocated blocks (st_blocks * 512), which include block rounding and exclude the holes in sparse files. This script reports apparent size, like du --apparent-size. du also counts each hard-linked inode once. To match du exactly, use st_blocks and keep a set of (st_dev, st_ino) already counted.

Finding which directory filled a disk is routine on-call work, and interviewers like it because the naive solution is quadratic in depth. Seeing that topdown=False gives you a post-order traversal, the same idea as computing subtree sums in a tree, is exactly the DSA-to-infra link they look for.