Hierarchical In-Memory Data Structures

What's being tested

These problems test building and manipulating hierarchical in-memory trees (file-system trees and tries) and reasoning about graph dependencies and cache eviction policies. Expect to show correct state modeling, path traversal, efficient per-operation complexity, and cycle detection/topological ordering.

Patterns & templates

• Trie node with `Map<char,Node>` children and boolean `isWord` — insert/search in O(L) time, where L is word length; watch memory vs compression tradeoffs.

• In-memory filesystem: represent directories as nodes with `Map<string,Node>` children and leaf files storing content; split paths once, then iterate/recursively traverse.

• Copy/append file ops: keep file content as `StringBuilder`/byte buffer for repeated `addContent` to avoid O(n^2) string copies.

• LRU cache: combine doubly-linked list + `HashMap<key,node>` for O(1) get/put and eviction; update-on-access to head, evict tail.

• Cycle detection / dependencies: use DFS with 3-color marking or Kahn's algorithm (queue of zero in-degree) — both O(V+E) time; be explicit about tie-breaking.

• Topological ordering: Kahn gives deterministic order if you use a `PriorityQueue` for lexicographic stable results.

• Path & permission edge cases: normalize redundant slashes, `..`, empty segments; decide on absolute vs relative semantics before coding.

Common pitfalls

Pitfall: Using naive string concatenation in repeated file writes leads to quadratic time and TLE on large content. Use buffered appends.

Pitfall: Forgetting to update both map and linked-list pointers in LRU removes can corrupt the structure; always update both atomically.

Pitfall: Running DFS without a visited-color scheme misclassifies back-edges and misses cycles in directed dependency graphs.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.