1166. Design File System

At a Glance

Topic: system-design-coding
Pattern: Trie path composition (Trie)
Difficulty: Medium
Companies: Amazon, Google, Uber, DoorDash, Stripe
Frequency: Medium
LeetCode: 1166

Problem (one-liner)

Implement a virtual filesystem: create paths with associated integer values, query exact path value, and list all paths under a prefix that store a value (lexicographic).

Recognition Cues

Path strings with / separators
Prefix listing — trie over path segments

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Flat map of full path strings — works for exact get; listing children needs prefix filter — slow.
Optimal — trie node per segment; leaf or node stores value if path is valid file.

Optimal Solution

Go

package main

import "sort"

// FileSystem API:
// - Constructor()
// - bool createPath(path string, value int)
// - int get(string path)
// - []string ls(string path)

type segmentNode struct {
	children map[string]*segmentNode
	value    int
	hasValue bool
}

type FileSystem struct {
	root *segmentNode
}

func Constructor() FileSystem {
	return FileSystem{root: &segmentNode{children: map[string]*segmentNode{}}}
}

func (filesystem *FileSystem) createPath(path string, value int) bool {
	if len(path) == 0 || path[0] != '/' {
		return false
	}
	segments := splitPath(path)
	current := filesystem.root
	for index := 0; index < len(segments)-1; index++ {
		name := segments[index]
		child, exists := current.children[name]
		if !exists {
			child = &segmentNode{children: map[string]*segmentNode{}}
			current.children[name] = child
		}
		if child.hasValue {
			return false
		}
		current = child
	}
	last := segments[len(segments)-1]
	if _, exists := current.children[last]; exists {
		return false
	}
	current.children[last] = &segmentNode{
		children: map[string]*segmentNode{},
		value:    value,
		hasValue: true,
	}
	return true
}

func (filesystem *FileSystem) get(path string) int {
	node := filesystem.walkExisting(path)
	if node == nil || !node.hasValue {
		return -1
	}
	return node.value
}

func (filesystem *FileSystem) ls(path string) []string {
	if path == "/" {
		names := collectNames(filesystem.root)
		sort.Strings(names)
		return names
	}
	node := filesystem.walkExisting(path)
	if node == nil {
		return []string{}
	}
	if node.hasValue {
		segments := splitPath(path)
		return []string{segments[len(segments)-1]}
	}
	names := collectNames(node)
	sort.Strings(names)
	return names
}

func (filesystem *FileSystem) walkExisting(path string) *segmentNode {
	if path == "/" {
		return filesystem.root
	}
	segments := splitPath(path)
	current := filesystem.root
	for _, name := range segments {
		next, exists := current.children[name]
		if !exists {
			return nil
		}
		current = next
	}
	return current
}

func splitPath(path string) []string {
	parts := []string{}
	start := 1
	for index := 1; index <= len(path); index++ {
		if index == len(path) || path[index] == '/' {
			if start < index {
				parts = append(parts, path[start:index])
			}
			start = index + 1
		}
	}
	return parts
}

func collectNames(node *segmentNode) []string {
	names := make([]string, 0, len(node.children))
	for name := range node.children {
		names = append(names, name)
	}
	return names
}

JavaScript

class SegmentNode {
	constructor() {
		this.children = new Map();
		this.value = 0;
		this.hasValue = false;
	}
}

class FileSystem {
	constructor() {
		this.root = new SegmentNode();
	}

	createPath(path, value) {
		if (!path || path[0] !== '/') {
			return false;
		}
		const segments = this.splitPath(path);
		let current = this.root;
		for (let index = 0; index < segments.length - 1; index++) {
			const name = segments[index];
			if (!current.children.has(name)) {
				current.children.set(name, new SegmentNode());
			}
			const child = current.children.get(name);
			if (child.hasValue) {
				return false;
			}
			current = child;
		}
		const last = segments[segments.length - 1];
		if (current.children.has(last)) {
			return false;
		}
		const created = new SegmentNode();
		created.value = value;
		created.hasValue = true;
		current.children.set(last, created);
		return true;
	}

	get(path) {
		const node = this.walkExisting(path);
		if (!node || !node.hasValue) {
			return -1;
		}
		return node.value;
	}

	ls(path) {
		if (path === '/') {
			const names = Array.from(this.root.children.keys()).sort();
			return names;
		}
		const node = this.walkExisting(path);
		if (!node) {
			return [];
		}
		if (node.hasValue) {
			const segments = this.splitPath(path);
			return [segments[segments.length - 1]];
		}
		return Array.from(node.children.keys()).sort();
	}

	splitPath(path) {
		return path.split('/').filter(Boolean);
	}

	walkExisting(path) {
		if (path === '/') {
			return this.root;
		}
		const segments = this.splitPath(path);
		let current = this.root;
		for (const name of segments) {
			if (!current.children.has(name)) {
				return null;
			}
			current = current.children.get(name);
		}
		return current;
	}
}