Quick Overview

This question evaluates proficiency in hierarchical string processing, prefix-based filtering, edge-case handling (duplicates, trailing slashes, empty inputs), data-structure selection, and algorithmic time/space complexity analysis within the Coding & Algorithms domain, emphasizing practical implementation over purely conceptual reasoning.

Filter hierarchical paths after deletions

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given two arrays: ( 1) paths — slash-delimited hierarchical strings such as "California", "California/San Francisco", "California/San Francisco/7th Street"; and ( 2) deletes — paths to remove such as "California/San Francisco". Remove every path that is equal to or a descendant of any path in deletes, and return the remaining paths (order your choice). Design an efficient solution (e.g., Trie or sorting plus prefix-skipping), handle edge cases (duplicates, overlapping deletes, trailing slashes, empty arrays), and analyze time and space complexity. Implement the core function.

Quick Answer: This question evaluates proficiency in hierarchical string processing, prefix-based filtering, edge-case handling (duplicates, trailing slashes, empty inputs), data-structure selection, and algorithmic time/space complexity analysis within the Coding & Algorithms domain, emphasizing practical implementation over purely conceptual reasoning.

You are given two arrays of strings: 1. `paths` — slash-delimited hierarchical strings such as `"California"`, `"California/San Francisco"`, `"California/San Francisco/7th Street"`. 2. `deletes` — paths to remove, such as `"California/San Francisco"`. Remove every path in `paths` that is **equal to** or a **descendant of** any path in `deletes`, and return the remaining paths. The returned order is your choice (the tests preserve the original input order of the surviving paths). A path `P` is a descendant of a delete `D` when `D` is a proper prefix of `P` at the segment boundary — i.e. splitting on `/` (ignoring empty segments produced by leading/trailing/duplicate slashes), the segments of `D` are a prefix of the segments of `P`. So delete `"California/San Francisco"` removes `"California/San Francisco"` and `"California/San Francisco/7th Street"`, but NOT `"California"` (an ancestor) and NOT `"Californian"` (a string-prefix that is not a segment-prefix). Handle edge cases: duplicate paths, overlapping deletes, trailing/leading/duplicate slashes (normalize before comparing, but keep the original string in the output), and empty input arrays. Implement the core function `filterPaths(paths, deletes)`. Example: Input: paths = ["California", "California/San Francisco", "California/San Francisco/7th Street"], deletes = ["California/San Francisco"] Output: ["California"]

Constraints

  • 0 <= len(paths), len(deletes) <= 10^5
  • Each path/delete string length up to ~200 characters
  • Segments are separated by '/'; leading, trailing, and duplicate slashes may appear and must be ignored when comparing
  • An empty delete entry (e.g. "" or "/") matches nothing and is skipped
  • Comparison is by full path segments, not raw substring prefixes

Examples

Input: (["California", "California/San Francisco", "California/San Francisco/7th Street"], ["California/San Francisco"])

Expected Output: ["California"]

Explanation: "California/San Francisco" equals the delete; "California/San Francisco/7th Street" is its descendant; "California" is an ancestor and survives.

Input: (["California", "California/San Francisco", "Nevada", "Nevada/Reno"], ["California", "Nevada/Reno"])

Expected Output: ["Nevada"]

Explanation: Deleting "California" removes it and all descendants; deleting "Nevada/Reno" removes only that leaf, leaving "Nevada".

Hints

  1. Normalize each path by splitting on '/' and dropping empty segments, so "California/San Francisco/" and "California//San Francisco" both become ["California", "San Francisco"]. This handles trailing/duplicate slashes.
  2. Put the normalized delete paths into a hash set (as tuples of segments). A path should be removed if ANY of its segment-prefixes (including the full path) is in that set.
  3. Why prefixes? Path P is a descendant of delete D exactly when D's segments are a prefix of P's segments. Checking every prefix of P against the set covers both 'equal to' and 'descendant of'.
  4. Keep the ORIGINAL string for output even though you compare on the normalized form — the test expects "California/" back, not "California".
  5. A Trie of segments is an alternative: insert each delete path, mark its terminal node as deleted, then walk each path and drop it if you pass through any deleted terminal node.

Loading coding console...