Depth-First Search Questions at Grammarly: What to Expect

Depth-First Search (DFS) is a fundamental algorithm for exploring graphs and trees, making it essential for solving problems involving hierarchical data, connected components, and pathfinding. At Grammarly, where engineers build features for understanding document structure, checking grammar across complex sentences, and analyzing text relationships, DFS is a practical tool. The algorithm's ability to traverse nested structures—like the parse tree of a sentence or the dependency graph between writing suggestions—makes it directly applicable to their work. With 4 out of their 26 total coding questions focused on DFS, mastering it is non-negotiable for passing their technical screen.

What to Expect — Types of Problems

Grammarly's DFS questions typically model real-world text and document analysis scenarios. You won't get abstract graph theory puzzles. Expect problems that involve traversing tree-like structures or exploring states in a constrained search space. Common patterns include:

• Tree Traversal & Modification: Problems involving sentence parse trees, XML/HTML document nodes, or nested list structures where you need to validate, transform, or extract information.
• Connected Components in a Grid: Modeling a document as a 2D grid (e.g., for a page layout analysis) and finding connected regions of characters or words.
• Pathfinding in a State Space: Exploring possible sequences of edits or corrections within certain rules, akin to finding a valid path through a graph of writing states.
• Backtracking: A specific DFS variant used for generating all valid combinations or placements, such as generating all possible grammar corrections for a given phrase.

How to Prepare — Study Tips with One Code Example

Focus on the recursive implementation of DFS; it's intuitive for tree problems and easier to write under interview pressure. Memorize the iterative stack-based version as a backup. Your practice should center on recognizing when a problem is fundamentally about exhaustive exploration of a structure.

The most critical pattern is the standard recursive traversal for a tree or graph. Understand how to pass down state (like a path or a cumulative value) and how to return results back up the call stack.

def dfs(node, target):
    if not node:
        return False
    if node.val == target:
        return True
    # Recurse on all children (for a graph, you'd track visited)
    for child in node.children:
        if dfs(child, target):
            return True
    return False

Recommended Practice Order

1. Master Tree Traversals: Start with basic pre-order, in-order, and post-order traversal on binary trees. Practice problems like finding a node, calculating depth, and path sum.
2. Solve Grid (Matrix) DFS: Practice the classic "number of islands" pattern. This directly translates to finding connected components in a 2D representation of data.
3. Tackle Backtracking: Practice generating permutations, subsets, and classic puzzles like N-Queens. This builds skill in exploring all possibilities and pruning invalid paths.
4. Simulate Grammarly Context: Finally, practice problems that involve strings and nested structures. Think about traversing a directory of documents, validating nested markdown tags, or exploring a graph of word synonyms.

Practice Depth-First Search at Grammarly