Introduction

In this blog post, we'll share the most commonly asked coding interview questions at Capital One. If you don't have months to study for your interviews, you can use AI tools like Chatmagic to generate solutions quickly and efficiently - helping you pass the interviews and get the job offer!

Problem #1: Simple Bank System

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)th account having an initial balance of balance[i]. Execute all the valid transactions. A transaction is valid if: The given account number(s) are between 1 and n, and The amount of money withdrawn or transferred from is less than or equal to the balance of the account. Implement the Bank class: Bank(long[] balance) Initializes the object with the 0-indexed integer array balance. boolean transfer(int account1, int account2, long money) Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise. boolean deposit(int account, long money) Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise. boolean withdraw(int account, long money) Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise. Example 1: Input ["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"] [[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]] Output [null, true, true, true, false, false] Explanation Bank bank = new Bank([10, 100, 20, 50, 30]); bank.withdraw(3, 10); // return true, account 3 has a balance of $20, so it is valid to withdraw $10. // Account 3 has $20 - $10 = $10. bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20. // Account 5 has $30 - $20 = $10, and account 1 has $10 + $20 = $30. bank.deposit(5, 20); // return true, it is valid to deposit $20 to account 5. // Account 5 has $10 + $20 = $30. bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10, // so it is invalid to transfer $15 from it. bank.withdraw(10, 50); // return false, it is invalid because account 10 does not exist. Constraints: n == balance.length 1 <= n, account, account1, account2 <= 105 0 <= balance[i], money <= 1012 At most 104 calls will be made to each function transfer, deposit, withdraw.

Topics: Array, Hash Table, Design, Simulation

Problem #2: Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order. Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5] Example 2: Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7] Constraints: m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100

Topics: Array, Matrix, Simulation

Problem #3: Block Placement Queries

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis. You are given a 2D array queries, which contains two types of queries: For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked. For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate. Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise. Example 1: Input: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]] Output: [false,true,true] Explanation: For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3. Example 2: Input: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]] Output: [true,true,false] Explanation: Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7. Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2. Constraints: 1 <= queries.length <= 15 104 2 <= queries[i].length <= 3 1 <= queries[i][0] <= 2 1 <= x, sz <= min(5 104, 3 * queries.length) The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked. The input is generated such that there is at least one query of type 2.

Topics: Array, Binary Search, Binary Indexed Tree, Segment Tree

Problem #4: Count Operations to Obtain Zero

You are given two non-negative integers num1 and num2. In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2. For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1. Return the number of operations required to make either num1 = 0 or num2 = 0. Example 1: Input: num1 = 2, num2 = 3 Output: 3 Explanation: - Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1. - Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1. - Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1. Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations. So the total number of operations required is 3. Example 2: Input: num1 = 10, num2 = 10 Output: 1 Explanation: - Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0. Now num1 = 0 and num2 = 10. Since num1 == 0, we are done. So the total number of operations required is 1. Constraints: 0 <= num1, num2 <= 105

Topics: Math, Simulation

Problem #5: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit. Example 1: Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2. Example 2: Input: nums = [10,1,2,4,7,2], limit = 5 Output: 4 Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5. Example 3: Input: nums = [4,2,2,2,4,4,2,2], limit = 0 Output: 3 Constraints: 1 <= nums.length <= 105 1 <= nums[i] <= 109 0 <= limit <= 109

Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

Problem #6: Text Justification

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left-justified, and no extra space is inserted between words. Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed maxWidth. The input array words contains at least one word. Example 1: Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 Output: [ "This is an", "example of text", "justification. " ] Example 2: Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16 Output: [ "What must be", "acknowledgment ", "shall be " ] Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word. Example 3: Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20 Output: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ] Constraints: 1 <= words.length <= 300 1 <= words[i].length <= 20 words[i] consists of only English letters and symbols. 1 <= maxWidth <= 100 words[i].length <= maxWidth

Topics: Array, String, Simulation

Problem #7: Minimum Operations to Write the Letter Y on a Grid

You are given a 0-indexed n x n grid where n is odd, and grid[r][c] is 0, 1, or 2. We say that a cell belongs to the Letter Y if it belongs to one of the following: The diagonal starting at the top-left cell and ending at the center cell of the grid. The diagonal starting at the top-right cell and ending at the center cell of the grid. The vertical line starting at the center cell and ending at the bottom border of the grid. The Letter Y is written on the grid if and only if: All values at cells belonging to the Y are equal. All values at cells not belonging to the Y are equal. The values at cells belonging to the Y are different from the values at cells not belonging to the Y. Return the minimum number of operations needed to write the letter Y on the grid given that in one operation you can change the value at any cell to 0, 1, or 2. Example 1: Input: grid = [[1,2,2],[1,1,0],[0,1,0]] Output: 3 Explanation: We can write Y on the grid by applying the changes highlighted in blue in the image above. After the operations, all cells that belong to Y, denoted in bold, have the same value of 1 while those that do not belong to Y are equal to 0. It can be shown that 3 is the minimum number of operations needed to write Y on the grid. Example 2: Input: grid = [[0,1,0,1,0],[2,1,0,1,2],[2,2,2,0,1],[2,2,2,2,2],[2,1,2,2,2]] Output: 12 Explanation: We can write Y on the grid by applying the changes highlighted in blue in the image above. After the operations, all cells that belong to Y, denoted in bold, have the same value of 0 while those that do not belong to Y are equal to 2. It can be shown that 12 is the minimum number of operations needed to write Y on the grid. Constraints: 3 <= n <= 49 n == grid.length == grid[i].length 0 <= grid[i][j] <= 2 n is odd.

Topics: Array, Hash Table, Matrix, Counting

Problem #8: Simplify Path

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path. The rules of a Unix-style file system are as follows: A single period '.' represents the current directory. A double period '..' represents the previous/parent directory. Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'. Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names. The simplified canonical path should follow these rules: The path must start with a single slash '/'. Directories within the path must be separated by exactly one slash '/'. The path must not end with a slash '/', unless it is the root directory. The path must not have any single or double periods ('.' and '..') used to denote current or parent directories. Return the simplified canonical path. Example 1: Input: path = "/home/" Output: "/home" Explanation: The trailing slash should be removed. Example 2: Input: path = "/home//foo/" Output: "/home/foo" Explanation: Multiple consecutive slashes are replaced by a single one. Example 3: Input: path = "/home/user/Documents/../Pictures" Output: "/home/user/Pictures" Explanation: A double period ".." refers to the directory up a level (the parent directory). Example 4: Input: path = "/../" Output: "/" Explanation: Going one level up from the root directory is not possible. Example 5: Input: path = "/.../a/../b/c/../d/./" Output: "/.../b/d" Explanation: "..." is a valid name for a directory in this problem. Constraints: 1 <= path.length <= 3000 path consists of English letters, digits, period '.', slash '/' or '_'. path is a valid absolute Unix path.

Topics: String, Stack

Problem #10: Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0. Constraints: 1 <= prices.length <= 105 0 <= prices[i] <= 104

Topics: Array, Dynamic Programming