Longest absolute file path

Photo by Michael Dziedzic on Unsplash

Problem

The question gives us the input in the form of a file path

dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext

which represents the following

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The length of absolute length of the longest file path. This includes:

• string length
• \t length, each tab character is considered as 1 length unit

So for the above input example, the answer would be adding up the length of dir -> subdir2 -> file.txt

Solution

The directory structure looks like the classic folder structure on our laptops, where each file is nested under a folder and folders in turn can be in other folders/directory.

Before you run off to start parsing the string as a tree like structure, I’d urge you to hold-your-horses. There’s very less ROI (return on investment)

The files are located directly under the directory one level up, and each path is separated by \n.

So that’s our #1 hint. Process each path one by one — split by \n

pro-tip: \t and \n are single characters

If you’re to closely look at the file path, you get each level or nesting one by one. For example, the below path would be three separate strings and not one if you split by \n.

You get the level by counting the \t character.

The following should probably do it :P

• process all files
• calculate the length of each input (file or folder)
• keep track of the max length encountered so far
• count the characters in the filename
• add the length of parent folders

(cost calculation figure)

The below code is written in Go, as I wanted to learn this for a long time and this will probably teach me at least 10% :P

Go code is very terse, and readable like English

processing the input and splitting it by \n

cost of item = self cost + prev level cost

I’ll also have to store the cost of each level so that it can be used to calculate the cost of subsequent levels. (using a map)

In the above code, all the magic is in the line which calculates the cost

If you’re scratching your head and wondering what’s going on in there, let me break it down.

practise

• this problem can be practised at leetcode
• you can paste the code snippet to verify the solution works for all test cases!
• this was also featured in Daily Coding Problem series and was asked by Google as per them :P

Originally published at https://ankeetmaini.dev