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 Technical Screen rounds at Upstart.

What role is this question designed for?

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

Implement Three Assessment Functions | Upstart Coding Question

Quick Overview

This multi-part problem evaluates competency in geometric bounds computation and coordinate arithmetic, record filtering and aggregation under threshold constraints, and constant-time arithmetic reasoning for constrained movement across discrete grids.

Implement Three Assessment Functions

Company: Upstart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

An online assessment contains three independent programming tasks. Implement each function clearly and efficiently. 1. **Compute coordinate bounds** - Input: a non-empty list of 2D integer coordinates `[(x1, y1), (x2, y2), ...]`. - Return: `[minX, minY, width, height]`, where `minX` is the smallest x-coordinate, `minY` is the smallest y-coordinate, `width = maxX - minX`, and `height = maxY - minY`. 2. **Find the highest eligible score** - Input: a list of records `(name, score)` and an integer `threshold`. - Filter out every record whose `score > threshold`. - Among the remaining records, find the maximum score and return the corresponding `name`. - If multiple records tie for the maximum eligible score, return the name that appears first in the input. - If no record is eligible, return `null` or the language-appropriate equivalent. 3. **Move across a server grid efficiently** - You are given a rectangular grid of servers with `width` columns and `height` rows. Coordinates are zero-indexed: `x` is the column and `y` is the row, so valid coordinates satisfy `0 <= x < width` and `0 <= y < height`. - Implement `solve(x, y, direction, width, height, maxAttempts)`. - `direction` is one of the eight directions: `"U"`, `"D"`, `"L"`, `"R"`, `"UR"`, `"DR"`, `"UL"`, or `"DL"`. - Starting from `(x, y)`, move one cell at a time in `direction`, but stop as soon as the next move would leave the grid or after making `maxAttempts` moves, whichever comes first. - Return the final coordinate `[finalX, finalY]`, representing the compromised server reached. - The grid size and `maxAttempts` may be very large, so the solution should compute the result in `O(1)` time rather than simulating every step.

Quick Answer: This multi-part problem evaluates competency in geometric bounds computation and coordinate arithmetic, record filtering and aggregation under threshold constraints, and constant-time arithmetic reasoning for constrained movement across discrete grids.

Part 1: Compute Coordinate Bounds

Given a non-empty list of 2D integer points, return [minX, minY, width, height], where minX is the smallest x-value, minY is the smallest y-value, width = maxX - minX, and height = maxY - minY.

Constraints

1 <= len(points) <= 200000
-10^9 <= x, y <= 10^9

Examples

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

Expected Output: [-1, 2, 4, 3]

Explanation: minX = -1, minY = 2, maxX = 3, and maxY = 5.

Input: ([(7, -3)],)

Expected Output: [7, -3, 0, 0]

Explanation: A single point forms a zero-width, zero-height bounding box.

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

Expected Output: [-5, -8, 4, 6]

Explanation: minX = -5, minY = -8, maxX = -1, and maxY = -2.

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

Expected Output: [0, 0, 2, 5]

Explanation: The points span x from 0 to 2 and y from 0 to 5.

Hints

Track the smallest and largest x and y values in one pass.
If there is only one point, both width and height are 0.

Part 2: Find the Highest Eligible Score

Given a list of records (name, score) and an integer threshold, ignore every record whose score is greater than threshold. Among the remaining records, return the name with the highest score. If multiple eligible records tie for the highest score, return the one that appears first in the input. If no record is eligible, return None.

Constraints

0 <= len(records) <= 200000
Each name is a string
-10^9 <= score, threshold <= 10^9

Examples

Input: ([('Alice', 70), ('Bob', 85), ('Cara', 85), ('Dan', 90)], 85)

Expected Output: 'Bob'

Explanation: Dan is filtered out, and Bob and Cara tie at 85. Bob appears first.

Input: ([('A', 10), ('B', 20)], 5)

Expected Output: None

Explanation: Both scores are above the threshold, so no record is eligible.

Input: ([], 100)

Expected Output: None

Explanation: An empty list has no eligible record.

Input: ([('Solo', 50)], 50)

Expected Output: 'Solo'

Explanation: The only record is eligible and must be returned.

Input: ([('Mia', -2), ('Noah', -5), ('Oli', -2)], -2)

Expected Output: 'Mia'

Explanation: Mia and Oli tie for the highest eligible score of -2, and Mia appears first.

Hints

Scan once and keep track of the best eligible score seen so far.
To preserve the first name on ties, only replace the answer when you find a strictly larger eligible score.

Part 3: Move Across a Server Grid Efficiently

You are on a rectangular grid of servers with width columns and height rows. Starting from (x, y), move one cell at a time in the given direction until the next move would leave the grid or you have made maxAttempts moves. Directions use row-style coordinates: U means y - 1, D means y + 1, L means x - 1, and R means x + 1. Diagonal directions combine these moves. Because width, height, and maxAttempts can be very large, compute the final coordinate in O(1) time.

Constraints

1 <= width, height <= 10^18
0 <= x < width
0 <= y < height
direction is one of 'U', 'D', 'L', 'R', 'UR', 'DR', 'UL', 'DL'
0 <= maxAttempts <= 10^18

Examples

Input: (1, 1, 'UR', 5, 4, 10)

Expected Output: [2, 0]

Explanation: From (1, 1), moving up-right is blocked after 1 step because the next move would leave the top edge.

Input: (3, 2, 'DL', 8, 6, 2)

Expected Output: [1, 4]

Explanation: Two down-left moves are possible, and maxAttempts is 2.

Input: (0, 0, 'UL', 10, 10, 5)

Expected Output: [0, 0]

Explanation: The very first move would leave the grid, so no movement occurs.

Input: (0, 0, 'R', 3, 3, 0)

Expected Output: [0, 0]

Explanation: With zero allowed attempts, the starting coordinate is returned.

Input: (5, 5, 'D', 10, 1000000000, 1000000000000)

Expected Output: [5, 999999999]

Explanation: You can move down until the last row, which is reached long before maxAttempts runs out.

Hints

Convert direction into a step pair (dx, dy).
Find how many steps you can take before hitting an x-boundary and a y-boundary, then take the minimum of those values and maxAttempts.

Quick Overview