Katkat
Back

Implement cd and merge intervals

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate string-based file system paths using a stack-based approach and consolidate overlapping time intervals using sorting.

Part 1: Path Normalization

Implement a function simplify_path(path: str) -> str that converts a Unix-style file path into its canonical form.

Rules:

  • The path must start with a single slash /.
  • Any directory names are separated by a single slash.
  • .. moves one level up.
  • . refers to the current directory.
  • Consecutive slashes // are treated as a single slash.

Example: Input: /a/./b/../../c/ Output: /c

Part 2: Merge Intervals

Given a collection of intervals, where each interval is represented as a list [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all intervals in the input.

Constraints:

  • 0 <= intervals.length <= 10^4
  • start <= end

Example: Input: [[1, 3], [2, 6], [8, 10], [15, 18]] Output: [[1, 6], [8, 10], [15, 18]]

Explain your complexity for both solutions.

Hints

Hint 1

For path simplification, use a stack to keep track of directory names and pop from the stack when you encounter '..'.

Hint 2

For interval merging, sorting the intervals by their start times is the critical first step to ensure you only need to compare the current interval with the last merged one.

Hint 3

For path normalization, remember to handle the root directory case correctly when the stack is empty and '..' is encountered.

Follow-up questions

  • How would you modify the path normalization to handle symbolic links?
  • What is the time and space complexity of your interval merging algorithm, and can you do it in O(1) extra space if the input array is mutable?
  • How would you adapt the interval merging logic if the intervals were not sorted by start time?