Hope you had a nice Thanksgiving day with family and friends. My wife and I typically roast a turkey. This year, for the first time, we went with a fresh turkey breast. It was a fraction of the weight of a full turkey and when all was said and done, my wife did not have to deal with cleaning the bones. Today, and probably for the next few days, we will be having different types of turkey sandwiches (Bread, butter on the outside, panini press @ 350F, turkey meat. When brown and crunchy, open sandwich, apply mayonnaise and a touch of mustard. Close and enjoy).
In this post I will revisit solving LeetCode 388. Longest Absolute File Path. The motivation was a message I received a few days back on a solution in O(n). I looked up my solution in Java from February 27, 2017 and it was hard to follow. At the time I used a different plugin and the output was not that great. With time it stopped working so I switched to a different one. Much better but sometimes it mangles the output.
In this post I also decided in writing the same solution using C#. Many years ago, I developed a general purpose storage server. I chose to start using Windows and with time port it to Linux and Unix. I used C, C++, and the POSIX subsystem of Windows. In the years (18) the software was available to customers, we only ran into a single Windows update that caused a problem. The update was to the BIOS. It took me an hour to address the issue. I consider that most (never generalize) of the choices I made paid off with time.
At some point the requirements came up to allow C# applications / servers access the API for the storage server. I used the InteropServices to allow the C/C++ API be invoked by C# code. I recalled marshaling the arguments, making the API call, and unmarshaling the results. Wrote C# console programs to test the 60+ APIs we supported at the time. It all worked very well.
The company I started initially developed custom software for different clients. Learned a lot with such exposure using different programming languages (i.e., C#, Java, JavaScript, Python), tools and libraries.
Enough on the background, and let’s take a look at the problem at hand. The description follows:
Suppose we have a `file system` that stores both files and directories. An example of one system is represented in the following picture: dir \n \t subdir1 \n \t \t file1.ext \n \t \t subsubdir1 \n \t subdir2 \n \t \t subsubdir2 \n \t \t \t file2.ext Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext. In text form, it looks like this (with -> representing the tab character): dir \n \t subdir1 \n \t\t file1.ext \n \t\t subsubdir1 \n \t subdir2 \n \t\t subsubdir2 \n \t\t\t file2.ext input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" !!! NOTE !!! The spaces between the '\n' and '\t' characters are an artifact I introduced for a visual representation. The strings do not contain ' ' spaces. If we were to write this representation in code, it will look like this: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext". Note that the '\n' and '\t' are the new-line and tab characters. Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by '/'s. Using the above example, the absolute path to file2.ext is: "dir/subdir2/subsubdir2/file2.ext". Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces. Requirements: Given a string input representing the file system in the explained format, return the length of the longest absolute path to a `file` in the abstracted file system. If there is no file in the system, return 0. Note that the testcases are generated such that the file system is valid and no file or directory name has length 0. Constraints: o 1 <= input.length <= 10^4 o input may contain lowercase or uppercase English letters, a new line character '\n', a tab character '\t', a dot '.', a space ' ', and digits. o All file and directory names have positive length.
If you are interested in this problem, please visit the LeetCode site and get the current description for the problem Longest Absolute File Path. I am not sure if the requirements are adjusted with time, but it is a good practice to get the latest and greatest before spending time solving a problem.
The LeetCode site offers three test samples to help us understand the requirements. The examples follow:
Input: input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" Output: 20 Explanation: We have only one file, and the absolute path is "dir/subdir2/file.ext" of length 20. Input: input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" Output: 32 Explanation: We have two files: "dir/subdir1/file1.ext" of length 21 "dir/subdir2/subsubdir2/file2.ext" of length 32. We return 32 since it is the longest absolute path to a file. Input: input = "a" Output: 0 Explanation: We do not have any files, just a single directory named "a".
What we are supposed to do is populate a function that will take as input a line describing the contents of a file system and find the maximum (longest) length of an absolute path to a `file`.
For this post I used C# and Java programming languages. The code was implemented using Visual Studio Code (VSCode) and Microsoft Visual Studio Community 2022 (64-bit) running on a DELL computer.
The signature for the function of interest in Java follows:
class Solution {
public int lengthLongestPath(String input) {
}
}
At this time please take a few minutes reading the description of the file system. I will wait for you… OK, now that you are back, look at the sample strings. Note that directories do not include a ‘.’ which will help us differentiate a directory from a file.
Also note that each path component ends with a ‘\n’ (new line). Each level is indented with a ‘\t’ (tab). If you have a folder two levels in, the name of the file or folder should have two ‘\t’ characters preceding the name of the directory or the file. It is a good thing to go back and think about how the file system is laid out by each sample string. I will wait… OK, now let’s look at the output of my test scaffold.
lengthLongestPath <<< input ==>dir
subdir1
subdir2
file.ext<==
lengthLongestPath <<< p ==>dir<==
lengthLongestPath <<< level: 0
lengthLongestPath <<< length: 3
lengthLongestPath <<< stack: [0]
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< p ==> subdir1<==
lengthLongestPath <<< level: 1
lengthLongestPath <<< length: 7
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< p ==> subdir2<==
lengthLongestPath <<< level: 1
lengthLongestPath <<< length: 7
lengthLongestPath <<< popped: 12
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< p ==> file.ext<==
lengthLongestPath <<< level: 2
lengthLongestPath <<< length: 8
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< maxLen: 20
main <<< maxLen: 20
lengthLongestPath <<< input ==>dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext<==
lengthLongestPath <<< p ==>dir<==
lengthLongestPath <<< level: 0
lengthLongestPath <<< length: 3
lengthLongestPath <<< stack: [0]
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< p ==> subdir1<==
lengthLongestPath <<< level: 1
lengthLongestPath <<< length: 7
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< p ==> file1.ext<==
lengthLongestPath <<< level: 2
lengthLongestPath <<< length: 9
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< maxLen: 21
lengthLongestPath <<< p ==> subsubdir1<==
lengthLongestPath <<< level: 2
lengthLongestPath <<< length: 10
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< stack: [0, 4, 12, 23]
lengthLongestPath <<< p ==> subdir2<==
lengthLongestPath <<< level: 1
lengthLongestPath <<< length: 7
lengthLongestPath <<< popped: 23
lengthLongestPath <<< popped: 12
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< p ==> subsubdir2<==
lengthLongestPath <<< level: 2
lengthLongestPath <<< length: 10
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< stack: [0, 4, 12, 23]
lengthLongestPath <<< p ==> file2.ext<==
lengthLongestPath <<< level: 3
lengthLongestPath <<< length: 9
lengthLongestPath <<< stack: [0, 4, 12, 23]
lengthLongestPath <<< maxLen: 32
main <<< maxLen: 32
lengthLongestPath <<< input ==>a<==
lengthLongestPath <<< p ==>a<==
lengthLongestPath <<< level: 0
lengthLongestPath <<< length: 1
lengthLongestPath <<< stack: [0]
lengthLongestPath <<< stack: [0, 2]
main <<< maxLen: 0
lengthLongestPath <<< input ==>dir
subdir1
subdir2
file.ext<==
lengthLongestPath <<< p ==>dir<==
lengthLongestPath <<< level: 0
lengthLongestPath <<< length: 3
lengthLongestPath <<< stack: [0]
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< p ==> subdir1<==
lengthLongestPath <<< level: 1
lengthLongestPath <<< length: 7
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< p ==> subdir2<==
lengthLongestPath <<< level: 1
lengthLongestPath <<< length: 7
lengthLongestPath <<< popped: 12
lengthLongestPath <<< stack: [0, 4]
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< p ==> file.ext<==
lengthLongestPath <<< level: 2
lengthLongestPath <<< length: 8
lengthLongestPath <<< stack: [0, 4, 12]
lengthLongestPath <<< maxLen: 20
main <<< maxLen: 20
You might note that I did not provide input to the program. The test strings are embedded in the test scaffold. For simplicity and efficiency, from now on, I decided to embed the input strings into the test scaffold.
Each test case (I have four; the first three are from the problem definitions, the fourth is from a test case that failed earlier on the development and testing), we start by displaying the input string. This offers an opportunity to look at a glance how the file system is laid out.
The rest of the lines are also for debugging purposes and for us to be able to follow the solution. I removed all the messages from the code before posting solutions in the LeetCode site.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
int n = 4;
// **** populate array of test cases ****
String[] testCases = new String[n];
testCases[0] = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
testCases[1] = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
testCases[2] = "a";
testCases[3] = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
// **** run all test cases ****
for (String testCase : testCases) {
// **** compute the max length ****
int maxLen = lengthLongestPath(testCase);
// **** display the max length ****
System.out.println("main <<< maxLen: " + maxLen + "\n");
}
}
This is the test scaffold for this problem. We start by defining a String array holding the four test cases. We then enter a loop and call the function of interest with a string holding the test case. The result is then displayed.
I always develop code using a Test Driven Development (TDD) approach. Note that there are no unit tests. They should be generated after the code is completed.
/**
* Longest Absolute File Path.
* Execution: O(n) - Space: O(n)
* @param input
* @return
*/
static int lengthLongestPath(String input) {
// **** initialization ****
int maxLen = 0;
Stack<Integer> stack = new Stack<Integer>();
stack.push(maxLen);
// ???? ????
System.out.println("lengthLongestPath <<< input ==>" + input + "<==");
// **** loop once per path (a path could be a directory or a file) ****
for (String p : input.split("\n")) {
// ???? ????
System.out.println("lengthLongestPath <<< p ==>" + p + "<==");
// **** compute the path level ****
int level = p.lastIndexOf("\t");
level++;
// ???? ????
System.out.println("lengthLongestPath <<< level: " + level);
// **** compute the length of this path ****
int length = p.length();
length -= level;
// ???? ????
System.out.println("lengthLongestPath <<< length: " + length);
// **** adjust the stack (if needed) ****
while (stack.size() > level + 1) {
// **** ****
int popped = stack.pop();
// ???? ?????
System.out.println("lengthLongestPath <<< popped: " + popped);
}
// ???? ????
System.out.println("lengthLongestPath <<< stack: " + stack.toString());
// **** p is a file ****
if (p.contains(".")) {
// **** max length including this path ****
maxLen = Math.max(maxLen, stack.peek() + length);
// ???? ????
System.out.println("lengthLongestPath <<< maxLen: " + maxLen);
}
// **** p is a directory ****
else {
// **** save it's length + '/' ****
stack.push(stack.peek() + length + 1);
// ???? ????
System.out.println("lengthLongestPath <<< stack: " + stack.toString());
}
}
// **** return the length of the max path of a file ****
return maxLen;
}
The function starts by declaring and initializing some variables. The result will be returned in the maxLen. A stack will be used to keep track of the different lengths of the intermediate paths including the ‘/’ separator.
We process each path by splitting the input string.
We compute the level of the path held in the p string variable. The root is at level zero (0) and each subdirectory is at a larger level.
We then compute the length of the current path.
The contents of the stack are then adjusted. Note that at the end of each file or folder we might need to remove the lengths of previous paths. Keep in mind that the stack is used to keep the length of the current path. The maximum length is kept in the maxLen variable.
If we are dealing with a file the maxLen variable is updated; otherwise the contents of the stack are updated.
After all the paths are processed the maxLen is returned as our solution.
Now that we are done with the Java implementation we will replicate it using C#.
public class Solution {
public int LengthLongestPath(string input) {
}
}
The signature for the function of interest, as expected, is quite similar to the Java implementation.
LengthLongestPath <<< input ==>dir
subdir1
subdir2
file.ext<==
LengthLongestPath <<< p ==>dir<==
LengthLongestPath <<< level: 0
LengthLongestPath <<< length: 3
LengthLongestPath <<< stack: 0
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< p ==> subdir1<==
LengthLongestPath <<< level: 1
LengthLongestPath <<< length: 7
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< p ==> subdir2<==
LengthLongestPath <<< level: 1
LengthLongestPath <<< length: 7
LengthLongestPath <<< popped: 12
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< p ==> file.ext<==
LengthLongestPath <<< level: 2
LengthLongestPath <<< length: 8
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< maxLen: 20
Main <<< maxLen: 20
LengthLongestPath <<< input ==>dir
subdir1
file1.ext
subsubdir1
subdir2
subsubdir2
file2.ext<==
LengthLongestPath <<< p ==>dir<==
LengthLongestPath <<< level: 0
LengthLongestPath <<< length: 3
LengthLongestPath <<< stack: 0
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< p ==> subdir1<==
LengthLongestPath <<< level: 1
LengthLongestPath <<< length: 7
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< p ==> file1.ext<==
LengthLongestPath <<< level: 2
LengthLongestPath <<< length: 9
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< maxLen: 21
LengthLongestPath <<< p ==> subsubdir1<==
LengthLongestPath <<< level: 2
LengthLongestPath <<< length: 10
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< stack: 23 12 4 0
LengthLongestPath <<< p ==> subdir2<==
LengthLongestPath <<< level: 1
LengthLongestPath <<< length: 7
LengthLongestPath <<< popped: 23
LengthLongestPath <<< popped: 12
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< p ==> subsubdir2<==
LengthLongestPath <<< level: 2
LengthLongestPath <<< length: 10
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< stack: 23 12 4 0
LengthLongestPath <<< p ==> file2.ext<==
LengthLongestPath <<< level: 3
LengthLongestPath <<< length: 9
LengthLongestPath <<< stack: 23 12 4 0
LengthLongestPath <<< maxLen: 32
Main <<< maxLen: 32
LengthLongestPath <<< input ==>a<==
LengthLongestPath <<< p ==>a<==
LengthLongestPath <<< level: 0
LengthLongestPath <<< length: 1
LengthLongestPath <<< stack: 0
LengthLongestPath <<< stack: 2 0
Main <<< maxLen: 0
LengthLongestPath <<< input ==>dir
subdir1
subdir2
file.ext<==
LengthLongestPath <<< p ==>dir<==
LengthLongestPath <<< level: 0
LengthLongestPath <<< length: 3
LengthLongestPath <<< stack: 0
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< p ==> subdir1<==
LengthLongestPath <<< level: 1
LengthLongestPath <<< length: 7
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< p ==> subdir2<==
LengthLongestPath <<< level: 1
LengthLongestPath <<< length: 7
LengthLongestPath <<< popped: 12
LengthLongestPath <<< stack: 4 0
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< p ==> file.ext<==
LengthLongestPath <<< level: 2
LengthLongestPath <<< length: 8
LengthLongestPath <<< stack: 12 4 0
LengthLongestPath <<< maxLen: 20
Main <<< maxLen: 20
Main >>> press <Enter> to exit:
The screen capture for the output of the C# implementation is as expected, quite similar to the one generated by the Java version.
/// <summary>
/// Test scaffold.
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
// **** test cases ****
String[] testCases = new String[4];
testCases[0] = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
testCases[1] = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
testCases[2] = "a";
testCases[3] = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
// **** run all test cases ****
foreach (String testCase in testCases)
{
// **** compute result ****
var maxLen = LengthLongestPath(testCase);
// **** display result ****
Console.WriteLine("Main <<< maxLen: {0}\n", maxLen);
}
// ???? ????
Console.Write("Main >>> press <Enter> to exit: ");
Console.ReadLine();
}
The test scaffold in C# follows closely the implementation of the Java version. I declare an array of four strings and assign the test case strings. The code then loops through the array calling the function of interest and displaying the associated result.
/// <summary>
///
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static int LengthLongestPath(String input)
{
// **** initialization ****
int maxLen = 0;
Stack<int> stack = new Stack<int>();
stack.Push(maxLen);
// ???? ????
Console.WriteLine("LengthLongestPath <<< input ==>{0}<==", input);
// **** ****
foreach (var p in input.Split('\n')) {
// ???? ????
Console.WriteLine("LengthLongestPath <<< p ==>{0}<==", p);
// **** compute the path level ****
var level = p.LastIndexOf('\t');
level++;
// ???? ????
Console.WriteLine("LengthLongestPath <<< level: {0}", level);
// **** compute the length of this path ****
var length = p.Length;
length -= level;
// ???? ????
Console.WriteLine("LengthLongestPath <<< length: {0}", length);
// **** adjust the stack (if needed) ****
while (stack.Count > level + 1)
{
var popped = stack.Pop();
// ???? ????
Console.WriteLine("LengthLongestPath <<< popped: {0}", popped);
}
// ???? very cumbersome ????
Console.Write("LengthLongestPath <<< stack: ");
foreach (var se in stack)
Console.Write("{0} ", se);
Console.WriteLine();
// **** p is a file ****
if (p.Contains("."))
{
maxLen = Math.Max(maxLen, stack.Peek() + length);
// ???? ????
Console.WriteLine("LengthLongestPath <<< maxLen: {0}", maxLen);
}
// **** p is a directory ****
else
{
stack.Push(stack.Peek() + length + 1);
// ???? very cumbersome ????
Console.Write("LengthLongestPath <<< stack: ");
foreach (var se in stack)
Console.Write("{0} ", se);
Console.WriteLine();
}
}
// **** return max length ****
return maxLen;
}
The implementation of the function of interest in C# is quite similar to the one for Java. Note that some extra steps are taken to display intermediate results. For example, when the stack is adjusted the value popped is captured to be able to be displayed. When removing the line that generates output the need for the var popped variable disappears. That can help reduce the number of lines of code yet allows us to maintain a well documented function. No one knows when changes might be needed to improve execution time or modify the code to add functionality (e.g., display not only the maximum length but the actual full path). You or perhaps a different developer could be assigned to make the changes. Being able to understand the current version in the least possible time helps with velocity.
Moving forward I will be using more often C# to solve problems and illustrate algorithms and tools.
The code for this post is available in GitHub at JohnCanessa/LongestAbsoluteFilePath.
If you have comments or questions please feel free to leave a comment below. Will respond as soon as possible.
Enjoy,
John