Katkat
Back

Implement phrase search and JSON path

NetflixData Engineer · Onsite
HardData EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to process unstructured text into a searchable index and navigate hierarchical data structures using path patterns.

Part 1: Inverted Index for Phrase Search

Implement a class PhraseSearcher that indexes a list of documents. Given a query (a multi-word phrase), return the indices of all documents where the exact sequence of words appears.

class PhraseSearcher:
    def __init__(self, documents: List[str]):
        # documents are space-separated strings
        pass
    def search(self, phrase: str) -> List[int]:
        # Returns list of document indices containing the exact phrase
        pass

Part 2: JSON Path Traversal

Implement a function json_path(data, path) that retrieves values from a nested JSON-like structure (dictionaries and lists) based on a dot-notation path. The path may include *, which acts as a wildcard to match all keys at that level.

def json_path(data: Union[dict, list], path: str) -> List[Any]:
    # path is a string like "store.books.*.title"
    # return a list of all matching values
    pass

Examples

Part 1: Docs: ["the quick brown fox", "the brown fox jumps"] Query: "brown fox" -> Returns: [0, 1]

Part 2: Data: {"a": [{"x": 1}, {"x": 2}]} Path: "a.*.x" -> Returns: [1, 2]

Constraints

  • For Part 1, assume documents contain only lowercase alphanumeric characters and spaces.
  • For Part 2, paths can contain nested wildcards and access indices in lists.
  • Consider efficiency for repeated queries.

Hints

Hint 1

For Part 1, represent the phrase as a list of tokens and consider using a dictionary mapping tokens to a list of (doc_index, position) tuples.

Hint 2

For Part 2, treat the path string as a sequence of keys to be processed recursively or via a queue, handling lists and dictionaries differently.

Hint 3

For the wildcard case in Part 2, ensure the function returns a flattened list of all matches found across all branches.

Follow-up questions

  • How would you optimize the phrase search if the number of documents grows to billions?
  • How would you handle cases where the JSON path includes filters, such as `store.books[price < 10].title`?
  • What are the space complexity implications of your inverted index versus a suffix tree for phrase searching?