Simplifying a path

Question

Please be super brutal, and treat this as a top technical interview.

Worst case analysis: \$O(n)\$ (please confirm)

Space complexity: \$O(n)\$

Problem:

Given an absolute path for a file (Unix-style), simplify it.

For example:

path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"

Corner Cases: Did you consider the case where path = /../? In this case, you should return /. Another corner case is the path might contain multiple slashes / together, such as /home//foo/. In this case, you should ignore redundant slashes and return /home/foo.

My attempt:

private static String simplifyPath(String path) {
 Deque<String> pathDeterminer = new ArrayDeque<String>();
 String[] pathSplitter = path.split("/");
 StringBuilder absolutePath = new StringBuilder();
 for(String term : pathSplitter){
 if(term == null || term.length() == 0 || term.equals(".")){
 /*ignore these guys*/
 }else if(term.equals("..")){
 if(pathDeterminer.size() > 0){
 pathDeterminer.removeLast();
 }
 }else{
 pathDeterminer.addLast(term);
 }
 }
 if(pathDeterminer.isEmpty()){
 return "/";
 }
 while(! pathDeterminer.isEmpty()){
 absolutePath.insert(0, pathDeterminer.removeLast());
 absolutePath.insert(0, "/");
 }
 return absolutePath.toString();
 }

• Loki Astari: Have you though of 'cd /;cd ../../A/AA/' Where does that go? Or more specifically '/../../A/AA/'
• Loki Astari: Rather than build a string. Build an array of path segments. If you hit a path segment of '.' (or the empty segment) don't add it. If you hit a path segment of '..' pop the last element (if one exists). Once you have parsed all the path segments and added them to the array you can just pull them back together into a string.
• AaronM: It might be worth adding a pre-check for some of the cases you handle. I am thinking scanning the string for . or // before making any copies will give you a very quick return on paths that are not complex. Reading through a string is much faster than copying it every case.
• Marco13: Not sure what being "super brutal" means, but in an interview, I'd repsond to this with something based on URI.create(path).normalize().getPath()...

Answer 1

Within the limits of the instructions, this is a good solution, but could do with some tweaks.

I would start with challenging the assumptions a little bit. Even if you don't handle the odd cases, I would still mention them. The things I am think of, when I hear "Given an absolute path for a file (Unix-style)" are:

• escaped slashes path/to/file\/with\/slash.in.name
• well, that's about it, actually... other unix-like special cases probably would not affect this code.

So, I would probably handle the escaped-backslash, probably with a negative-look-behind on the split regex path.split("(?!\\\\)/")....

Then, I dislike the insert(0, ...) use of the StringBuilder. Because I know the internals of StringBuilder, I know that it is faster to append. I would treat the StringBuilder differently to you in 2 ways:

1. Set the initial size:

   StringBuilder absolutePath = new StringBuilder(path.length());
   

2. Append values from the other end of the Deque

   while(! pathDeterminer.isEmpty()){
    absolutePath.append("/");
    absolutePath.append(0, pathDeterminer.removeFirst());
   } 
   

Because your code uses the StringBuilder.insert(0, ...) mechanism, and because that is an \$O(n)\$ operation (because it has to move all the other characters that come after the inserted value), the overall complexity of the code is not \$O(n)\,ドル but rather \$O(n^2)\$. Changing to an append will bring the code back (closer) to \$O(n)\,ドル where each character is copied only once....

See the differences between:

• StringBuilder.append()
• StringBuilder.insert(0, ...)

• bazang: how does your stringbuilder approach improve performance?
• rolfl: Compare the insert logic which does a System.arrayCopy() to move the characters, to the append logic which does not. Essentially, the insert adds an order of complexity
• bazang: I did not know that, wow!

Answer 2

Overall, it is very easy to read and understand your code. I think that you make good choices of data structures.

A few things:

• I'm not very fond of your spacing formatting, but at least you're consistent which makes this a minor issue. I prefer, and the Java styling conventions is, while (!pathDeterminer.isEmpty()) {

• if(term == null will never happen. As pathSplitter is a String array acquired from using .split on a regular string, there will be no null entries in the array.

• term.length() == 0 and if(pathDeterminer.size() > 0){ - use .isEmpty() instead.

• /*ignore these guys*/ I would use a continue; to make it more clear that they really should be ignored, or use this:

  if (term.equals("..")) {
   if (!pathDeterminer.isEmpty())
   pathDeterminer.removeLast();
  }
  else if (!term.isEmpty() && !term.equals(".")) {
   pathDeterminer.addLast(term);
  }
  

Regarding the complexities: Yes, I agree that those are \$O(n)\$.

Answer 3

I would expect the function to work with either absolute or relative paths. If I pass it a relative path as a parameter, I expect a relative path returned.