Here is the full interview question "Coding - Word Search II" asked at Uber:

Uber Interview Question

Title: Coding - Word Search II

Problem Statement: Given an m x n grid of characters and a list of words to search for within that grid, return a list of all words found in the grid in the order of their appearance in the list.

Constraints:

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• All characters in the board are lowercase English letters.
• 1 <= words.length <= 12
• 1 <= words[i].length <= 12
• All words consist of lowercase English letters only.

Examples:

1. Input:

   • board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]
   • words = ["oath","pea","eat","rain"]
   • startLetters = ["o","e","a","i"]
   • index = 0 Output: ["oath","eat"]

2. Input:

   • board = [["a","b"],["c","d"]]
   • words = ["abcb"] Output: []

Hints:

• Use a trie data structure to store all the words.
• Perform a depth-first search (DFS) for each word in the trie.
• Keep track of visited cells to avoid revisiting them.

Solution: `python class TrieNode: def init(self): self.children = {} self.is_end_of_word = False

class Trie: def init(self): self.root = TrieNode()

def insert(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

class Solution: def findWords(self, board, words): trie = Trie() for word in words: trie.insert(word)

    res = []
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] in trie.root.children:
                self.dfs(board, trie.root, i, j, board[i][j], "", res, directions)
    return res

def dfs(self, board, node, i, j, char, curr_word, res, directions):
    if node.is_end_of_word:
        res.append(curr_word + char)
        node.is_end_of_word = False

    temp, board[i][j] = board[i][j], '#'
    for dir in directions:
        x, y = i + dir[0], j + dir[1]
        if 0 <= x < len(board) and 0 <= y < len(board[0]) and board[x][y] in node.children:
            self.dfs(board, node.children[board[x][y]], x, y, board[x][y], curr_word + char, res, directions)
    board[i][j] = temp

Example usage:

board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]] words = ["oath","pea","eat","rain"] solution = Solution() print(solution.findWords(board, words)) # Output: ["oath","eat"] `

Source: LeetCode (https://leetcode.com/problems/word-search-ii/)