How should I practice Rectangular K-in-a-Row?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Databricks onsite interview problems in FastPrep.

Is Rectangular K-in-a-Row associated with Databricks?

FastPrep tags this as a Databricks onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Design

Rectangular K-in-a-Row

Learn this problem

● Hard

DatabricksFULLTIMEONSITE INTERVIEW

Problem statement

An empty game board has rows rows and columns columns. Two players, numbered 1 and 2, place marks through the ordered array moves. Each move is [row, column, player].

After placing a mark, that player wins if the new mark belongs to a contiguous run of at least k marks by the same player in any one of four directions:

horizontal,
vertical,
the top-left to bottom-right diagonal, or
the top-right to bottom-left diagonal.

Return one result for every move. The result is the winning player number if that move completes a winning run; otherwise it is 0.

Rows and columns use zero-based indexing. Every move is inside the board and targets an empty cell. The sequence ends immediately after the first winning move, so no move is made after a winner exists.

Function

playKInARow(rows: int, columns: int, k: int, moves: int[][]) → int[]

Examples

Example 1

rows = 3columns = 3k = 3moves = [[0,0,1],[0,1,2],[1,1,1],[0,2,2],[2,2,1]]return = [0,0,0,0,1]

Player 1 completes the main diagonal at [2,2]. No earlier move forms three contiguous marks.

Example 2

rows = 3columns = 5k = 4moves = [[0,0,1],[1,0,2],[0,1,1],[1,1,2],[2,4,1],[1,2,2],[2,3,1],[1,3,2]]return = [0,0,0,0,0,0,0,2]

On the final move, player 2 owns four consecutive cells from column 0 through column 3 in row 1.

Example 3

rows = 2columns = 2k = 1moves = [[1,0,2]]return = [2]

When k = 1, the first valid mark is already a winning run of length one.

Constraints

1 <= rows, columns <= 10^9
1 <= k <= max(rows, columns)
1 <= moves.length <= 200000
Every move has exactly three integers [row, column, player].
0 <= row < rows and 0 <= column < columns.
player is either 1 or 2.
No cell appears in more than one move.
The sequence stops immediately after the first winning move.