File System

Functional Requirements

• Support a tree-like directory structure with files and folders
• Files can be created, read, written, deleted, moved, and copied
• Directories can be created, listed, and deleted (with contents)
• Support path-based navigation (/home/user/documents/file.txt)
• Implement permission system: read (r), write (w), execute (x) for owner/group/others
• Track file metadata: size, timestamps (created, modified, accessed)
• Support file content storage and retrieval

Non-Functional Requirements

• Performance: Efficient path resolution and file lookup
• Concurrency: Thread-safe operations for simultaneous access
• Scalability: Handle millions of files efficiently
• Durability: Metadata persistence (in-memory for LLD, but discuss persistence)

Core Entities

Entity	Description
INode	Abstract base for all file system objects
File	Represents a file with content and metadata
Directory	Contains child inodes, implements Composite pattern
Permission	Read/write/execute bits for owner/group/others
FileSystem	Entry point, manages root and operations

Directory Tree Structure

/ (root)
├── home/
│   ├── user1/
│   │   ├── documents/
│   │   │   ├── resume.pdf (245KB)
│   │   │   └── notes.txt (12KB)
│   │   ├── photos/
│   │   │   └── vacation.jpg (3.2MB)
│   │   └── .bashrc (1KB)
│   └── user2/
│       └── projects/
│           └── app/
│               └── main.java (5KB)
├── etc/
│   ├── passwd (4KB)
│   └── hosts (1KB)
└── tmp/
    └── cache.dat (50MB)

Inode Concept

An inode (index node) is a data structure that stores metadata about a file or directory. It doesn't contain the filename or the actual data, but rather pointers to data blocks and metadata.

INode Hierarchy with Composite Pattern

// Permission class
public class Permission {
    private boolean ownerRead, ownerWrite, ownerExecute;
    private boolean groupRead, groupWrite, groupExecute;
    private boolean othersRead, othersWrite, othersExecute;
    
    public Permission(boolean... perms) {
        this.ownerRead = perms[0];
        this.ownerWrite = perms[1];
        this.ownerExecute = perms[2];
        this.groupRead = perms[3];
        this.groupWrite = perms[4];
        this.groupExecute = perms[5];
        this.othersRead = perms[6];
        this.othersWrite = perms[7];
        this.othersExecute = perms[8];
    }
    
    public static Permission defaultFile() {
        return new Permission(true, true, false, true, false, false, true, false, false);
    }
    
    public static Permission defaultDir() {
        return new Permission(true, true, true, true, false, true, true, false, true);
    }
    
    public boolean canRead(String user, String group, Set<String> userGroups) {
        if (isOwner(user)) return ownerRead;
        if (userGroups.contains(group)) return groupRead;
        return othersRead;
    }
    
    public boolean canWrite(String user, String group, Set<String> userGroups) {
        if (isOwner(user)) return ownerWrite;
        if (userGroups.contains(group)) return groupWrite;
        return othersWrite;
    }
    
    public boolean canExecute(String user, String group, Set<String> userGroups) {
        if (isOwner(user)) return ownerExecute;
        if (userGroups.contains(group)) return groupExecute;
        return othersExecute;
    }
    
    private boolean isOwner(String user) {
        return user.equals(owner);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(ownerRead ? 'r' : '-');
        sb.append(ownerWrite ? 'w' : '-');
        sb.append(ownerExecute ? 'x' : '-');
        sb.append(groupRead ? 'r' : '-');
        sb.append(groupWrite ? 'w' : '-');
        sb.append(groupExecute ? 'x' : '-');
        sb.append(othersRead ? 'r' : '-');
        sb.append(othersWrite ? 'w' : '-');
        sb.append(othersExecute ? 'x' : '-');
        return sb.toString();
    }
}

// Abstract INode base class
public abstract class INode {
    protected final String name;
    protected final String owner;
    protected final String group;
    protected Permission permission;
    protected final long createdAt;
    protected long modifiedAt;
    protected long accessedAt;
    protected long size;
    
    public INode(String name, String owner, String group) {
        this.name = name;
        this.owner = owner;
        this.group = group;
        this.createdAt = System.currentTimeMillis();
        this.modifiedAt = this.createdAt;
        this.accessedAt = this.createdAt;
        this.size = 0;
    }
    
    public String getName() { return name; }
    public String getOwner() { return owner; }
    public String getGroup() { return group; }
    public Permission getPermission() { return permission; }
    public long getCreatedAt() { return createdAt; }
    public long getModifiedAt() { return modifiedAt; }
    public long getAccessedAt() { return accessedAt; }
    public long getSize() { return size; }
    
    public void setPermission(Permission perm) { this.permission = perm; }
    public void touch() { this.accessedAt = System.currentTimeMillis(); }
    public void modify() { this.modifiedAt = System.currentTimeMillis(); }
    
    public abstract boolean isFile();
    public abstract boolean isDirectory();
}

File Implementation

public class File extends INode {
    private byte[] content;
    
    public File(String name, String owner, String group) {
        super(name, owner, group);
        this.permission = Permission.defaultFile();
        this.content = new byte[0];
    }
    
    @Override
    public boolean isFile() { return true; }
    
    @Override
    public boolean isDirectory() { return false; }
    
    public byte[] read() {
        touch();
        return content.clone();
    }
    
    public void write(byte[] data) {
        this.content = data.clone();
        this.size = data.length;
        modify();
    }
    
    public void append(byte[] data) {
        byte[] newContent = new byte[content.length + data.length];
        System.arraycopy(content, 0, newContent, 0, content.length);
        System.arraycopy(data, 0, newContent, content.length, data.length);
        this.content = newContent;
        this.size = newContent.length;
        modify();
    }
    
    public File copy(String newName) {
        File copy = new File(newName, this.owner, this.group);
        copy.write(this.content);
        return copy;
    }
}

Directory Implementation (Composite Pattern)

public class Directory extends INode {
    private final Map<String, INode> children;
    
    public Directory(String name, String owner, String group) {
        super(name, owner, group);
        this.permission = Permission.defaultDir();
        this.children = new LinkedHashMap<>();
    }
    
    @Override
    public boolean isFile() { return false; }
    
    @Override
    public boolean isDirectory() { return true; }
    
    public void addEntry(INode node) {
        children.put(node.getName(), node);
        this.size = children.size();
        modify();
    }
    
    public void removeEntry(String name) {
        children.remove(name);
        this.size = children.size();
        modify();
    }
    
    public INode getEntry(String name) {
        return children.get(name);
    }
    
    public List<INode> listEntries() {
        touch();
        return new ArrayList<>(children.values());
    }
    
    public boolean contains(String name) {
        return children.containsKey(name);
    }
    
    public Directory deepCopy(String newName) {
        Directory copy = new Directory(newName, this.owner, this.group);
        for (INode child : children.values()) {
            if (child instanceof File) {
                copy.addEntry(((File) child).copy(child.getName()));
            } else if (child instanceof Directory) {
                copy.addEntry(((Directory) child).deepCopy(child.getName()));
            }
        }
        return copy;
    }
}

Path Resolution

public class PathResolver {
    private final Directory root;
    
    public PathResolver(Directory root) {
        this.root = root;
    }
    
    // Resolve absolute path like /home/user/file.txt
    public INode resolve(String path) {
        if (!path.startsWith("/")) {
            throw new IllegalArgumentException("Path must be absolute: " + path);
        }
        
        String[] parts = path.split("/");
        INode current = root;
        
        for (String part : parts) {
            if (part.isEmpty()) continue;
            if (!(current instanceof Directory)) {
                throw new IllegalArgumentException("Not a directory: " + current.getName());
            }
            Directory dir = (Directory) current;
            current = dir.getEntry(part);
            if (current == null) {
                throw new FileNotFoundException("Path not found: " + path);
            }
        }
        return current;
    }
    
    // Get parent directory of a path
    public Directory getParent(String path) {
        int lastSlash = path.lastIndexOf('/');
        if (lastSlash <= 0) return root;
        return (Directory) resolve(path.substring(0, lastSlash));
    }
    
    // Get filename from path
    public String getFileName(String path) {
        int lastSlash = path.lastIndexOf('/');
        return path.substring(lastSlash + 1);
    }
}

FileSystem Class

public class FileSystem {
    private final Directory root;
    private final PathResolver resolver;
    
    public FileSystem() {
        this.root = new Directory("/", "root", "root");
        this.resolver = new PathResolver(root);
    }
    
    // Create a file at the given path
    public File createFile(String path, String user) throws PermissionDeniedException {
        Directory parent = resolver.getParent(path);
        String name = resolver.getFileName(path);
        
        if (!parent.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to " + parent.getName());
        }
        if (parent.contains(name)) {
            throw new IllegalArgumentException("File already exists: " + name);
        }
        
        File file = new File(name, user, "users");
        parent.addEntry(file);
        return file;
    }
    
    // Read file content
    public byte[] readFile(String path, String user) throws PermissionDeniedException {
        INode node = resolver.resolve(path);
        
        if (!(node instanceof File)) {
            throw new IllegalArgumentException("Not a file: " + path);
        }
        File file = (File) node;
        
        if (!file.canRead(user)) {
            throw new PermissionDeniedException("Cannot read " + path);
        }
        
        return file.read();
    }
    
    // Write to file
    public void writeFile(String path, byte[] content, String user) throws PermissionDeniedException {
        INode node = resolver.resolve(path);
        
        if (!(node instanceof File)) {
            throw new IllegalArgumentException("Not a file: " + path);
        }
        File file = (File) node;
        
        if (!file.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to " + path);
        }
        
        file.write(content);
    }
    
    // Create directory
    public Directory mkdir(String path, String user) throws PermissionDeniedException {
        Directory parent = resolver.getParent(path);
        String name = resolver.getFileName(path);
        
        if (!parent.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to " + parent.getName());
        }
        if (parent.contains(name)) {
            throw new IllegalArgumentException("Directory already exists: " + name);
        }
        
        Directory dir = new Directory(name, user, "users");
        parent.addEntry(dir);
        return dir;
    }
    
    // List directory contents
    public List<INode> ls(String path, String user) throws PermissionDeniedException {
        INode node = resolver.resolve(path);
        
        if (!(node instanceof Directory)) {
            throw new IllegalArgumentException("Not a directory: " + path);
        }
        Directory dir = (Directory) node;
        
        if (!dir.canRead(user)) {
            throw new PermissionDeniedException("Cannot read " + path);
        }
        
        return dir.listEntries();
    }
    
    // Delete file or empty directory
    public void delete(String path, String user) throws PermissionDeniedException {
        Directory parent = resolver.getParent(path);
        String name = resolver.getFileName(path);
        INode node = resolver.resolve(path);
        
        if (!parent.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to " + parent.getName());
        }
        
        if (node instanceof Directory) {
            Directory dir = (Directory) node;
            if (!dir.listEntries().isEmpty()) {
                throw new IllegalArgumentException("Directory not empty: " + path);
            }
        }
        
        parent.removeEntry(name);
    }
    
    // Move file or directory
    public void move(String sourcePath, String destPath, String user) throws PermissionDeniedException {
        Directory sourceParent = resolver.getParent(sourcePath);
        Directory destParent = resolver.getParent(destPath);
        String sourceName = resolver.getFileName(sourcePath);
        String destName = resolver.getFileName(destPath);
        INode node = resolver.resolve(sourcePath);
        
        if (!sourceParent.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to source directory");
        }
        if (!destParent.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to destination directory");
        }
        
        sourceParent.removeEntry(sourceName);
        // Rename if destination name is different
        if (node instanceof File) {
            File file = (File) node;
            File moved = file.copy(destName);
            destParent.addEntry(moved);
        } else if (node instanceof Directory) {
            Directory dir = (Directory) node;
            Directory moved = dir.deepCopy(destName);
            destParent.addEntry(moved);
        }
    }
    
    // Copy file or directory
    public void copy(String sourcePath, String destPath, String user) throws PermissionDeniedException {
        Directory destParent = resolver.getParent(destPath);
        String destName = resolver.getFileName(destPath);
        INode node = resolver.resolve(sourcePath);
        
        if (!destParent.canWrite(user)) {
            throw new PermissionDeniedException("Cannot write to destination directory");
        }
        
        if (node instanceof File) {
            File file = (File) node;
            File copy = file.copy(destName);
            destParent.addEntry(copy);
        } else if (node instanceof Directory) {
            Directory dir = (Directory) node;
            Directory copy = dir.deepCopy(destName);
            destParent.addEntry(copy);
        }
    }
    
    // Find files matching a pattern (simple implementation)
    public List<String> find(String startPath, String pattern, String user) throws PermissionDeniedException {
        List<String> results = new ArrayList<>();
        findRecursive(startPath, pattern, user, results);
        return results;
    }
    
    private void findRecursive(String path, String pattern, String user, List<String> results) {
        try {
            INode node = resolver.resolve(path);
            if (node.getName().contains(pattern)) {
                results.add(path);
            }
            if (node instanceof Directory) {
                Directory dir = (Directory) node;
                for (INode child : dir.listEntries()) {
                    findRecursive(path + "/" + child.getName(), pattern, user, results);
                }
            }
        } catch (Exception e) {
            // Skip inaccessible paths
        }
    }
}

Permission Checking

public class PermissionDeniedException extends Exception {
    public PermissionDeniedException(String message) {
        super(message);
    }
}

// Extension to INode
public abstract class INode {
    // ... existing fields ...
    
    public boolean canRead(String user) {
        Set<String> userGroups = UserService.getGroups(user);
        return permission.canRead(user, this.group, userGroups);
    }
    
    public boolean canWrite(String user) {
        Set<String> userGroups = UserService.getGroups(user);
        return permission.canWrite(user, this.group, userGroups);
    }
    
    public boolean canExecute(String user) {
        Set<String> userGroups = UserService.getGroups(user);
        return permission.canExecute(user, this.group, userGroups);
    }
}

File Allocation Strategies

// File Allocation Table (FAT) approach
public class FileAllocationTable {
    private final Map<Integer, List<Integer>> fileBlocks; // fileId -> list of block IDs
    private final Set<Integer> freeBlocks;
    
    public FileAllocationTable(int totalBlocks) {
        this.fileBlocks = new HashMap<>();
        this.freeBlocks = new TreeSet<>();
        for (int i = 0; i < totalBlocks; i++) {
            freeBlocks.add(i);
        }
    }
    
    // Contiguous allocation: allocate consecutive blocks
    public boolean allocateContiguous(int fileId, int numBlocks) {
        int start = findContiguousFree(numBlocks);
        if (start == -1) return false;
        
        List<Integer> blocks = new ArrayList<>();
        for (int i = 0; i < numBlocks; i++) {
            blocks.add(start + i);
            freeBlocks.remove(start + i);
        }
        fileBlocks.put(fileId, blocks);
        return true;
    }
    
    // Linked allocation: each block points to next
    public void allocateLinked(int fileId, int numBlocks) {
        List<Integer> blocks = new ArrayList<>();
        for (int i = 0; i < numBlocks; i++) {
            int block = freeBlocks.iterator().next();
            freeBlocks.remove(block);
            blocks.add(block);
        }
        fileBlocks.put(fileId, blocks);
    }
    
    // Indexed allocation: index block contains pointers
    public Map<Integer, List<Integer>> getIndexedAllocation(int fileId) {
        Map<Integer, List<Integer>> result = new HashMap<>();
        List<Integer> blocks = fileBlocks.get(fileId);
        if (blocks != null) {
            result.put(0, blocks); // Index 0 contains all block pointers
        }
        return result;
    }
    
    private int findContiguousFree(int numBlocks) {
        int count = 0;
        int start = -1;
        for (int block : freeBlocks) {
            if (start == -1) start = block;
            count++;
            if (count == numBlocks) return start;
        }
        return -1;
    }
}

Caching Layer

public class FileSystemCache {
    private final Map<String, INode> pathCache;
    private final Map<Integer, byte[]> contentCache;
    private final int maxSize;
    
    public FileSystemCache(int maxSize) {
        this.pathCache = new LinkedHashMap<>(maxSize, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, INode> eldest) {
                return size() > FileSystemCache.this.maxSize;
            }
        };
        this.contentCache = new HashMap<>();
        this.maxSize = maxSize;
    }
    
    public INode getCachedNode(String path) {
        return pathCache.get(path);
    }
    
    public void cacheNode(String path, INode node) {
        pathCache.put(path, node);
    }
    
    public byte[] getCachedContent(int inodeId) {
        return contentCache.get(inodeId);
    }
    
    public void cacheContent(int inodeId, byte[] content) {
        contentCache.put(inodeId, content);
    }
    
    public void invalidate(String path) {
        pathCache.remove(path);
    }
}

Visitor Pattern for Traversal

public interface FileSystemVisitor {
    void visit(File file, String path);
    void visit(Directory directory, String path);
}

public class SizeCalculator implements FileSystemVisitor {
    private long totalSize = 0;
    
    @Override
    public void visit(File file, String path) {
        totalSize += file.getSize();
    }
    
    @Override
    public void visit(Directory directory, String path) {
        // Directories don't contribute to size in this model
    }
    
    public long getTotalSize() { return totalSize; }
}

public class DirectoryTraversal {
    public static void traverse(Directory dir, String path, FileSystemVisitor visitor) {
        visitor.visit(dir, path);
        for (INode node : dir.listEntries()) {
            String childPath = path + "/" + node.getName();
            if (node instanceof File) {
                visitor.visit((File) node, childPath);
            } else if (node instanceof Directory) {
                traverse((Directory) node, childPath, visitor);
            }
        }
    }
}

Compression Support

public class CompressedFile extends File {
    private final CompressionAlgorithm algorithm;
    private byte[] compressedContent;
    
    public CompressedFile(String name, String owner, CompressionAlgorithm algo) {
        super(name, owner);
        this.algorithm = algo;
    }
    
    @Override
    public byte[] read() {
        if (compressedContent != null) {
            return algorithm.decompress(compressedContent);
        }
        return super.read();
    }
    
    @Override
    public void write(byte[] data) {
        this.compressedContent = algorithm.compress(data);
        this.size = compressedContent.length;
        modify();
    }
}

public interface CompressionAlgorithm {
    byte[] compress(byte[] data);
    byte[] decompress(byte[] data);
}

public class ZipCompression implements CompressionAlgorithm {
    @Override
    public byte[] compress(byte[] data) {
        // ZIP compression implementation
        return data; // Placeholder
    }
    
    @Override
    public byte[] decompress(byte[] data) {
        return data; // Placeholder
    }
}

Journaling for Crash Recovery

public class Journal {
    private final List<JournalEntry> entries;
    private final String journalPath;
    
    public Journal(String path) {
        this.journalPath = path;
        this.entries = new ArrayList<>();
    }
    
    public void logOperation(Operation op) {
        entries.add(new JournalEntry(op, System.currentTimeMillis()));
        flush();
    }
    
    public void flush() {
        // Write journal entries to persistent storage
    }
    
    public void recover() {
        // Read journal and replay operations
        for (JournalEntry entry : entries) {
            entry.getOperation().execute();
        }
    }
}

public sealed interface Operation permits CreateFileOp, DeleteFileOp, WriteFileOp {
    void execute();
    void undo();
}

public record CreateFileOp(String path, String user) implements Operation {
    @Override
    public void execute() { /* create file */ }
    
    @Override
    public void undo() { /* delete file */ }
}

Thread Safety

public class ConcurrentFileSystem {
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    
    public File createFile(String path, String user) throws PermissionDeniedException {
        lock.writeLock().lock();
        try {
            // File creation logic
        } finally {
            lock.writeLock().unlock();
        }
    }
    
    public byte[] readFile(String path, String user) throws PermissionDeniedException {
        lock.readLock().lock();
        try {
            // Read logic
        } finally {
            lock.readLock().unlock();
        }
    }
}

Design Patterns Summary

Pattern	Usage
Composite	Files and Directories both implement INode interface
Visitor	Traversal operations (size calculation, search, etc.)
Strategy	Different file allocation algorithms
Proxy	Caching layer wraps filesystem operations
Decorator	CompressedFile extends File behavior
Command	Journal operations for undo/recovery

Complexity Analysis

Operation	Time Complexity
Path resolution	O(d) where d = depth
Create file	O(d) for path resolution + O(1) to add
Read file	O(d) for path resolution + O(1) for content
List directory	O(1) for map lookup
Find files	O(n) where n = total files
Copy directory	O(n) recursive copy

Interview Tips

• Start with the Composite pattern for INode hierarchy
• Discuss inode metadata early (permissions, timestamps, size)
• Mention file allocation strategies as a follow-up
• Be prepared to discuss caching strategies
• Consider concurrency and thread safety
• Show understanding of real-world file system concepts (inodes, journaling)