← Glean Interview Insights

Glean·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Interviewed for a software engineer role at Glean. The main question was Word Search II, which is already a pretty well-known hard problem, so not a huge surprise but still stressful under pressure.

Questions Asked (1)

Q1

Given a 2D board of characters and a list of words, find all words that exist in the board. Words can be constructed from sequentially adjacent cells (horizontally or vertically neighboring), and the same cell may not be used more than once per word.

Algorithms & Data Structures
Author's notes

This is the trie plus DFS backtracking problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a Trie to store the word list for efficient prefix lookups, then perform DFS with backtracking from each cell to explore all possible paths. During DFS, mark cells as visited and prune branches when the current prefix is not in the Trie. Collect words when a complete word is found, and optionally remove them from the Trie to avoid duplicates.

Pro tip: Optimize by storing words in a Trie and pruning the search as soon as the current path is not a prefix of any word. Also, consider removing found words from the Trie to avoid redundant searches and duplicates.

1. Clarify and Plan

Confirm the problem constraints: board dimensions, word list size, and whether words can be reused. Discuss the naive approach and its inefficiencies, then propose the Trie + DFS optimization.

2. Build Trie

Insert all words into a Trie, where each node represents a character and stores a flag indicating if it's the end of a word. This allows O(1) prefix checks during DFS.

3. DFS with Backtracking

For each cell, start a DFS if its character is a child of the Trie root. At each step, check if the current Trie node marks a word end; if so, add the word to results. Then, recursively explore all four adjacent cells, marking the current cell as visited to avoid reuse.

4. Prune and Optimize

During DFS, if the current character is not in the Trie, backtrack immediately. After finding a word, consider removing it from the Trie to prevent duplicate results and reduce search space.

5. Analyze Complexity

Explain time complexity: O(M * N * 4^L) worst-case, where L is max word length, but Trie pruning reduces it significantly. Space complexity: O(total characters in words) for the Trie plus recursion stack.

Key Points to Mention

  • Trie data structure for efficient prefix matching
  • Depth-first search with backtracking
  • Visited state management to avoid reusing cells
  • Pruning when current prefix is not in Trie
  • Handling duplicate words (e.g., removing from Trie or using a set)
  • Time and space complexity analysis

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.