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.

Hints

  1. Track the smallest and largest x and y values in one pass.
  2. 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.

Hints

  1. Scan once and keep track of the best eligible score seen so far.
  2. 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.

Hints

  1. Convert direction into a step pair (dx, dy).
  2. 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.

Loading coding console...