Compute Entity Size and Validate a Hierarchical File System

Question

This question asks the candidate to compute the total size of a specified entity within a hierarchical file system and to validate the structure of the file system itself.

Codemia · Accepted Answer

To solve this problem, we need to compute the total size of a given entity (either a file or a directory) in a hierarchical file system. Additionally, we need to validate that the file system adheres to the expected structure, ensuring that directories contain valid files or subdirectories.

We can represent the file system using classes for `File` and `Directory`. Each `File` has a size attribute, while each `Directory` contains a list of files and subdirectories. The main functions will include:
1. A method to compute the total size of an entity.
2. A method to validate the file system structure.

The computation of the total size can be done using a recursive function. For a file, we simply return its size. For a directory, we iterate through its contents, summing the sizes of files and recursively calling the function for subdirectories. Here's a sample implementation in Python:

```python
class File:
    def __init__(self, size):
        self.size = size

class Directory:
    def __init__(self):
        self.contents = []

def add(self, entity):
        self.contents.append(entity)

def compute_size(entity):
    if isinstance(entity, File):
        return entity.size
    elif isinstance(entity, Directory):
        total_size = 0
        for item in entity.contents:
            total_size += compute_size(item)
        return total_size
    return 0
```

For validation, we can check that each directory only contains valid files or directories.

This approach is straightforward and works well for small to medium-sized file systems. However, for very large file systems, we might encounter performance issues due to deep recursion. An iterative approach using a stack could be considered to avoid stack overflow errors. Additionally, ensuring that the file system does not contain circular references is crucial for validation, which can be handled using a set to track visited directories.

Compute Entity Size and Validate a Hierarchical File System

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Google 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