Solve Four Coding Assessment Tasks
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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
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
- Walk through the array once while keeping a running sum.
- As soon as the running sum becomes at least target, you can return that index immediately.
Part 2: Repeated Left-to-Right Subtraction Simulation
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
- A direct simulation is acceptable here; focus on matching the rules exactly.
- 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
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
- Scan possible anchors in row-major order. That automatically enforces the tie-breaking rule.
- 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
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
- For the increasing pattern k + i, the smallest valid k is max(heights[i] - i).
- Compute the total cost for both target patterns separately, then return the smaller one.