A deploy script built a chroot working directory by concatenating a prefix, an overlay from config, and a trailing slash the template always added. Staging used /opt/app/ and the binary started in the right tree. Production mixed .. climbs, doubled slashes from an empty overlay, and a . from a “current directory” placeholder. The intern looped replace("//", "/") until the string looked tidy. /opt/app/../var still contained .. after the slash pass, and the process started in the host /var instead of the jail.
Simplify Path asks you to collapse a Unix absolute path to its canonical form. Collapsing extra slashes uses that and still leaves . and .. in the string. A parent climb has to delete the previous directory, not rewrite two dots.
This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about the directories still live after . and .. so a parent climb is a pop, not a string splice.
The problem
Given a string path that is a Unix-style absolute path (it starts with /), return the simplified canonical path. The result starts with /, contains no . or .. segments, collapses repeated slashes, and has no trailing slash except for the root /. . means stay; .. means parent, and a climb at root is a no-op.
path = "/home//foo/" → "/home/foo"
path = "/../" → "/"
path = "/a/./b/../../c/" → "/c"
path = "/.../a/../b/c/../d/./" → "/.../b/d"Note: Only the whole tokens . and .. are special. ... is a legal directory name. A filename may contain dots (.hidden, ..bar); do not scan inside a segment. Empty tokens come from // and from the leading slash.
Repeated replace is the honest brute force
Collapsing // with replace is tempting and incomplete. replace("/../", "/") never deletes the parent. replace("..", "") is worse: it smashes ....
"/a/../b".replace("/../", "/") → "/a/b" wanted "/b"
"/.../".replace("..", "") → "/./" wanted "/..."The honest loop splices until the string stops changing: drop one extra /, drop one /./, or drop one /../ together with the segment before it. Pad a trailing / so a final .. still matches /../; each splice copies the string, so the walk is quadratic once the indices are right.
String simplifyPathReplace(String path) {
String cur = path.endsWith("/") ? path : path + "/";
boolean changed = true;
while (changed) {
changed = false;
int dbl = cur.indexOf("//");
if (dbl >= 0) {
cur = cur.substring(0, dbl) + cur.substring(dbl + 1);
changed = true;
continue;
}
int dot = cur.indexOf("/./");
if (dot >= 0) {
cur = cur.substring(0, dot) + cur.substring(dot + 2);
changed = true;
continue;
}
int up = cur.indexOf("/../");
if (up == 0) {
cur = cur.substring(3);
if (cur.isEmpty() || cur.charAt(0) != '/') {
cur = "/" + cur;
}
changed = true;
continue;
}
if (up > 0) {
int slash = cur.lastIndexOf('/', up - 1);
cur = cur.substring(0, slash) + cur.substring(up + 3);
changed = true;
}
}
if (cur.length() > 1 && cur.endsWith("/")) {
cur = cur.substring(0, cur.length() - 1);
}
return cur.isEmpty() ? "/" : cur;
}At n = 20 the copies are a rounding error. At n in the thousands you paid repeated splices for a question whose live directories are already the contents of a stack.
Split on slash, stack the live names
Split on / and walk the tokens: skip empty and ., pop on .. if the deque is non-empty — at root, stay at root; do not pop — and push every other name, including .... Join with / and prefix /; an empty deque is root. Walk a parent climb, a no-op at root, and ... as a name.
path = "/a/./b/../../c/"
split: "" a . b .. .. c
"" empty skip stack: []
a name push stack: [a]
. stay skip stack: [a]
b name push stack: [a b]
.. pop stack: [a]
.. pop stack: []
c name push stack: [c]
join → /c
path = "/../"
split: "" ..
"" skip stack: []
.. empty, stay at root stack: []
join → /
path = "/.../"
split: "" "..."
"" skip stack: []
"..." name push stack: ["..."]
join → /...The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack. addLast / removeLast keep iteration in path order so String.join is the answer.
String simplifyPath(String path) {
Deque<String> dirs = new ArrayDeque<>();
for (String seg : path.split("/")) {
if (seg.isEmpty() || seg.equals(".")) {
continue;
}
if (seg.equals("..")) {
if (!dirs.isEmpty()) {
dirs.removeLast();
}
continue;
}
dirs.addLast(seg);
}
if (dirs.isEmpty()) {
return "/";
}
return "/" + String.join("/", dirs);
}Time is O(n) — one split, one push or pop per token, one join. Space is O(n) for live names (worst case the path never climbs). Java split("/") drops trailing empty tokens; you already skip empties, so a trailing slash does not need a second pass.
Note: ArrayDeque.push inserts at the head. String.join would then emit the path backwards. That is why this walk uses addLast, not push. java.util.Stack is a synchronized Vector leftover — not the ADT, not the interview type.
What interviewers usually poke next
- Relative paths. No leading
/, and..that climbs above the start. The prompt is absolute; say so, then decide whether extra..stays in the result or is dropped. - Windows. Backslashes, drive letters, UNC prefixes. Out of scope for this Unix-token walk; do not start converting
\until they change the contract. - Symlinks. POSIX
..does not pop a symlink component the way a string stack pops a name. You need the real filesystem. Out of scope for the string problem. - Dots inside a name.
.hiddenand..barare ordinary directories. Only the whole tokens.and..are special;...stays. - In-place two pointers. Same skip/pop rules on a character array if they forbid the extra deque. The walk does not change.
You are done with this problem when you can skip empty and ., refuse to pop at root, leave ... as a name, and join with a leading /.