FastPrepCount Grid Words with One Turn
Problems/Count Grid Words with One Turn

Count Grid Words with One Turn

Capital One logoCapital One● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2023 Capital One software engineer intern coding assessment on CodeSignal had four problems, and one of them counts how often each word in a list appears in a letter grid. A path there may bend at most one time. The report's example bends straight back along one row.

The report does not say which steps are allowed, how to count paths that reuse cells, how to count one-letter words, or what the limits are. Here, steps go up, down, left or right, and the one turn may go any other way, including straight back. Two paths count as different when their cell lists differ, so a one-letter word counts once for each cell that holds it. The limits are our choice.

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

grid is a rectangle of lowercase letters given as strings of equal length; grid[r][c] is the letter at row r, column c. words holds the lowercase words to look for.

A trace of a word is a list of cells, one per letter, that spells the word in order. For a word of one letter, the list is just one cell holding that letter, and there is no heading to choose. For longer words, the list must also obey these rules:

  • Consecutive cells of a trace share a side, so they are vertical or horizontal neighbors.
  • A trace starts with one heading and keeps it. At one cell of its choice it may switch, once, to a different heading, and it keeps that heading to the end.
  • The new heading may point straight back, so a cell can appear in a trace twice.

Two traces are counted separately whenever their cell sequences differ. Return an array where entry i counts the traces of words[i].

Function

countWordPaths(grid: String[], words: String[]) → int[]

Examples

Example 1

grid = ["ab","cd"]words = ["abd","abdc","aba"]return = [1,0,1]
grid
010ab1cd

The cells are a (row 0, column 0), b (0, 1), c (1, 0) and d (1, 1). "abd": a then b heads right, and the one switch, to heading down, reaches d, so its count is 1. "abdc": after a, b, d the heading would have to change a second time to reach c, so its count is 0. "aba": a then b, and the switch points straight back to a, so its count is 1.

Example 2

grid = ["sun","nod","use"]words = ["nun","u","sus","dos"]return = [2,2,2,1]
grid
0120sun1nod2use

The rows are s u n, n o d and u s e. "nun": from the n at (0, 2), step left to u and turn back right; from the n at (1, 0), step down to u and turn back up. That is 2, one in a row and one in a column. "u": one letter, so each of the 2 cells holding u is one trace. "sus": (0, 0) to (0, 1) and back, and (2, 1) to (2, 0) and back, so 2. "dos": from d at (1, 2), left to o, then the one switch heads down to s, so 1.

Example 3

grid = ["plan","atee","sent"]words = ["planet","ten","ene"]return = [1,3,5]
grid
01230plan1atee2sent

"planet" has 6 letters, more than any row (4) or column (3) holds, so a trace must bend. The only one runs right along row 0 to the n at (0, 3), then down column 3 through e and t. That gives 1. "ten": the t at (1, 1) has two bent traces, down to the e at (2, 1) then right to the n at (2, 2), or right to the e at (1, 2) then down to the same n. The t at (2, 3) has one straight trace, up column 3 through e and n. That is 3. "ene": from the e at (1, 2), go down to the n at (2, 2), then either back up to (1, 2) or left to the e at (2, 1). From the e at (2, 1), go right to the same n, then either back left to (2, 1) or up to the e at (1, 2). From the e at (1, 3), go up to the n at (0, 3) and back down. The bend (1, 2), (2, 2), (2, 1) and its reverse use the same three cells in a different order, so they count as two traces, and the total is 5.

Constraints

  • 1 <= grid.length <= 30
  • 1 <= grid[i].length <= 30, and every row has the same length.
  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 20
  • grid and words contain only lowercase English letters.

More Capital One Online Assessment questions

  • Rank Football TeamsOA · Seen Oct 2026
  • Count Subarrays Matching a Comparison PatternOA · Seen Oct 2026
  • Arithmetic Triplets After QueriesOA · Seen Oct 2026
  • Branch with the Most FilesOA · Seen Oct 2026
  • Count One-Swap Number PairsOA · Seen Oct 2026
  • Distinct Values on Maximum-Sum FramesOA · Seen Oct 2026
  • Earliest Meeting Time for All EmployeesOA · Seen Oct 2026
  • Earn the Most 🐝OA · Seen Oct 2026
  • Sort Adjacent PairsOA · Seen Oct 2026
  • Bouncing Diagonal WeightsOA · Seen Oct 2026

Similar questions at other companies

  • Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
  • Maximum Equal-Bit Pairs in a SubsequenceAmazon · OA
  • Longest Subsequence That Is a SubstringBooking.com · OA
  • Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
  • Grid Paths with Override PassesIMC Trading · OAIMC Trading interview questions
  • Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
  • Largest Square of OnesOpenAI · OAOpenAI interview questions
  • Count Straight-Line Word Occurrences in a GridOptiver · OAOptiver interview questions
  • Longest String ChainVisa · OAVisa interview questions
  • Minimum Moves to Spread Stones Across a GridAmerican Express · OAAmerican Express interview questions

Capital One interview experiences

  • Capital One Experienced Engineer Power Day and OA: 6 Experiences
  • Capital One New Grad OA Questions: 14 Experiences (Part 2 of 2)
  • Capital One TDP Agentic Round (AI Coding): 7 Experiences
  • Capital One SWE Power Day, Level Not Reported: 6 Experiences
  • Capital One TIP Intern OA and Power Day: 13 Experiences
  • Capital One TDP Agentic Power Day: 25 Experiences (Part 1 of 2)
All Capital One interview questionsSee Capital One hiring insights
Saved
class Solution {
    public int[] countWordPaths(String[] grid, String[] words) {
        // Write your code here.
    }
}
Checking account…