← Glean Interview Insights

Glean·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Interviewed for a software engineer role at Glean and got hit with Word Search (LC 79). Short and to the point, nothing too surprising.

Questions Asked (1)

Q1

Given a 2D board of characters and a target word, determine whether the word exists in the grid by searching through adjacent cells (horizontally or vertically connected, no reuse of cells).

Algorithms & Data Structures
Author's notes

Classic backtracking problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use depth-first search (DFS) with backtracking to explore all possible paths from each cell that matches the first character of the word. Mark cells as visited during the search and unmark them when backtracking to avoid reusing cells. Return true if any path spells the entire word.

Pro tip: Before coding, discuss optimizations like pruning branches when the remaining word length exceeds available cells or using a trie for multiple word searches. Also, clarify edge cases such as empty board or word longer than total cells.

1. Clarify problem and constraints

Confirm the rules: movement only horizontally/vertically, no cell reuse, and whether the word can start anywhere. Ask about board size and character set to discuss complexity.

2. Outline DFS with backtracking

Explain that you'll iterate over each cell, and if it matches the first character, perform DFS to match subsequent characters. Use a visited set or modify the board temporarily to mark visited cells.

3. Detail the DFS function

Describe the recursive function: base case when index equals word length (return true), check boundaries and character match, mark cell visited, recurse in four directions, then unmark (backtrack).

4. Analyze complexity and optimizations

State time complexity O(N * 3^L) where N is number of cells and L is word length, and space O(L) for recursion. Mention pruning: if remaining length > available cells, or if character counts in board don't match word.

5. Test with examples and edge cases

Walk through a small example, and discuss edge cases: empty board, word longer than total cells, single cell, and cases where no path exists.

Key Points to Mention

  • Depth-first search (DFS) with backtracking
  • Marking cells as visited and unmarking (backtracking)
  • Iterating over all starting cells
  • Time and space complexity analysis
  • Pruning optimizations (e.g., character count check, length check)
  • Handling edge cases (empty board, word longer than board)

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