Implement cd and merge intervals
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem 1: Implement a simplified `cd` command
You are given:
- `cwd`: the current working directory as an absolute Unix path (starts with `/`).
- `path`: a target path that may be absolute (starts with `/`) or relative.
Implement the behavior of a simplified Linux `cd` command and return the resulting **normalized absolute path**.
Normalization rules:
- `.` means “stay in the same directory”.
- `..` means “go to parent directory” (if already at `/`, stay at `/`).
- Multiple consecutive slashes should be treated as a single separator.
- The output must:
- start with `/`
- not end with `/` unless the path is exactly `/`
**Input:** `cwd` (string), `path` (string)
**Output:** normalized absolute path (string)
**Examples**
- `cwd = "/a/b"`, `path = "../c"` → `"/a/c"`
- `cwd = "/"`, `path = "../../x"` → `"/x"`
- `cwd = "/a/b"`, `path = "/d//e/./f/.."` → `"/d/e"`
---
## Problem 2: Merge overlapping intervals
You are given a list of intervals `intervals`, where each interval is `[start, end]` (inclusive) and `start <= end`.
Merge all intervals that overlap and return a list of the merged, non-overlapping intervals that cover the same ranges.
Two intervals overlap if they share any point, i.e., `[a, b]` and `[c, d]` overlap when `c <= b`.
**Input:** `intervals: List[List[int]]`
**Output:** merged intervals (in any order, or sorted by start—specify which you choose)
**Examples**
- `[[1,3],[2,6],[8,10],[15,18]]` → `[[1,6],[8,10],[15,18]]`
- `[[1,4],[4,5]]` → `[[1,5]]`
**Constraints (typical):**
- `1 <= len(intervals) <= 10^5`
- interval endpoints fit in 32-bit integers
Quick Answer: This question evaluates proficiency in filesystem path normalization (string parsing, tokenization, and edge-case handling) and interval-merging algorithms (sorting, range consolidation, and handling overlaps), testing skills in string manipulation, data structures, and algorithmic reasoning.
Simplified cd Path Normalization
Given an absolute cwd and a relative or absolute path, return the normalized absolute Unix path.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('/a/b', '../c')
Expected Output: '/a/c'
Explanation: Prompt example.
Input: ('/', '../../x')
Expected Output: '/x'
Explanation: Cannot go above root.
Input: ('/a/b','/d//e/./f/..')
Expected Output: '/d/e'
Explanation: Absolute path resets cwd.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.
Merge Overlapping Inclusive Intervals
Merge inclusive intervals that overlap, returning sorted non-overlapping intervals.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,3],[2,6],[8,10],[15,18]],)
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Prompt example.
Input: ([[1,4],[4,5]],)
Expected Output: [[1, 5]]
Explanation: Touching inclusive intervals overlap.
Input: ([],)
Expected Output: []
Explanation: No intervals.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.