Coding Challenge: Finding the Longest Absolute Path in an Abstracted File System Display

Lately I've been trying to challenge myself by taking a stab at some common coding questions asked in software engineering job interviews. After years of working on apps you would think that this kind of thing comes easy, but software development in the modern age comes with a heavy side of Googling and lookup, and very few truly unique problems, so challenging your brain in this way is good practice to keep you sharp.

I've been working lately on LeetCode and came across this interesting problem titled Longest Absolute File Path. The problem gives us an abstracted, serialized representation of a file system directory structure, and asks us to find the longest absolute file name in the system.

In this representation, each \n represents the end of line (dir or file), and each \t corresponds to the files depth in the system, though there is no information one can deduce about its path to get to that depth. For example, this string…

"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"

…actually maps to a directory that graphically looks like this:

dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext

In this case, the longest length absolute file path would be dir/subdir2/subsubdir2/file2.ext with a length of 32.

We've been asked to solve the problem with O(n) time complexity. We are told that directory names will not have a . in them, and every file will.

Full disclosure:I didn't solve this problem in a reasonable time. When I first read it, I somehow dove in head first to the deep end by deciding that I should build a directory tree using nodes and children lists, then I would do a DFS search hitting every node on the tree, calculating while searching. I missed the O(n) time complexity requirement and I wasted a bunch of time writing code to build a tree unnecessarily. I did end up solving the question with all tests passing however, not just in the allotted time. Here's how I did it.

The first thing we need to do is to get a list of all directories and files. We can do this by splitting the original string on the newlines: \n

# @param {String} input
# @return {Integer}
def length_longest_path(input)
  all_dirs_and_files = input.split("\n")
end

Because it is O(n), we need to check each file, and keep track of the longest along the way. So we add a longest variable which will hold the return value. We also need a way to keep track of where we are in the directory structure. For example, if we find file1.ext, and we need to know the length of the absolute path to this file, we are going to need the names of the directories above it. The way to do this is by maintaining a dir_stack array that we can push or pop to. And with that setup, we will want to iterate over the directories and files and inspect each one, storing it in an iterative current variable.

def length_longest_path(input)
  longest = 0
  dir_stack = []

  all_dirs_and_files = input.split("\n")
  all_dirs_and_files.each do |current|

  end
  longest
end

Now that we have this framework setup, let's write some helpers to determine a few things. We will need to know whether any given String in all_dirs_and_files is a file or a directory. We also will need to know the depth of any given file. The rules on those are given with the problem and are simple to implement:

def file?(s)
  s.include? '.'
end

def depth(s)
  s.scan(/\t/).count
end

For file?, we simply take the String s and check if it has a . or not. Perhaps it didn't need a helper, but if the representation ever became more complex, implementing the . or .. directory links, we could add that logic here. The depth method simply scans the string for all occurrences of \t and counts them. Thus, if we don't see any, we are at root level (depth: 1), and if we see two (depth: 2), then we know there are 2 directories above that file.

The pseudocode for each iteration looks like this:

if the current item is a file
  find out how deep in the file system it is,
  look at that many elements in the beginning of the stack,
  cleanup the names and add them together to get a length
  if the length is longer than the longest we have seen
    update it
else it must be a directory so
  find out how deep in the file system it is,
  put the directory in its correct place on the stack

In ruby code, this leads to the following lines:

if file?(current)
  d = depth(current)
  parents = dir_stack.take(d)
  path = (parents + [current]).join('/').gsub(/\t/,'')
  length = path.length
  longest = length if length > longest
else
  d = depth(current)
  dir_stack[d] = current
end

Cleaning it up a bit and combining with the rest of the code we have:

# @param {String} input
# @return {Integer}
def length_longest_path(input)
  longest = 0
  dir_stack = []

  all_dirs_and_files = input.split("\n")
  all_dirs_and_files.each do |current|
    d = depth(current)

    if file?(current)
      path = (dir_stack.take(d) + [current]).join('/').gsub(/\t/,'')
      length = path.length
      longest = length if length > longest
    else
      dir_stack[d] = current
    end
  end

  longest
end

And running our test string through gives up correct results:

>> length_longest_path "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
=> 32

I know the code is correct because it passes all of LeetCode's tests, so I won't bother coming up with other example tests here. It's O(n) because we are looping through the entire array, but only once. Do you see a simpler or faster way to accomplish this? Let me know in the comments.

Was this page helpful for you? Buy me a slice of 🍕 to say thanks!