Quick Overview

This question evaluates competency in designing data structures for hierarchical string-path file systems, including string parsing, stateful API semantics, validation logic, and efficient lookup/update operations.

Implement string-path file system operations

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question LeetCode 1166. Design File System – extended to support Create(path, value), Get(path), Set(path, value) and Delete(path) with validation rules. https://leetcode.com/problems/design-file-system/description/

Overview: This question evaluates competency in designing data structures for hierarchical string-path file systems, including string parsing, stateful API semantics, validation logic, and efficient lookup/update operations.

Implement a simple path-based file system that supports four operations over UNIX-like paths using strings. You are given a list of operations to process; return a result for each operation in order. Paths must start with '/', use '/' as a separator, have no empty segments, and may not end with '/' unless the path is exactly '/'. The root '/' exists by default and cannot be created, set, or deleted. The operations are: 1) Create(path, value): Create a node at 'path' with integer 'value' only if its parent exists and the path does not already exist. Returns True on success, False otherwise. 2) Get(path): Return the integer value stored at 'path', or -1 if the path does not exist or if 'path' is invalid or is '/'. 3) Set(path, value): Update the value at 'path' to 'value'. Returns True if the path exists and is valid (not '/'), otherwise False. 4) Delete(path): Remove the entire subtree rooted at 'path'. Returns True if the path exists and is not '/', otherwise False. Return for each operation: Create/Set/Delete -> boolean; Get -> integer. Input is a list of operations where each operation is one of: ['Create', path, value], ['Get', path], ['Set', path, value], ['Delete', path].

Constraints

  • 1 <= len(ops) <= 50000
  • Sum of path lengths across all operations <= 2e6
  • Each value is a 32-bit signed integer
  • Paths use '/' as separator, start with '/', have no empty segments, and do not end with '/' unless the path is exactly '/'
  • Root '/' exists initially and cannot be created, set, or deleted
  • Create requires the immediate parent of the path to exist and the path to not already exist

Hints

  1. Store the directory tree as nested hash maps (a trie-like structure).
  2. Validate path format before performing any operation.
  3. For Create, traverse to the parent; for Set/Get/Delete, traverse to the exact node.
  4. Delete can be implemented by removing the child entry from its parent's map.

Loading coding console...

Show the approach

Approach

Use a trie-like tree where each node holds a value and a hashmap of children. Paths are validated before any operation: they must start with '/', cannot end with '/', and cannot contain empty segments. The root '/' is represented by the initial node and is not creatable, settable, or deletable. For Create, traverse to the parent and insert a new child if it does not already exist. For Get and Set, traverse to the node; Get returns its value or -1 if missing, and Set updates the value if it exists. For Delete, traverse to the parent and remove the child entry; this discards the entire subtree. Each traversal touches at most the number of segments in the path.

Time complexity:
O(total path segments processed) overall; O(L) per operation where L is the number of segments in the path
Space complexity:
O(N) for N created nodes (sum of path segments created)