Decode the Coding Interview in Rust: Real-World Examples/

...

/

Feature #6: File Management System

Feature #6: File Management System

Implement the "File Management System" feature for our "Operating System" project.

We'll cover the following...

Description

In this feature, we will make a file management system that will maintain a file system index. We want to allow the user to conduct searches with an optional wildcard character, ., which matches any single character. For example, . in the string .ata can have 26 possible search results like aata, bata, cata, and so on. We must keep in mind while searching that if the searched word matches some part of an already added file or directory then it should return false.

For this feature, the target is to have a data structure that will:

  • Add a file or directory name in the data structure. A file or directory name can be added only once. It must not allow two files with the same name. Keep in mind that file and directory names are case-sensitive.
  • Perform wildcard searches. The search should return false if the word is not found in the file system. Otherwise, the search should return true.
  • Return a list of all the files and directories in the data structure.

Let’s take a look at how we can add, search, and get all the files and directory names with the help of the following example:

Solution

For this solution, we will make a trie, which is a hashmap. A trie is a useful data structure that is used to match exactly and conduct wildcard matches for words. Each node in it is a data structure, TrieNode, which has the following variables:

  • nodes: This is an array of length 26. Each index of this array corresponds to a letter of the English alphabet.
  • complete: This variable takes a boolean value. The value will be true if the node represents the last character of the file or directory name. Otherwise, it will be false.

While adding a file or directory we will verify, at each step, if the child node that needs to be added is already present. If it is already present, then we will just go down one step. If it is not already present, then we will add the child node into the trie and go down one step. A file or directory name must only be added once.

For searches, there are two possibilities:

  • In the absence of the . character, the search will be as simple as the add feature. Each key in the trie is represented as a path from the root node. In this type of search, we start from the root and go down the trie, checking character by character.
  • When the current character is a ., we will match against all the children of the current TrieNode.

Here is how both the features will look:

Let’s take a look at the code for the solution:

Press + to interact
main.rs
TrieNodes.rs
#[derive(Default,Debug, PartialEq, Eq, Clone)]
pub struct FileSystem{
  pub canFind: bool,
  pub root: TrieNode
}
impl FileSystem {
  fn new() -> Self {
        Default::default()
    }
   pub fn dfs(&mut self, r: Option<Box<TrieNode>>, w: String, names:&mut Vec<String>)-> Vec<String> {
        if r.is_none() {return names.to_vec()};
        if r.clone().unwrap().complete {
            names.push(w.to_string());
        }
        let mut j = 'a' as u8;
        while j  <= 'z' as u8{
            let n = format!("{}{:}",w,j as char);
            *names = self.dfs(r.clone().unwrap().nodes[(j  - 'a' as u8) as usize].clone(), n.to_string(),&mut names.to_vec()); 
            j  +=1;
        }
        return names.to_vec();
    }
    pub fn getAll(&mut self)-> Vec<String> {
        let mut names: Vec<String> = Vec::new();
        if Some(self.root.clone()).is_none()
           { return vec![];}
        return self.dfs(Some(Box::new(self.root.clone())), "".to_string(),&mut names);
    }
  pub fn add(&mut self,word: String) {
        let n = word.len();
        let mut currNode=  &mut self.root;
        let mut i =0;
        for &c in word.as_bytes() {
            currNode = currNode.nodes[(c - b'a') as usize].get_or_insert(Box::new(Default::default()));
            if i == n - 1 {
                if currNode.complete == true{
                    println!("Word already present" );
                    return;
                }
                currNode.complete = true;
            }
            i+=1;
        }
    }
    pub fn search(&mut self, word: String)-> bool {
        self.canFind = false;
        self.dfs2(Some(Box::new(self.root.clone())), word, 0);
        return self.canFind;
    }
    pub fn dfs2(&mut self, root: Option<Box<TrieNode>>, word: String, i: i32) {
        if self.canFind {return};
        if root.is_none() {return};
        let n = word.len();
        if n == i as usize{
            if root.unwrap().complete {
                self.canFind = true;
            }
            return;
        }
        if word.chars().nth(i as usize).unwrap() == '.' {
            let mut j = 'a' as u32;
            while j <= 'z' as u32{
                self.dfs2(root.clone().unwrap().nodes[(j - 'a' as u32) as usize].clone(), word.to_string(), i + 1); 
                j +=1;
            }
        } else {
            let index = word.chars().nth(i as usize).unwrap() as u32 - 'a' as u32;
            self.dfs2(root.clone().unwrap().nodes[index as usize].clone(), word.to_string(), i + 1);
        }
    }
}
fn main() {
    println!("Initializing fsect" );
    let mut fs = FileSystem::new();
    println!("Adding \'dir\' as a directory" );
    fs.add("dir".to_string());
    println!("Adding \'dir\' as a directory again" );
    fs.add("dir".to_string());
    println!("Adding \'dirr\' as a directory");
    fs.add("dirr".to_string());
    println!("Adding \'file\' as a file");
    fs.add("file".to_string());
    println!("Searching if \'.ile\' exists" );
    println!("{:?}",fs.search(".ile".to_string()));
    println!("Searching if \'..ile\' exists" );
    println!("{:?}",fs.search("..ile".to_string()));
    println!("Getting all of the files\\directories:" );
    let result = fs.getAll();
     println!("{:?}",result);
    
}

Complexity measures

Time complexity Space complexity
add O(m)O(m)
...