Grokking the Coding Interview: The Original Course
Vote

0% completed

​

Problem 6: Simplify Path (medium)

Problem Statement

Given an absolute file path in a Unix-style file system, simplify it by converting ".." to the previous directory and removing any "." or multiple slashes. The resulting string should represent the shortest absolute path.

Examples

Example 1

  • Input: path = "/a//b////c/d//././/.."
  • Expected Output: "/a/b/c"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • "." refers to the current directory and is ignored.
    • ".." moves up one directory, so "d" is removed.
    • The simplified path is "/a/b/c".

.....

.....

.....

Like the course? Get enrolled and start learning!
H

hahn.zachary

· 12 hours ago

I encountered a few issues with this problem:

  1. The problem statement states that multiple slashes should be removed but never states that file paths cannot end with a single slash. It also never states that file paths must begin with a single slash. The examples and test cases imply these rules, but they are never explicitly specified.
  2. One of the test cases uses an input of "/..." and expects an output of "/...". By both the stated and implied rules of this problem, I do not see how "/..." is a valid directory path. It's not even a valid directory path in real Unix-style file systems. I believe the expected output for an input of "/..." should be "/".
Gabriele Gennaro

Gabriele Gennaro

· 7 days ago

Inconsistent Guidance and Progression Across Coding Exercises

I’m leaving this feedback here, but it applies to several problems I’ve encountered so far. The exercises and proposed solutions don’t always feel consistent or progressively structured. In the stacks section, for example, it should be clear whether stacks are required only for the core algorithm and whether auxiliary arrays or built-in functions are allowed, especially when earlier exercises discouraged them.

Please distinguish the concept being practiced from the supporting tools we can use, and gradually reduce guidance, explicitly stating when we’re expected to choose the approach independently. Otherwise, it’s hard to tell whether I’m overlooking a solution or following restrictions that no longer apply.

Nikolay Danshin

Nikolay Danshin

· 3 months ago

i like my solution, kind of simple, understandable and fast:

class Solution:
    def simplifyPath(self, path):
        stack = []
        for c in path:
            if c == "/":
                while stack and (stack[-1] == "/" or stack[-1] == "."):
                    stack.pop()
                stack.append(c)
            elif c == ".":
                if stack and stack[-1] == ".": # .. command, moves up one directory
                    stack.pop()
                    if stack and stack[-1] == "/": 
                        stack.pop()
                    while stack and stack[-1] != "/":
                        stack.pop()
                else:
                    stack.append(c) # add ., maybe next . is .. command
            else:
                stack.append(c)

        #
Show 1 reply
K

krishi87

· 2 years ago

class Solution:
    def simplifyPath(self, path):
        stack = []
        for index in range(len(path)):
            char = path[index]
            if stack:
                if char == "." and index != len(path)-1 and path[index+1] == char:
                    # Go back a dir, pop twice
                    stack.pop()
                    if stack:
                        stack.pop() # Always check for underflow while popping
                elif char == "/" and ((index != len(path)-1 and path[index+1] == char) or stack[-1] == char): 
                    # Simplify // to / by not pushing anything to stack
                    continue
            if char not in ["."]:
                # Ignore . and push char to stack
                stack.append(char)
        return "".join(
Show 1 reply
Marie Arroyo

Marie Arroyo

· 2 years ago

As in, we go from step 4, to step 4. :)

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
    def simplifyPath(self, path):
        
        stack = []
        i = 0 
        temp = []  # for accumulating sub path characters like "foo/home". it stores foo and home

        while i < len(path):
            # if we have perviously accumulated path push it to the stack
            if path[i] == "/" and len(temp) > 0:
                stack.append(''.join(temp))
                temp = []

            # ".." case. pop the previous element
            elif path[i] == "." and len(stack) > 0 and stack[-1] == '.':
                stack.pop()
                if len(stack) > 0:
                    stack.pop()

            # "/." case. pop the "."
            elif path[i] == "/" and len(stack) > 0 and stack[-1] == '.':
                stack.pop()

            #
Show 1 reply
Renat Zamaletdinov

Renat Zamaletdinov

· 3 years ago

So I ended up with that awful, yet working solution

class Solution:
    def simplifyPath(self, path):
        stack = []
        l = len(path)
        i = 0

        while i < l:
            char = path[i]

            if char == '/':
                while stack and stack[-1] == '/':
                    stack.pop()
            elif char == '.':
                if i < l - 1 and path[i + 1] == '.':
                    if stack and stack[-1] == '/':
                        stack.pop()

                    while stack and stack[-1] != '/':
                        stack.pop()

            if char != '.':
                stack.append(char)
            i += 1

        while stack and stack[-1] == '/':
            stack.pop()

        if not stack:
            return '/'

        re
Show 1 reply
D

Davide Pugliese

· 3 years ago

In my view, even in Java, as for Python (where you have syntactic sugar like list comprehensions and tuple unpacking for example), the solution should leverage the language specific API.

In modern Java we don't use Stack anymore, so ArrayDeque should be used. In Java ArrayDeque is a double-ended queue that can be used to add elements to the head or to the tail and remove elements from the head and from the tail. Unlike LinkedList, ArrayDeque guarantees to retrieve the elements in the same order as they were entered when using an iterator (for loop).

import java.util.*;
import java.util.stream.*;
public class Solution {
    public String simplifyPath(String path) {
       Deque<String> stack = new ArrayDeque<>();
      
       var patWoSlash = path.split("/");
Show 1 reply
Yan Pomanitskiy (Pliant GmbH)

Yan Pomanitskiy (Pliant GmbH)

· 3 years ago

  • The stack is processed in LIFO (Last-In-First-Out) order. Each component is popped and appended to the start of the result string, preceded by "/".

This is a bit wrong.

The stack contains [a, b, c]. Using LIFO will create a string: /c/b/a

It should be noted that for-each uses internal array-based representation.

Show 3 replies
Maharshi Jinandra

Maharshi Jinandra

· 3 years ago

return join statement uses stack as array ....

Show 1 reply

Reading Progress

0%

Vote for new content