Longest absolute file path
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