Katkat
Back

Build Quadtree and Find Grid Words

UberSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to implement a spatial partitioning data structure (Quadtree) for a grid and perform recursive searches to locate words within that grid efficiently.

Part 1: Quadtree Construction

Given an N x N grid of characters (where N is a power of 2), build a Quadtree to represent the grid. A Quadtree node is either a leaf containing a character (if all cells in its subgrid are identical) or an internal node that splits the grid into four equal quadrants (top-left, top-right, bottom-left, bottom-right).

Define a Node class that contains pointers to its four children and a value (the character, if the node is a leaf). Implement a function buildQuadtree(grid) that returns the root of the tree.

Part 2: Word Search

Given the same N x N grid, find if a list of words exists in the grid. A word can be formed by moving to any of the 8 adjacent cells (horizontally, vertically, or diagonally). A cell can only be used once per word.

Implement findWords(grid, words) which returns a list of words found in the grid.

Constraints

  • N is a power of 2, up to 1024.
  • Grid contains lowercase English letters.
  • The list of words contains up to 1000 words, each of length up to 20.

Example

grid = [['a', 'b'], ['c', 'd']]
# buildQuadtree would return an internal node with 4 leaf children.
# findWords(grid, ['ab', 'ad']) would return ['ab', 'ad']

Hints

Hint 1

To build the Quadtree, use recursion: check if all cells in the current bounds are identical, otherwise split the bounds into four equal parts and recurse.

Hint 2

For the word search, use backtracking with a 'visited' set to keep track of cells used in the current path.

Hint 3

Consider using a Trie to store the list of words to optimize the search if multiple words share prefixes.

Follow-up questions

  • How would the Quadtree construction change if the grid size was not a power of 2?
  • What is the time complexity of building the Quadtree in terms of N?
  • How does the search complexity change if you use a Trie compared to searching for each word individually?