Capital One Applied Researcher Interview Experience — CodeSignal OA with a Tetris-Style Block-Placement Problem

A friend referred me to Capital One (C1). After the recruiter phone screen, they sent a CodeSignal Online Assessment, which had to be completed within 7-10 days — 4 questions, 70 minutes total. I got the link last Friday and finished it this Tuesday.

I had grinded LeetCode and the C1-tagged questions from the last three months on 1point3acres, but only the first question actually overlapped. My feeling is that C1 cares more about simulation and problem-solving approach than heavy algorithms.

Question 1: Easy. Given an array visit of a website's daily view counts, return the index of the Nth day such that the cumulative views up through that day exceed a target. The approach is roughly:

if sum(visit[:i]) >= target:
    return i - 1

Question 2: Easy-medium. You're given an algorithm described in words and have to implement it in code. (Trying my best to remember the exact wording.)

Input is a non-negative array nums.
Initialize res = 0.
Step 1: scan from left to right and find the first non-negative number x.
Step 2: starting from the number right after x, compare each subsequent number to x in order; if it's less than x, go to step 3; otherwise subtract x from it.
Step 3: res += x.
Step 4: go back to step 1.
When the algorithm terminates, return res.

Question 3: Medium. Kind of like Tetris. Five block shapes are predefined — 'A', 'B', 'C', 'D', 'E'. You're given a list containing the arrival order of those letters, and you have to return an m x n board with all the blocks from the list placed on it without overlapping. Each block has to be placed at the position with the smallest possible row and column, and the problem guarantees a solution exists. Brute force works: for each incoming block, scan all positions top-to-bottom, left-to-right, and place it at the first position where it fits. This one had a lot of code, and the IDE didn't allow copy-paste, so writing out all the condition checks and assignments by hand was painful.

Question 4: Medium. The heights of the houses on a block are stored in an array nums. To make the block look nice, the heights need to either strictly increase by 1 from left to right, or strictly decrease by 1 from left to right. Each operation increases one house's height by 1. Return the minimum number of operations needed to make the block look nice.

Approach: separately find the minimum number of operations to make the array a +1-increasing sequence and a -1-decreasing sequence, then take the smaller of the two.

For the +1-increasing requirement, think of the array as a bar chart A, and you need to find a +1-increasing bar chart B that fully covers A (i.e. B[i] >= A[i] everywhere). The difference in area between the two bar charts is the minimum number of operations to turn A into B. In code:

num_ops = 0  # return value
ascent_arr = list(range(len(nums)))
min_adjust = 0
for i in range(len(nums)):
    min_adjust = max(min_adjust, nums[i] - ascent_arr[i])
for i in range(len(nums)):
    ascent_arr[i] += min_adjust
for i in range(len(nums)):
    num_ops += (ascent_arr[i] - nums[i])

The -1-decreasing case works the same way.