Canonicalize an Absolute Unix-Style Path With Dot and Double-Dot Segments
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an absolute path in a Unix-style file system, return its simplified canonical form.
### Function Signature
```python
def simplify_path(path: str) -> str:
```
### Rules
Interpreting the input:
- `path` starts with `/`.
- A single period `.` refers to the current directory and is dropped.
- A double period `..` moves up to the parent directory; at the root it stays at the root.
- Several consecutive slashes (for example `//`) act as a single slash.
- Any other sequence of characters between slashes is a directory or file name, including sequences of three or more periods such as `...`.
The canonical output:
- starts with a single `/`;
- separates names with exactly one `/`;
- has no trailing `/` unless the result is the root `/` itself;
- contains no `.` or `..` components.
### Constraints
- `1 <= len(path) <= 3000`
- `path` consists of English letters, digits, `.`, `/`, and `_`.
- `path` is a valid absolute Unix path.
### Examples
**Example 1**
Input: `path = "/home//foo/"`
Output: `"/home/foo"`
Explanation: the double slash collapses to one and the trailing slash is removed.
**Example 2**
Input: `path = "/../"`
Output: `"/"`
Explanation: moving up from the root stays at the root.
**Example 3**
Input: `path = "/.../a/../b/c/../d/./"`
Output: `"/.../b/d"`
Explanation: `...` is an ordinary name; `a/..` and `c/..` cancel out, and `.` is dropped.
Overview: Convert an absolute Unix-style file path into its canonical form by collapsing repeated slashes, dropping single-dot segments, resolving double-dot segments against the parent directory, and treating other dot sequences as ordinary names. It tests careful string parsing and edge cases such as the root directory.
You are given `path`, an absolute path in a Unix-style file system. Return its simplified canonical form as a string.
### Interpreting the input
- `path` starts with `/`.
- A single period `.` refers to the current directory and is dropped.
- A double period `..` moves up to the parent directory; at the root it stays at the root.
- Several consecutive slashes (for example `//`) act as a single slash.
- Any other sequence of characters between slashes is a directory or file name, including sequences of three or more periods such as `...`.
### The canonical output
- starts with a single `/`;
- separates names with exactly one `/`;
- has no trailing `/` unless the result is the root `/` itself;
- contains no `.` or `..` components.
### Function
`simplify_path(path)` receives `path` as a string and returns the canonical path as a string.
### Examples
**Example 1**
Input: `path = "/home//foo/"`
Output: `"/home/foo"`
Explanation: the double slash collapses to one and the trailing slash is removed.
**Example 2**
Input: `path = "/.../a/../b/c/../d/./"`
Output: `"/.../b/d"`
Explanation: `...` is an ordinary name; `a/..` and `c/..` cancel out, and `.` is dropped.
### Constraints
- `1 <= len(path) <= 3000`
- `path` consists of English letters, digits, `.`, `/`, and `_`.
- `path` is a valid absolute Unix path.
Constraints
- 1 <= len(path) <= 3000
- path consists of English letters, digits, '.', '/', and '_'.
- path is a valid absolute Unix path and starts with '/'.
Examples
Input: ('/home//foo/',)
Expected Output: '/home/foo'
Explanation: Source example 1: the double slash collapses and the trailing slash is removed.
Input: ('/../',)
Expected Output: '/'
Explanation: Source example 2: moving up from the root stays at the root.
Hints
- Only a component that is exactly '.' or exactly '..' is special; '...', '.a', 'a..' and similar pieces are ordinary names.
- A '..' cancels only the most recently kept name, and has no effect once you are back at the root.
- Repeated slashes and a trailing slash never contribute a component of their own, so the answer depends only on the non-empty pieces between slashes.