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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

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

Find Earliest Column With One | Uber Coding Question

Q: Find Earliest Column With One

This question evaluates algorithmic problem-solving and optimization skills for working with a row-wise sorted binary matrix accessed via an API, focusing on search efficiency and query-cost awareness.

Find Earliest Column With One

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given access to a binary matrix through an API rather than direct storage. The matrix has `m` rows and `n` columns. Each row is sorted in nondecreasing order, so every row consists of zero or more `0`s followed by zero or more `1`s. The API provides: - `get(row, col) -> int`: returns the value at the given row and column, either `0` or `1`. - `dimensions() -> [m, n]`: returns the number of rows and columns. Return the smallest column index that contains at least one `1`. If the matrix contains no `1`, return `-1`. Constraints: - `1 <= m, n <= 100` - Minimize the number of calls to `get`. Example: ```text matrix = [ [0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 0, 0] ] ``` The answer is `2`, because column `2` is the leftmost column containing a `1`.

Quick Answer: This question evaluates algorithmic problem-solving and optimization skills for working with a row-wise sorted binary matrix accessed via an API, focusing on search efficiency and query-cost awareness.

You are given a binary matrix where each row is sorted in nondecreasing order. That means every row contains zero or more `0`s followed by zero or more `1`s. Return the smallest 0-based column index that contains at least one `1`. If the matrix contains no `1`, return `-1`. Note: In the original interview version, the matrix is accessed through an API (`get(row, col)` and `dimensions()`). For this coding task, the matrix is provided directly as a 2D list, but the intended efficient strategy is the same: inspect as few cells as possible.

Constraints

1 <= m, n <= 100
matrix[i][j] is either 0 or 1
Each row is sorted in nondecreasing order

Examples

Input: ([ [0,0,0,1], [0,0,1,1], [0,0,0,0] ],)

Expected Output: 2

Explanation: Column 2 contains a 1 in the second row, and no column to the left contains any 1.

Input: ([ [0,0], [0,0] ],)

Expected Output: -1

Explanation: The matrix contains only 0s, so there is no valid column.

Input: ([ [1,1,1], [1,1,1] ],)

Expected Output: 0

Explanation: The very first column already contains 1s, so the answer is 0.

Input: ([ [0,0,0,0,1] ],)

Expected Output: 4

Explanation: There is only one row, and its first 1 appears at column 4.

Input: ([ [1] ],)

Expected Output: 0

Explanation: In this single-cell matrix, the only cell is 1, so the earliest column is 0.

Hints

Because each row is sorted, finding a `1` means everything to its right is also `1`, so those columns cannot improve the answer.
Try starting from the top-right corner. From there, each step can eliminate either one row or one column.

Quick Overview

This question evaluates algorithmic problem-solving and optimization skills for working with a row-wise sorted binary matrix accessed via an API, focusing on search efficiency and query-cost awareness.