Decode the Coding Interview in Elixir: 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 a hashmap that will be used for storing the letters 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.exs
TrieNode.ex
defmodule FileSystem do
    defstruct root: TrieNode.init, can_find: false
    def init, do: %__MODULE__{}
    def get_all(obj) do
      names = Arrays.new([])
      if obj.root == nil, do: [], else: dfs(obj.root, "", names) |> Arrays.to_list
    end
    def dfs(nil, _word, names), do: names
    def dfs(node, word, names) do
      names = if node.complete == true, do: Arrays.append(names, word), else: names
      ?a..?z
      |> Enum.to_list
      |> Enum.reduce(names, fn(j, names) -> 
        n = word <> <<j>>
        dfs(node.nodes[<<j>>], n, names)
      end)
    end
    defp node_creater_getter(curr_node, key) do
      curr_node.nodes 
      |> Map.put_new(key, TrieNode.init) 
      |> Map.get(key)
    end
    def add(curr_node, [], _i, _n), do: %TrieNode{curr_node | complete: true}
    def add(curr_node, [head | tail], i, n) do
      child = node_creater_getter(curr_node, head)
      child = add(child, tail, i+1, n)
      %TrieNode{curr_node | nodes: Map.put(curr_node.nodes, head, child)}
    end
    def add(obj, word) do
      curr_node = obj.root
      n = byte_size(word)
      word_list = word |> String.graphemes
      %__MODULE__{obj | root: add(curr_node, word_list, 0, n)}
    end
    defp depth_first_search([], node), do: node.complete
    defp depth_first_search([first | tail], node) do
      cond do
        String.equivalent?(first, ".") ->
          node.nodes 
          |> Enum.any?(fn {_, v} -> depth_first_search(tail, v) end)
        true ->
          if !Map.has_key?(node.nodes, first), do: false, else: depth_first_search(tail, node.nodes[first])
      end
    end
    def search(obj, word) do
      node = obj.root
      word |> String.graphemes |> depth_first_search(node)
    end
end
# FileSystem()
IO.puts "-----------------------------"
IO.puts "PROGRAM OUTPUT:\n"
IO.puts "Initializing object"
obj = FileSystem.init
IO.puts "add_wording \'dir\' as a directory"
obj = obj |> FileSystem.add("dir")
IO.puts "add_wording \'dir\' as a directory again"
obj = obj |> FileSystem.add("dir")
IO.puts "add_wording \'dirr\' as a directory"
obj = obj |> FileSystem.add("dirr")
IO.puts "add_wording \'file\' as a directory"
obj = obj |> FileSystem.add("file")
# IO.inspect obj
IO.puts "Searching if \'.ile\' exists"
IO.inspect obj |> FileSystem.search(".ile")
IO.puts "Searching if \'..ile\' exists"
IO.inspect obj |> FileSystem.search("..ile")
IO.puts "Getting all of the files\\directories:"
IO.inspect obj |> FileSystem.get_all()

Complexity measures

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