PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCareers

Quick Overview

This multi-part coding question evaluates array manipulation, algorithm simulation, deterministic spatial placement, and constrained optimization competencies across tasks involving cumulative thresholds, iterative subtraction sequences, fixed-shape grid placement, and minimal-increment adjustments for monotonic patterns.

  • medium
  • Capital One
  • Coding & Algorithms
  • Machine Learning Engineer

Solve Four Coding Assessment Tasks

Company: Capital One

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Complete the following four independent coding tasks. ### 1. Find the day a cumulative visit target is reached You are given an array `visits`, where `visits[i]` is the number of website visits on day `i`, and an integer `target`. Return the smallest 0-based day index `i` such that the total number of visits from day `0` through day `i` is at least `target`. If the target is never reached, return `-1`. ### 2. Simulate a repeated subtraction algorithm You are given an array `nums` of non-negative integers. Simulate the following process and return the final value of `res`. Initialize `res = 0`. Repeat: 1. Scan `nums` from left to right and find the first positive value. Call this value `x`. If no positive value exists, stop and return `res`. 2. Starting at that index, scan to the right. For each element: - If the element is less than `x`, stop this scan and go to step 3. - Otherwise, subtract `x` from the element and continue scanning right. 3. Add `x` to `res`. 4. Repeat from step 1. Implement this algorithm exactly. ### 3. Place blocks on a grid You are given an `m x n` empty grid and a list `order` containing block identifiers from the set `{A, B, C, D, E}`. Each identifier corresponds to a fixed block shape represented by a set of relative cell coordinates, such as `[(0, 0), (0, 1)]`. The shape definitions are provided as part of the input or as constants. Process the blocks in the given order. For each incoming block, place it on the grid without rotating it and without overlapping previously placed blocks. A placement is valid if every occupied cell of the block lies inside the grid and is currently empty. For each block, choose the valid placement with the smallest row index for its top-left anchor; if there is a tie, choose the smallest column index. The input is guaranteed to have at least one valid placement for every block. Return the final grid after all blocks have been placed, marking each occupied cell with the block's identifier. ### 4. Minimize increments to make house heights beautiful You are given an array `heights`, where `heights[i]` is the height of the `i`-th house in a street. In one operation, you may increase the height of any single house by `1`. A street is considered beautiful if its heights form one of the following patterns: - Strictly increasing by exactly `1` from left to right: `k, k+1, k+2, ...` - Strictly decreasing by exactly `1` from left to right: `k, k-1, k-2, ...` You may only increase heights, never decrease them. Return the minimum number of operations needed to make the street beautiful under either pattern.

Quick Answer: This multi-part coding question evaluates array manipulation, algorithm simulation, deterministic spatial placement, and constrained optimization competencies across tasks involving cumulative thresholds, iterative subtraction sequences, fixed-shape grid placement, and minimal-increment adjustments for monotonic patterns.

Part 1: First Day Cumulative Visits Reach Target

Given a list 'visits' where visits[i] is the number of website visits on day i, return the smallest 0-based day index i such that the cumulative total visits[0] + visits[1] + ... + visits[i] is at least 'target'. If the target is never reached, return -1.

Constraints

  • 0 <= len(visits) <= 200000
  • 0 <= visits[i] <= 1000000000
  • 1 <= target <= 1000000000000000000

Examples

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

Expected Output: 1

Explanation: Running totals are 3, 5, 9, 10. The target is first reached on day 1.

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

Expected Output: -1

Explanation: The total visits are only 3, so the target is never reached.

Input: ([], 1)

Expected Output: -1

Explanation: There are no days at all, so the target cannot be reached.

Input: ([7], 7)

Expected Output: 0

Explanation: The very first day already reaches the target.

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

Expected Output: 0

Explanation: The cumulative total is already 2 on day 0.

Hints

  1. Walk through the array once while keeping a running sum.
  2. As soon as the running sum becomes at least target, you can return that index immediately.

Part 2: Repeated Left-to-Right Subtraction Simulation

You are given a list 'nums' of non-negative integers. Simulate this process exactly: start with res = 0. Repeatedly find the first positive value x when scanning from left to right. If none exists, return res. Starting from that index, keep moving right while each current element is at least x, subtracting x from each such element. Stop that rightward scan at the first element that is less than x. Then add x to res and repeat.

Constraints

  • 0 <= len(nums) <= 2000
  • 0 <= nums[i] <= 10000
  • sum(nums) <= 200000

Examples

Input: ([2, 2, 3],)

Expected Output: 3

Explanation: First subtract 2 from the whole prefix [2,2,3] until it becomes [0,0,1], so res = 2. Then subtract 1 from the final element, giving res = 3.

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

Expected Output: 5

Explanation: Round 1 uses x = 3 and only affects the first element. Then x = 1 affects the last two positive elements, and the final 1 is removed in the last round.

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

Expected Output: 0

Explanation: There is no positive value to begin with, so the algorithm stops immediately.

Input: ([],)

Expected Output: 0

Explanation: An empty list has no positive value, so the result is 0.

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

Expected Output: 3

Explanation: First subtract 1 across all three elements to get [0,2,0], making res = 1. Then subtract 2 from the middle element, giving a final res of 3.

Hints

  1. A direct simulation is acceptable here; focus on matching the rules exactly.
  2. After choosing x, do not skip over an element smaller than x. You must stop that scan immediately.

Part 3: Row-Major Block Placement on a Grid

You are given an empty m x n grid and a list 'order' of block identifiers. Use these fixed, non-rotatable shapes, all defined relative to anchor (0, 0): A = [(0,0)], B = [(0,0),(0,1)], C = [(0,0),(1,0)], D = [(0,0),(1,0),(1,1)], E = [(0,0),(0,1),(1,0),(1,1)]. Process blocks in the given order. For each block, place it at the valid anchor with the smallest row index; if tied, choose the smallest column index. A placement is valid only if every occupied cell is inside the grid and currently empty. Return the final grid as a list of strings, using the block letter for occupied cells and '.' for empty cells.

Constraints

  • 1 <= m, n <= 20
  • 0 <= len(order) <= 200
  • Each value in order is one of 'A', 'B', 'C', 'D', 'E'
  • The input guarantees that every block in order has at least one valid placement

Examples

Input: (3, 4, ['B', 'C', 'A'])

Expected Output: ['BBCA', '..C.', '....']

Explanation: B is placed at (0,0), C at (0,2), and then A fits at (0,3).

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

Expected Output: ['A']

Explanation: The single-cell block fills the only cell.

Input: (4, 4, ['E', 'D', 'B'])

Expected Output: ['EED.', 'EEDD', 'BB..', '....']

Explanation: E goes at (0,0), D then fits first at (0,2), and B finally fits first at (2,0).

Input: (2, 3, ['C', 'C', 'C'])

Expected Output: ['CCC', 'CCC']

Explanation: Each vertical domino is placed at columns 0, 1, and 2 respectively.

Input: (2, 2, [])

Expected Output: ['..', '..']

Explanation: No blocks are placed, so the grid stays empty.

Hints

  1. Scan possible anchors in row-major order. That automatically enforces the tie-breaking rule.
  2. Represent each block as a short list of relative coordinates, and verify all of them before placing the block.

Part 4: Minimum Increments to Make House Heights Beautiful

You are given a list 'heights' where heights[i] is the height of the i-th house. In one operation, you may increase any single house by 1. A street is beautiful if its final heights match either k, k+1, k+2, ... or k, k-1, k-2, ... for some integer k. You may only increase heights, never decrease them. Return the minimum number of operations needed.

Constraints

  • 0 <= len(heights) <= 200000
  • 0 <= heights[i] <= 1000000000

Examples

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

Expected Output: 0

Explanation: The street already matches an increasing-by-1 pattern.

Input: ([5, 4, 3],)

Expected Output: 0

Explanation: The street already matches a decreasing-by-1 pattern.

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

Expected Output: 3

Explanation: The best target is decreasing: [4, 3, 2], which needs 1 + 2 + 0 = 3 increments.

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

Expected Output: 3

Explanation: Either [2, 3, 4] or [4, 3, 2] works, and both require 3 total increments.

Input: ([],)

Expected Output: 0

Explanation: An empty street needs no changes.

Hints

  1. For the increasing pattern k + i, the smallest valid k is max(heights[i] - i).
  2. Compute the total cost for both target patterns separately, then return the smaller one.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • Careers
  • 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

  • Write SQL using joins and window functions - Capital One (medium)
  • Review Preprocessing Code and Tests - Capital One (easy)
  • Remove nodes with a given value - Capital One (medium)
  • Solve multiple algorithmic interview questions - Capital One (hard)
  • Place Pieces on a Grid - Capital One (medium)