Simplifying a path

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 pathDeterminer = new ArrayDeque();
    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();
 }

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:

-
Set the initial size:

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

-
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, ...)

StackExchange Code Review Q#47923, answer score: 7