Find Duplicate Files with a Hand-Written Directory Traversal

Question

The candidate is asked to implement a function that finds duplicate files in a directory by performing a hand-written directory traversal.

Codemia · Accepted Answer

To find duplicate files, I will perform a depth-first traversal of the directory structure. As I traverse, I will read the contents of each file and use a hash map to store file contents as keys and their corresponding file paths as values. If a file's content already exists in the map, it indicates a duplicate.

The algorithm can be outlined as follows:
1. Initialize an empty hash map to store file contents and paths.
2. Define a recursive function that takes a directory path as input.
3. For each item in the directory:
   - If it's a file, read its content and update the hash map.
   - If it's a directory, call the function recursively.
4. After traversal, filter the hash map to find entries with multiple paths, indicating duplicates.

The time complexity of this algorithm is O(N), where N is the total number of files in the directory structure, as each file is read once. The space complexity is O(M), where M is the number of unique file contents stored in the hash map.

Here is a sample implementation in Python:
```python
import os
from collections import defaultdict

def find_duplicate_files(directory):
    file_map = defaultdict(list)
    
    def traverse_dir(dir_path):
        for entry in os.listdir(dir_path):
            full_path = os.path.join(dir_path, entry)
            if os.path.isdir(full_path):
                traverse_dir(full_path)
            else:
                with open(full_path, 'rb') as file:
                    content = file.read()
                    file_map[content].append(full_path)
    
    traverse_dir(directory)
    return [paths for paths in file_map.values() if len(paths) > 1]
```
This code traverses the directory and collects duplicate files based on their content.

While this approach is straightforward, it may not scale well for very large files or directories with millions of files. In such cases, we could consider using file checksums (like SHA-256) instead of reading entire file contents, which would reduce memory usage and potentially speed up comparisons.

Find Duplicate Files with a Hand-Written Directory Traversal

Snapchat

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Snapchat Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline