Quick Overview

This question evaluates design and analysis skills for string-matching data structures that support one-edit queries and for binary tree traversal with coordinate-based ordering, testing understanding of data structures, search algorithms, sorting, and complexity analysis within the Coding & Algorithms domain.

Solve string dictionary and tree ordering

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Part A — One-edit dictionary: Build a data structure supporting build(words: List[str]) and search(query: str) -> bool that returns true if and only if there exists a stored word obtainable by changing exactly one character of query. Discuss possible designs (e.g., trie with masked patterns or hash-based buckets), edge cases (length mismatches, duplicates, non-lowercase), and complexity. Part B — Tree ordering by coordinates: Given a binary tree whose nodes contain lowercase letters, assign coordinates with root at (row=0, col= 0), left child at (row+1, col- 1), and right child at (row+1, col+ 1). Output the concatenation of node values ordered by column ascending, then row ascending; break ties left-to-right. Describe an algorithm (e.g., DFS/BFS to collect (row, col, char) then stable sort) and analyze time and space complexity.

Quick Answer: This question evaluates design and analysis skills for string-matching data structures that support one-edit queries and for binary tree traversal with coordinate-based ordering, testing understanding of data structures, search algorithms, sorting, and complexity analysis within the Coding & Algorithms domain.

One-Edit Dictionary Lookup

Build a dictionary from a list of words, then answer queries. For each query string, return true if and only if the dictionary contains some stored word that can be obtained from the query by changing **exactly one** character (same length, exactly one differing position). Implement `solution(words, queries)` that returns a list of booleans, one per query. Notes and edge cases: - An exact match (zero differences) must return **false** — you need exactly one edited character, not zero. - A query whose length differs from every stored word returns false (you may only substitute, not insert or delete). - Duplicate words in the dictionary are harmless and do not change the answer. - The dictionary may be empty (every query is false). Example: dictionary = ["hello", "world", "cat"]. Query "cello" -> true (one edit from "hello"). Query "hello" -> false (zero edits). Query "world" -> false (it matches a stored word exactly, so no single edit is needed).

Constraints

  • 0 <= len(words), len(queries) <= 10^4
  • 1 <= len(word) <= 100 for each word and query
  • All characters are lowercase English letters (handle non-lowercase gracefully by treating them as ordinary characters)
  • An exact match counts as zero edits and must return false

Examples

Input: (['hello', 'world', 'cat'], ['cello', 'hello', 'cot', 'cat', 'dog', 'world'])

Expected Output: [True, False, True, False, False, False]

Explanation: 'cello' is one edit from 'hello' -> True. 'hello' matches exactly (0 edits) -> False. 'cot' is one edit from 'cat' -> True. 'cat' matches exactly -> False. 'dog' has no same-length stored word within one edit -> False. 'world' matches exactly -> False.

Input: ([], ['abc'])

Expected Output: [False]

Explanation: Empty dictionary, so no word can be one edit away.

Hints

  1. Words can only match by substitution, so a query can never match a stored word of a different length. Bucket the dictionary by length first.
  2. For two equal-length strings, count differing positions and stop early once the count exceeds 1. You want the count to equal exactly 1.
  3. Watch the 'exactly one' boundary: a query identical to a stored word has zero differences and must return false.

Binary Tree Ordering by Column then Row

A binary tree's nodes each hold a single lowercase letter. Assign coordinates with the root at (row=0, col=0); a left child is at (row+1, col-1) and a right child is at (row+1, col+1). Output the concatenation of node values ordered by **column ascending**, then **row ascending**; break remaining ties **left-to-right** (the order in which nodes are reached by a pre-order traversal that visits the left subtree before the right). This is the classic vertical-order traversal flattened into a string. The tree is given as a LeetCode-style level-order list: index 0 is the root, and `None` marks an absent child. Implement `solution(level_order)` returning the resulting string. Example: the tree where root 'c' has a right child 'i' that in turn has a right child 'a' is encoded as ['c', None, 'i', None, 'a'] and produces "cia" (columns 0, 1, 2). Edge cases: an empty list (or a list whose root is None) yields the empty string; a single-node tree yields that node's character.

Constraints

  • 0 <= N <= 10^4 nodes
  • Each node value is a single lowercase English letter
  • Input is a LeetCode-style level-order list with None (or empty string for C++) for missing children
  • An empty list, or a list whose root is None, yields the empty string

Examples

Input: (['c', None, 'i', None, 'a'],)

Expected Output: "cia"

Explanation: Root c at col 0; right child i at col 1; i's right child a at col 2. Columns 0,1,2 -> 'cia'.

Input: (['b', 'a', 'c'],)

Expected Output: "abc"

Explanation: b at col 0, left child a at col -1, right child c at col 1. By column ascending: a(-1), b(0), c(1) -> 'abc'.

Hints

  1. Coordinates are deterministic: root (0,0), left child (row+1, col-1), right child (row+1, col+1). A single DFS can carry (row, col) down the tree.
  2. Collect a tuple (col, row, visit_order, char) for every node, then sort by (col, row, visit_order). The visit order from a left-before-right traversal breaks any remaining ties.
  3. Reconstruct the tree from the level-order list with a queue, skipping children of None nodes, before traversing for coordinates.

Loading coding console...