PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part Coding & Algorithms question evaluates algorithmic problem-solving skills and mastery of core competencies including temporal window reasoning, greedy optimization under repeated operations, bracket-matching/parsing, log aggregation and parsing, and combinatorial placement on grids.

  • hard
  • NVIDIA
  • Coding & Algorithms
  • Software Engineer

Implement short algorithms on logs, grids, and strings

Company: NVIDIA

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given several independent short coding tasks. For each task, implement the requested function(s). Assume standard library data structures are allowed. ## 1) Detect CPU temperature spikes You receive CPU temperature readings as a list of pairs `(timestamp, tempC)` sorted by `timestamp` ascending. Define a **spike** at reading `i` (time `t_i`, temperature `x_i`) if there exists some earlier reading `j < i` such that: - `t_i - t_j <= windowSeconds`, and - `x_i - x_j >= deltaC`. **Input:** - `readings: List[Tuple[int timestamp, int tempC]]` (timestamps are seconds) - `windowSeconds: int` - `deltaC: int` **Output:** - Return the list of timestamps `t_i` where reading `i` is a spike. **Constraints (example):** up to `2e5` readings. --- ## 2) Minimum possible sum after K operations Given an array of non-negative integers `a` and an integer `k`, you may perform the following operation exactly `k` times: - Choose an index `i` and replace `a[i]` with `ceil(a[i] / 2)`. **Goal:** minimize the final sum of the array. **Input:** `a: List[int]`, `k: int` **Output:** the minimum achievable sum after `k` operations. **Constraints (example):** `n` up to `2e5`, values up to `1e9`, `k` up to `2e5`. --- ## 3) Verify matching brackets in a mathematical expression Given a string `s` representing a mathematical expression containing characters including `()[]{}` and other non-bracket characters, determine whether the brackets are correctly matched and nested. **Input:** `s: str` **Output:** `True` if valid, else `False`. **Notes:** Non-bracket characters should be ignored. --- ## 4) Aggregate HTTP logs by status code You are given log lines. Each line contains a status code and a response time in milliseconds: Format: `"<statusCode> <responseTimeMs>"` Example: `"200 153"`, `"500 12"`. **Task:** aggregate by `statusCode`: - count of requests - average response time (as a floating-point value) **Input:** `logs: List[str]` **Output:** a mapping/dictionary `statusCode -> (count, avgResponseTime)`. **Edge cases:** empty input; malformed lines may be ignored (state and implement a consistent rule). --- ## 5) Tree planting on a grid (no adjacent trees) You are given an `m x n` grid `land` with: - `1` meaning an existing tree - `0` meaning empty land You may plant additional trees on empty cells, but **no two trees** (existing or newly planted) may be adjacent in the 4-neighborhood (up/down/left/right). **Task:** determine a set of cells to plant new trees that is **maximum in size**. **Input:** `land: List[List[int]]` **Output:** - `maxNewTrees: int`, the maximum number of new trees that can be planted - optionally (if asked), one valid resulting grid configuration **Constraints (example):** `m, n` up to ~`50` (state assumptions and optimize accordingly).

Quick Answer: This multi-part Coding & Algorithms question evaluates algorithmic problem-solving skills and mastery of core competencies including temporal window reasoning, greedy optimization under repeated operations, bracket-matching/parsing, log aggregation and parsing, and combinatorial placement on grids.

Part 1: Detect CPU Temperature Spikes

You are given CPU temperature readings as pairs of timestamp and temperature, sorted by timestamp in ascending order. A reading i is a spike if there exists an earlier reading j such that the two readings are at most windowSeconds apart and the temperature increased by at least deltaC from j to i. Return the timestamps of all spike readings.

Constraints

  • 0 <= len(readings) <= 200000
  • readings is sorted by timestamp ascending; timestamps may repeat
  • 0 <= windowSeconds <= 10^9
  • 0 <= deltaC <= 10^9
  • Temperatures are integers

Examples

Input: ([(1, 40), (3, 42), (5, 50), (10, 45), (12, 60)], 5, 8)

Expected Output: [5, 12]

Explanation: At t=5, temperature rose from 40 to 50 within 4 seconds. At t=12, it rose from 45 to 60 within 2 seconds.

Input: ([], 10, 5)

Expected Output: []

Explanation: No readings means no spikes.

Input: ([(5, 40), (5, 45), (6, 50)], 0, 5)

Expected Output: [5]

Explanation: The second reading has the same timestamp as the first, so it is within a 0-second window.

Input: ([(1, 30), (10, 50)], 5, 20)

Expected Output: []

Explanation: The temperature increase is large enough, but the readings are too far apart in time.

Hints

  1. For each reading, you only need to know the minimum temperature among earlier readings still inside the time window.
  2. Use a monotonic deque to maintain candidate earlier readings with increasing temperatures.

Part 2: Minimum Possible Sum After K Halving Operations

You are given an array of non-negative integers a and an integer k. Exactly k times, choose one element and replace it with ceil(value / 2). Return the minimum possible final sum. If the array is empty, return 0.

Constraints

  • 0 <= len(a) <= 200000
  • 0 <= a[i] <= 10^9
  • 0 <= k <= 200000
  • The answer may exceed 32-bit integer range

Examples

Input: ([10, 20, 7], 4)

Expected Output: 14

Explanation: Apply operations to 20, 10, 10, and 7, producing values such as [5, 5, 4] with sum 14.

Input: ([5], 3)

Expected Output: 1

Explanation: 5 becomes 3, then 2, then 1.

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

Expected Output: 2

Explanation: Values 0 and 1 do not decrease under the operation.

Input: ([], 5)

Expected Output: 0

Explanation: The empty array has sum 0.

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

Expected Output: 11

Explanation: No operations are performed.

Hints

  1. Each operation reduces an element x by floor(x / 2).
  2. The best next operation is always on the current largest element.

Part 3: Verify Matching Brackets in an Expression

Given a string representing a mathematical expression, determine whether all brackets are correctly matched and nested. The bracket types are (), [], and {}. Ignore all non-bracket characters.

Constraints

  • 0 <= len(s) <= 200000
  • s may contain arbitrary non-bracket characters
  • Only (), [], and {} are considered brackets

Examples

Input: ('([x+1] * {y-2})',)

Expected Output: True

Explanation: All brackets are matched and properly nested.

Input: ('([)]',)

Expected Output: False

Explanation: The brackets are crossed rather than nested.

Input: ('abc + 123',)

Expected Output: True

Explanation: There are no brackets, so the expression is valid.

Input: ('',)

Expected Output: True

Explanation: The empty string has no unmatched brackets.

Input: ('((x)',)

Expected Output: False

Explanation: One opening parenthesis is never closed.

Hints

  1. Use a stack to remember currently open brackets.
  2. When you see a closing bracket, it must match the most recent unmatched opening bracket.

Part 4: Aggregate HTTP Logs by Status Code

You are given HTTP log lines. Each valid line contains exactly two whitespace-separated integers: a status code and a response time in milliseconds. Aggregate valid lines by status code and return the request count and average response time for each code. Malformed lines are ignored. A line is considered malformed if it does not have exactly two fields, either field is not an integer, the status code is outside 100..599, or the response time is negative.

Constraints

  • 0 <= len(logs) <= 200000
  • Each log line length is reasonable for splitting by whitespace
  • Valid status codes are integers from 100 to 599 inclusive
  • Valid response times are non-negative integers

Examples

Input: (['200 100', '500 12', '200 200', '404 50'],)

Expected Output: {200: (2, 150.0), 500: (1, 12.0), 404: (1, 50.0)}

Explanation: Status 200 has two response times, 100 and 200, with average 150.0.

Input: ([],)

Expected Output: {}

Explanation: No logs produce an empty aggregation.

Input: (['200 100', 'bad line', '999 1', '404 -3', '500 10 extra', '500 20'],)

Expected Output: {200: (1, 100.0), 500: (1, 20.0)}

Explanation: Malformed lines and invalid status/response values are ignored.

Input: (['201 0', '201 5', '302 10'],)

Expected Output: {201: (2, 2.5), 302: (1, 10.0)}

Explanation: Multiple spaces are accepted because splitting is whitespace-based.

Input: (['hello', '600 1', '200 -1', '204 two'],)

Expected Output: {}

Explanation: All lines are malformed under the stated rules.

Hints

  1. Keep two dictionaries per status code: one for counts and one for total response time.
  2. Parse defensively; ignore invalid lines instead of raising an error.

Part 5: Maximum Tree Planting on a Grid

You are given an m x n grid land where 1 means an existing tree and 0 means empty land. You may plant new trees only on empty cells. No two trees, including existing and newly planted trees, may be adjacent vertically or horizontally. Return the maximum number of new trees that can be planted. Assume the existing trees are already non-adjacent.

Constraints

  • 0 <= m <= 50
  • 0 <= n <= 50
  • land[r][c] is either 0 or 1
  • Existing trees are guaranteed not to be adjacent in the 4-neighborhood

Examples

Input: ([],)

Expected Output: 0

Explanation: An empty grid has no place to plant.

Input: ([[0]],)

Expected Output: 1

Explanation: A single empty cell can contain one new tree.

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

Expected Output: 3

Explanation: On a row of length 5, plant at positions 0, 2, and 4.

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

Expected Output: 5

Explanation: A checkerboard pattern allows 5 planted trees on a 3x3 grid.

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

Expected Output: 4

Explanation: The center tree blocks its four neighbors; all four corners can be planted.

Hints

  1. Cells occupied by existing trees, and empty cells adjacent to existing trees, cannot be used.
  2. The remaining candidate cells form a bipartite grid graph. The answer is maximum independent set size, which equals vertices minus maximum matching.
Last updated: Jun 18, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute the Final Robot Score - NVIDIA (easy)
  • Return all file paths via DFS - NVIDIA (easy)
  • Implement a disk space manager with eviction - NVIDIA (medium)
  • Implement encode/decode for list of strings - NVIDIA (easy)
  • Implement matrix transpose and KV store - NVIDIA (medium)