FastPrepTrace a Word Through a Letter Grid
Problems/Trace a Word Through a Letter Grid

Trace a Word Through a Letter Grid

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A post published on October 21, 2021, by a student in an Expedia campus internship drive puts this task in the second technical interview. It states the task, including the rule that each step moves to a cell sharing an edge with the current one.

The post gives no limits or examples and does not say whether a cell may be used more than once in a word. Here, each cell can be used at most once. The grid has 1 to 6 rows and 1 to 6 columns of English letters. Upper and lower case count as different letters. The word has 1 to 15 letters.

Our version is about 95% the same as the reported question.

You are given an m x n grid of letters board and a string word. Return true if you can spell word by walking through the grid, and false otherwise.

A walk starts at any cell whose letter is the first letter of word. Each step moves to a neighbouring cell that shares a side with the current one (up, down, left or right; corners do not count, and the grid does not wrap around), and that cell must hold the next letter of word. A cell can be used at most once in the same walk.

Upper and lower case letters are different: 'a' does not match 'A'.

Function

exist(board: char[][], word: String) → boolean

Examples

Example 1

board = [["T","R","I","P"],["O","A","X","S"],["U","R","E","T"]]word = "TRIPS"return = true
board
01230TRIP1OAXS2URET

Start at the T in the top-left corner and move right through R, I and P, then down to the S below P.

Example 2

board = [["T","R","I","P"],["O","A","X","S"],["U","R","E","T"]]word = "STAR"return = false
board
01230TRIP1OAXS2URET

The only S is in row 1, column 3 (counting from 0). The only T next to it is in row 2, column 3, and that T has no A next to it. The other T is not next to an S. Every letter of the word is on the board, but no path spells it.

Example 3

board = [["T","R","I","P"],["O","A","X","S"],["U","R","E","T"]]word = "TOT"return = false
board
01230TRIP1OAXS2URET

T then O works only from the top-left T down to the O below it. The O has no other T next to it, and the first T cannot be used a second time.

Constraints

  • m == board.length and n == board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word contain only English letters, upper and lower case.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
  • Word Search with Eight-Direction AdjacencyMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Find a Word in a Letter GridAdobe · PHONE SCREENAdobe interview questions
  • Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Word SearchAmazon · ONSITE INTERVIEW
  • Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
  • Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
  • Query Whether an Island Size ExistsMeta · ONSITE INTERVIEWMeta interview questions
  • Maximum Number of Fish in a GridGlobalization Partners · ONSITE INTERVIEW
  • Max Area of IslandGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public boolean exist(char[][] board, String word) {
        // Write your code here.
    }
}
Checking account…