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 medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Upstart.

What role is this question designed for?

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

Solve remembered OA coding tasks | Upstart Coding Question

Quick Overview

This set of problems evaluates skills in data aggregation and ordering (identifying top averages), computational geometry and extrema calculation (axis-aligned bounding rectangle), and grid constraint validation and consistency checking (partially filled 9x9 number board).

Solve remembered OA coding tasks

Company: Upstart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

The online assessment reportedly had five coding questions, but only the following three were described clearly enough to reconstruct: 1. **Find the top three companies by average stock price** You are given a mapping from company name to a list of its daily stock prices over several days. Compute the average stock price for each company and return the names of the **three companies with the highest average price**. If there are fewer than three companies, return all of them. If two companies have the same average, break ties by company name in ascending lexicographic order. 2. **Compute the bounding rectangle of a set of points** You are given a list of 2D coordinates `[(x1, y1), (x2, y2), ..., (xn, yn)]`. Return four values: - the minimum `x` value, - the minimum `y` value, - `max_x - min_x`, - `max_y - min_y`. In other words, return the lower-left corner, width, and height of the smallest axis-aligned rectangle that contains all points. 3. **Validate a partially filled 9x9 number board** You are given a 9x9 grid where each cell contains either a digit `'1'` through `'9'` or `'.'` for empty. Determine whether the current board state is valid under these rules: - no digit may appear more than once in any row, - no digit may appear more than once in any column, - no digit may appear more than once in any 3x3 subgrid. The other two OA questions were not described clearly enough to reconstruct.

Quick Answer: This set of problems evaluates skills in data aggregation and ordering (identifying top averages), computational geometry and extrema calculation (axis-aligned bounding rectangle), and grid constraint validation and consistency checking (partially filled 9x9 number board).

Top Three Companies by Average Stock Price

You are given a mapping from company name to a list of its daily stock prices over several days. Compute the average stock price for each company and return the names of the three companies with the highest average price. Rules: - If there are fewer than three companies, return all of them. - If two companies have the same average, break ties by company name in ascending lexicographic order. Return the company names as a list, ordered from highest average to lowest (with lexicographic tie-break). Example: Input: {"A": [10, 20, 30], "B": [5, 5, 5], "C": [100], "D": [40, 40]} Averages: A=20, B=5, C=100, D=40 Output: ["C", "D", "A"]

Constraints

0 <= number of companies
Each price list has at least one price
Prices are integers (or floats)
Company names are unique strings

Examples

Input: ({'A': [10, 20, 30], 'B': [5, 5, 5], 'C': [100], 'D': [40, 40]},)

Expected Output: ['C', 'D', 'A']

Explanation: Averages: A=20, B=5, C=100, D=40. Top three by average: C(100), D(40), A(20).

Input: ({'X': [10], 'Y': [10]},)

Expected Output: ['X', 'Y']

Explanation: Both average 10; fewer than three companies, so return all, tie-broken by name: X then Y.

Hints

Compute the average for every company first.
Sort by average descending, then by company name ascending for ties.
Slice the first three entries; if there are fewer than three companies, the slice naturally returns all of them.

Bounding Rectangle of a Set of Points

You are given a list of 2D coordinates [(x1, y1), (x2, y2), ..., (xn, yn)]. Return four values describing the smallest axis-aligned rectangle that contains all the points: - the minimum x value, - the minimum y value, - max_x - min_x (the width), - max_y - min_y (the height). Return the four values as a list [min_x, min_y, width, height]. Example: Input: [[1, 2], [3, 4], [5, 0]] min_x = 1, min_y = 0, width = 5 - 1 = 4, height = 4 - 0 = 4 Output: [1, 0, 4, 4]

Constraints

1 <= number of points
Each point is a pair [x, y] of integers
Coordinates may be negative

Examples

Input: ([[1, 2], [3, 4], [5, 0]],)

Expected Output: [1, 0, 4, 4]

Explanation: min_x=1, min_y=0, max_x=5, max_y=4 -> width=4, height=4.

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

Expected Output: [0, 0, 0, 0]

Explanation: Single point: corner at (0,0), zero width and height.

Hints

Track the minimum and maximum x separately, and the minimum and maximum y separately.
Width is max_x - min_x; height is max_y - min_y.
A single point gives width and height of 0.

Validate a Partially Filled 9x9 Number Board

You are given a 9x9 grid where each cell contains either a digit '1' through '9' or '.' for an empty cell. Determine whether the current board state is valid under these rules: - no digit may appear more than once in any row, - no digit may appear more than once in any column, - no digit may appear more than once in any 3x3 subgrid. The board does not need to be solvable or complete — only the currently filled cells must satisfy the rules. Return True if the board is valid, False otherwise. This is the classic 'Valid Sudoku' board-validation problem.

Constraints

board is exactly 9 rows by 9 columns
each cell is a single character '1'-'9' or '.'
the board need not be complete or solvable

Examples

Input: ([['5','3','.','.','7','.','.','.','.'],['6','.','.','1','9','5','.','.','.'],['.','9','8','.','.','.','.','6','.'],['8','.','.','.','6','.','.','.','3'],['4','.','.','8','.','3','.','.','1'],['7','.','.','.','2','.','.','.','6'],['.','6','.','.','.','.','2','8','.'],['.','.','.','4','1','9','.','.','5'],['.','.','.','.','8','.','.','7','9']],)

Expected Output: True

Explanation: The canonical valid Sudoku starting board: no row, column, or box has a repeat.

Input: ([['8','3','.','.','7','.','.','.','.'],['6','.','.','1','9','5','.','.','.'],['.','9','8','.','.','.','.','6','.'],['8','.','.','.','6','.','.','.','3'],['4','.','.','8','.','3','.','.','1'],['7','.','.','.','2','.','.','.','6'],['.','6','.','.','.','.','2','8','.'],['.','.','.','4','1','9','.','.','5'],['.','.','.','.','8','.','.','7','9']],)

Expected Output: False

Explanation: The 5 at (0,0) was changed to 8; now column 0 has two 8's (rows 0 and 3) and the top-left box also has two 8's. Invalid.

Hints

Use one set per row, one per column, and one per 3x3 box to track seen digits.
Map cell (r, c) to its box index with (r // 3) * 3 + (c // 3).
Skip '.' cells; on any duplicate insertion into a row/column/box set, the board is invalid.