How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bytedance during technical interviews.

Find Words in a Character Grid | Bytedance Coding Question

Q: Find Words in a Character Grid

This question evaluates algorithm design for efficient multi-word search in a character grid, testing competencies in constrained graph traversal, managing large dictionaries, and selecting data structures for efficient lookup.

Find Words in a Character Grid

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement `findWords(board, words)` for a word-search game. You are given an `m x n` grid of lowercase English letters and a list of lowercase dictionary words. A word can be formed by starting at any cell and repeatedly moving one step up, down, left, or right. The same grid cell may not be used more than once in a single word. Return all unique dictionary words that can be formed in the grid. The output order does not matter. Constraints: - `1 <= m, n <= 12` - `1 <= words.length <= 30000` - `1 <= words[i].length <= 10` - All words contain only lowercase English letters. Optimize for a large dictionary and avoid searching the grid independently for every word.

Quick Answer: This question evaluates algorithm design for efficient multi-word search in a character grid, testing competencies in constrained graph traversal, managing large dictionaries, and selecting data structures for efficient lookup.

Implement `solution(board, words)` for a word-search game. You are given an `m x n` grid of lowercase English letters and a list of lowercase dictionary words. A word can be formed by starting at any cell and repeatedly moving one step up, down, left, or right. The same grid cell may not be used more than once in a single word. Return all unique dictionary words that can be formed in the grid. Because the dictionary can be large, your solution should avoid searching the board independently for every word. For deterministic output in this problem, return the result sorted in lexicographical order.

Constraints

1 <= len(board), len(board[0]) <= 12
1 <= len(words) <= 30000
1 <= len(words[i]) <= 10
All board cells and words contain only lowercase English letters

Examples

Input: ([['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], ['oath','pea','eat','rain'])

Expected Output: ['eat', 'oath']

Explanation: The words 'oath' and 'eat' can be formed by valid adjacent paths. 'pea' and 'rain' cannot.

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

Expected Output: ['a']

Explanation: Only 'a' can be formed. 'aa' would require reusing the same cell, and duplicates should appear only once in the result.

Input: ([['a','b'],['c','d']], ['ab','abc','abd','acdb','bdca','ab'])

Expected Output: ['ab', 'abd', 'acdb', 'bdca']

Explanation: 'ab', 'abd', 'acdb', and 'bdca' all have valid paths. 'abc' cannot be formed with orthogonal moves only.

Input: ([['x','y'],['z','w']], ['xyzwx','yzx','xx'])

Expected Output: []

Explanation: None of the words can be formed without reusing a cell or making an invalid move.

Input: ([['a','a']], ['a','aa','aaa'])

Expected Output: ['a', 'aa']

Explanation: The board can form 'a' and 'aa'. 'aaa' is impossible because the board has only two cells and a cell cannot be reused.

Hints

Searching the full grid separately for every word repeats a lot of work. Think about a data structure that groups words by shared prefixes.
While doing DFS from the board, stop exploring as soon as the current path is not a prefix of any remaining dictionary word.

Quick Overview

This question evaluates algorithm design for efficient multi-word search in a character grid, testing competencies in constrained graph traversal, managing large dictionaries, and selecting data structures for efficient lookup.