Decode the Coding Interview in Scala: 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:

import scala.collection.mutable
import scala.collection.mutable.ListBuffer
object Main extends App{
  class TrieNode() {
    var nodes: Array[TrieNode] = new Array[TrieNode](26)
    var complete: Boolean = false
  }
  class FileSystem() {
    /** Initialize your data structure here. */
    var root = new TrieNode
    var canFind: Boolean = false
    /** Adds a word into the data structure. */
    def add(word: String): Unit = {
      val n = word.length
      var curNode = root
      var i = 0
      while ( {
        i < n
      }) {
        val index = word(i) - 'a'
        if (curNode.nodes(index) == null) curNode.nodes(index) = new Main.TrieNode
        curNode = curNode.nodes(index)
        if (i == n - 1) {
          if (curNode.complete == true) {
            println("Word already present")
            return
          }
          curNode.complete = true
        }
        i += 1
      }
    }
    def search(word: String): Boolean = {
      canFind = false
      dfs(root, word, 0)
      canFind
    }
    def dfs(r: TrieNode, w: String, _names: ListBuffer[String]): ListBuffer[String] = {
      var names = _names
      if (r == null) return names
      if (r.complete) names.addOne(w)
      var j = 'a'
      while ( {
        j <= 'z'
      }) {
        val n = w + j
        names = dfs(r.nodes((j - 'a').toChar), n, names)
        j = (j+ 1).toChar
      }
      names
    }
    
    def getAll: List[String] = {
      val names = new ListBuffer[String]
      if (root == null) return List("")
      dfs(root, "", names).toList
    }
    private def dfs(root: TrieNode, word: String, i: Int): Unit = {
      if (canFind) return
      if (root == null) return
      val n = word.length
      if (n == i) {
        if (root.complete) canFind = true
        return
      }
      if (word(i) == '.') {
        var j = 'a'
        while ( {
          j <= 'z'
        }) {
          dfs(root.nodes((j - 'a').toChar), word, i + 1)
          j = (j+1).toChar
        }
      }
      else {
        val index = word(i) - 'a'
        dfs(root.nodes(index), word, i + 1)
      }
    }
  }
  println("Initializing object")
  var obj = new FileSystem()
  println("Adding \'dir\' as a directory")
  obj.add("dir")
  println("Adding \'dir\' as a directory again")
  obj.add("dir")
  println("Adding \'dirr\' as a directory")
  obj.add("dirr")
  println("Adding \'file\' as a file")
  obj.add("file")
  println("Searching if \'.ile\' exists")
  println(obj.search(".ile"))
  println("Searching if \'..ile\' exists")
  println(obj.search("..ile"))
  println("Getting all of the files\\directories:")
  println(obj.getAll)
}
File Management System

Complexity measures

Time complexity Space complexity
add O(m)O(m)
...
Access this course and 1400+ top-rated courses and projects.