Applied intuition·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

Jul 2026

Summary

System design round at Applied Intuition for a software engineering role. One meaty question that took up the whole session, lots of follow-ups, and I left feeling like I'd only scratched the surface of what they actually wanted.

Questions Asked (1)

You have a massive POSIX-like filesystem with millions of files in nested directories. Design an algorithm to find groups of duplicate files without reading file contents. You can only use metadata like file size, timestamps, permissions, and inode info. Cover how you'd traverse the tree, avoid symlink loops, handle hard links, deal with permission errors, and define what 'duplicate' even means under these constraints. Also discuss data structures, memory and I/O tradeoffs for scale, and give complexity analysis.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one wrecked me a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that without reading contents, 'duplicate' can only mean metadata-identical files, and propose a multi-pass algorithm that first groups by size, then refines using other metadata like inode, timestamps, and permissions. Emphasize a robust traversal that handles symlink loops, hard links, and permission errors, and discuss scalable data structures and tradeoffs.

Pro tip: Mention that you would first check if the filesystem provides a built-in deduplication tool (e.g., fdupes) or if you can use file system APIs like extents or checksums stored in metadata, but since the question restricts to metadata, you'll design from scratch. This shows awareness of practical shortcuts while still solving the problem.

1. Define 'Duplicate' Under Constraints

Clarify that without content, duplicates are files with identical metadata (size, timestamps, permissions, inode). Discuss that this is a heuristic and may produce false positives/negatives, and decide which metadata fields to use.

2. Design Traversal Strategy

Use an iterative DFS with a stack to avoid recursion limits. Track visited directories by (device, inode) to prevent symlink loops and hard link cycles. Handle permission errors by logging and skipping.

3. Handle Hard Links and Symlinks

For hard links, use (device, inode) to identify unique files; count links but treat as same file. For symlinks, either skip or resolve carefully with loop detection.

4. Group and Compare Metadata

Use a hash map keyed by size to bucket files, then within each bucket, compare other metadata (e.g., mtime, permissions) to form candidate groups. Optionally use a composite key.

5. Analyze Complexity and Tradeoffs

Discuss time O(N) for traversal and grouping, space O(N) for metadata storage. Consider memory vs. I/O tradeoffs: storing all metadata in memory vs. external sorting. Mention scalability with sharding or streaming.

Key Points to Mention

Use (device, inode) to detect hard links and avoid double-counting.
Implement symlink loop detection via visited set of (device, inode) for directories.
Handle permission errors gracefully by skipping and logging.
Choose metadata fields: size is most discriminating; timestamps and permissions can refine.
Data structures: hash map for grouping, stack for DFS, set for visited.
Complexity: O(N) time, O(N) space; discuss memory pressure and possible external sort.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.