Codesignal Software Engineer Interview Questions

## Problem An AI tool flags potentially buggy code regions as `(file, start_line, end_line, confidence)` where confidence is 0.0-1.0. Human reviewers have capacity to manually review at most `B` total lines. Select a subset of flagged regions to maximize total confidence score, subject to: 1. Total lines reviewed <= B. 2. No two selected regions from the same file may overlap. ```python def select_regions( flags: list[tuple[str, int, int, float]], # (file, start, end, confidence) budget: int ) -> list[tuple[str, int, int, float]]: ... ``` **Example:** ``` flags = [ ("a.py", 1, 10, 0.9), ("a.py", 5, 15, 0.8), # overlaps with first ("b.py", 1, 5, 0.7), ] budget = 15 Output: [("a.py",1,10,0.9), ("b.py",1,5,0.7)] # total lines=15, score=1.6 ``` ## Follow-ups - How do you handle the per-file overlap constraint? Is it still a standard knapsack after removing overlaps? - What is the time complexity of your approach? - Extend to support a minimum confidence threshold: only consider regions with confidence >= 0.5.

## Problem You are given an integer array `nums` and a list of mutation operations. Each operation is one of: - `SET i v`: set `nums[i] = v` - `ADD i v`: set `nums[i] += v` - `REVERSE l r`: reverse the subarray `nums[l..r]` in place - `QUERY l r`: return the sum of `nums[l..r]` Process all operations and return the results of all QUERY operations in order. ```python def process_mutations(nums: list[int], ops: list[tuple]) -> list[int]: ... ``` **Example:** ``` nums = [1, 2, 3, 4, 5] ops = [("ADD",1,10),("QUERY",0,2),("REVERSE",0,4),("QUERY",0,4)] Output: [16, 25] # After ADD: [1,12,3,4,5] -> QUERY 0..2 = 1+12+3 = 16 # After REVERSE: [5,4,3,12,1] -> QUERY 0..4 = 25 ``` ## Follow-ups - A naive solution is O(n) per operation. How would a segment tree or BIT help for SET/ADD/QUERY? - The REVERSE operation is the hard part -- what advanced data structure supports O(log n) range reversal? - If there are no REVERSE operations, what is the optimal approach?

## Problem Given an unsorted array of positive integers, count the number of triplets `(a, b, c)` (by index, `i < j < k`) such that `a^2 + b^2 == c^2` (or any permutation: any of the three values can be the hypotenuse). ```python def count_pythagorean_triplets(nums: list[int]) -> int: ... ``` **Example:** ``` Input: [3, 4, 5, 6, 8, 10] Output: 4 Explanation: (3,4,5): 9+16=25 ✓ (3,5,4) same indices different order -- counted once per index triple. (6,8,10): 36+64=100 ✓ (4,?,8)? 4^2=16, 8^2=64, 64-16=48, sqrt(48) not integer. Work through to get exact count. ``` **Constraints:** `3 <= len(nums) <= 1000`, values in `[1, 1000]`. ## Follow-ups - A brute-force O(n^3) solution works for n<=1000. How do you improve to O(n^2) using a hash set? - How does your counting change if the problem asks for distinct value triplets (not index triplets)? - What pre-processing step makes the O(n^2) approach cleaner?

## Problem Implement a multi-level banking system. Operations are applied in order. **Level 1:** Basic accounts. ``` CREATE_ACCOUNT id -> "created" or "error" if exists DEPOSIT id amount -> new balance or "error" if no account WITHDRAW id amount -> new balance or "error" if insufficient funds GET_BALANCE id -> balance or "error" ``` **Level 2:** Transfers and fees. ``` TRANSFER from to amount -> "success" or "error" # Fee: 1% of transfer amount deducted from sender (in addition to amount) ``` **Level 3:** Transaction history. ``` HISTORY id n -> last n transactions as list of strings ``` **Level 4:** Scheduled transfers. ``` SCHEDULE from to amount time -> execute TRANSFER at given time tick TICK -> advance clock by 1, execute due scheduled transfers ``` ## Follow-ups - How do you represent the transaction log efficiently for O(1) append and O(k) recent-k queries? - What happens to a scheduled transfer if the sender has insufficient funds at execution time? - How would you add interest accrual: 2% monthly applied at each TICK that crosses a month boundary?

## Problem A grid of colored bubbles is represented as a 2D array of characters. When a player pops a bubble at `(r, c)`, all connected bubbles of the same color (4-directional flood fill) are removed. Remaining bubbles above the removed region fall down to fill the gap (gravity: bubbles fall straight down, not diagonally). Simulate a sequence of pops and return the grid state after all pops. ```python def simulate_pops(grid: list[list[str]], pops: list[tuple[int,int]]) -> list[list[str]]: # '.' represents empty space ... ``` **Example:** ``` grid = [ ['R','B','R'], ['R','B','B'], ['G','G','B'] ] pops = [(0,0)] # pop 'R' at (0,0), connected R's: (0,0),(1,0) After flood fill remove: [['.',B','R'], ['.','B','B'], ['G','G','B']] After gravity: [['.','B','R'], ['G','B','B'], ['.','G','B']] ``` ## Follow-ups - What is the time complexity per pop operation? - How do you handle chain reactions (removed bubbles expose new connected groups of size >= 3 that auto-pop)? - Extend to 3D (cube grid) -- how does gravity change?

## Problem Given a list of 5 card strings (e.g., `"AS"`, `"10H"`, `"KD"`), classify the poker hand. Cards are rank + suit where rank is one of `A,2,3,...,10,J,Q,K` and suit is `C,D,H,S`. Return the hand rank as a string: `"royal_flush"`, `"straight_flush"`, `"four_of_a_kind"`, `"full_house"`, `"flush"`, `"straight"`, `"three_of_a_kind"`, `"two_pair"`, `"one_pair"`, `"high_card"` ```python def classify_hand(cards: list[str]) -> str: ... ``` **Example:** ``` classify_hand(["10H","JH","QH","KH","AH"]) -> "royal_flush" classify_hand(["2C","2D","2H","3S","3C"]) -> "full_house" classify_hand(["AS","2C","3D","4H","5S"]) -> "straight" ``` **Note:** Ace can be low (A-2-3-4-5) or high (10-J-Q-K-A). ## Follow-ups - How do you handle the low-ace straight edge case cleanly? - Extend to compare two hands and return the winner, including tiebreakers (e.g., higher pair wins). - What changes if the game uses a 54-card deck with 2 Jokers that act as wild cards?

## Problem Given an array of strings `words`, build a "character cascade": for each position `i` (0-indexed), collect the character at index `i` from every string that has length > `i`. Concatenate these characters top-to-bottom to form column strings, then return the column strings joined by spaces. ```python def character_cascade(words: list[str]) -> str: ... ``` **Example:** ``` words = ["cat", "do", "bird"] Column 0: 'c','d','b' -> "cdb" Column 1: 'a','o','i' -> "aoi" Column 2: 't','r' -> "tr" ("do" has no index 2) Column 3: 'd' -> "d" Output: "cdb aoi tr d" ``` **Follow-up variant:** Return each column reversed. ## Follow-ups - What is the time and space complexity in terms of total characters across all words? - Extend: given a target string `t`, find which column contains the most characters from `t` (by frequency). - How would you parallelize this if the word list has 10 million entries and each word is up to 1000 chars?

## Problem Full multi-level cloud storage implementation. Must pass all unit tests to unlock subsequent levels. **Level 1:** Core file operations. - `ADD_FILE path size` -> "added" or "error" if path exists - `COPY_FILE src dst` -> "copied" or "error" - `GET_FILE_SIZE path` -> size or "error" **Level 2:** Prefix/suffix search. - `FIND_FILES prefix suffix` -> all files matching both; sort by size desc, then name asc. Return as `"name(size)"`. **Level 3:** User management. - `ADD_USER user_id capacity` - `ADD_FILE_BY user_id path size` -> adds file; if user over capacity, delete their largest files until under capacity. - `UPDATE_CAPACITY user_id new_cap` **Level 4:** Compression. - `COMPRESS_FILE path` -> halves file size (floor), appends `".compressed"` to name. - `DECOMPRESS_FILE path` -> reverses compression. Error if file was never compressed or already decompressed. ## Follow-ups - How do you efficiently find a user's largest file for eviction in Level 3? - In Level 4, how do you track the original size to restore it exactly on decompress? - What is the time complexity of `FIND_FILES` across n files?

## Problem You are given a list of service latency measurements (in ms) over time as `(timestamp, latency)`. A period is "consistent" if every measurement within it falls within `[median - d, median + d]` for a given tolerance `d`, where median is computed over the entire period. Find the longest consistent period (contiguous subarray of measurements). ```python def longest_consistent_period( measurements: list[tuple[int, float]], d: float ) -> tuple[int, int]: # return (start_index, end_index) inclusive ... ``` **Example:** ``` measurements = [(0,100),(1,105),(2,98),(3,200),(4,102)] d = 10 Output: (0, 2) # median of [100,105,98]=100, all within [90,110]. (3) breaks it. ``` **Constraints:** `n <= 10^4`. ## Follow-ups - Computing the median for every subarray is expensive. What is the brute-force complexity? Can binary search help? - A sliding window does not directly apply because adding an element changes the median. How do you handle this? - Extend: return the start/end timestamps (not indices) of all maximal consistent periods.

## Problem Count the number of valid words in a string based on lexical rules such as allowed characters and punctuation placement. ## Tags strings

## Problem A game field is an `N x M` grid. Each cell is either empty (`0`) or contains a power-up (`1`). A player starts at `(0, 0)` and must reach `(N-1, M-1)` moving only right or down. The player collects all power-ups on their path. **Part 1:** Find the path that collects the maximum number of power-ups. **Part 2:** After collecting power-ups along the optimal path, those cells become `0`. Find the maximum power-ups collectible on a second independent path from `(0,0)` to `(N-1,M-1)` on the modified grid. ```python def max_powerups_two_paths(grid: list[list[int]]) -> int: ... ``` **Example:** ``` grid = [[1,1,0],[0,1,1],[0,0,1]] Path 1: (0,0)->(0,1)->(1,1)->(1,2)->(2,2) collects 5. Modified grid: all zeros. Path 2: 0. Total: 5 ``` ## Follow-ups - Can you solve Part 2 by running two simultaneous paths via DP? What are the DP states? - What if movement includes up and left (any direction, no revisit)? How does the complexity change? - Extend to `k` paths. What is the DP formulation?

## Problem Process group chat messages to track or count user mentions based on @username patterns. ## Tags strings, hash_table

## Problem An `N x N` grid has lamps at given positions. Each lamp illuminates its entire row, column, and both diagonals. Given a list of query cells, for each query determine if the cell is illuminated, then turn off the lamp at that cell and all 8 adjacent lamps (if any). ```python def process_queries( n: int, lamps: list[tuple[int,int]], queries: list[tuple[int,int]] ) -> list[int]: # 1 if illuminated at query time, 0 otherwise ... ``` **Example:** ``` n=5, lamps=[(0,0),(1,2)] queries=[(1,1),(1,0)] - Query (1,1): illuminated by (0,0) via diagonal. Output 1. Turn off lamps at (1,1) and neighbors -> turns off (0,0). - Query (1,0): (0,0) already off; (1,2) illuminates row 1, so (1,0) is illuminated. Output 1. Result: [1,1] ``` ## Follow-ups - How do you efficiently track which rows/columns/diagonals are lit? (counter maps per row, col, diag) - What is the time complexity per query with your approach? - Extend to lamps with a limited range (illuminates only within `r` cells along each direction).

## Problem You are given a street as an array where each element represents a house's property value. Find the length of the longest contiguous subarray of houses where: 1. The difference between the maximum and minimum value in the subarray is at most `k`. 2. The subarray contains at least one house with value >= `threshold`. ```python def longest_valid_block(values: list[int], k: int, threshold: int) -> int: ... ``` **Example:** ``` values = [4, 7, 2, 8, 5, 3], k = 5, threshold = 7 Output: 4 Explanation: Subarray [4,7,2,8] has max=8, min=2, diff=6 > 5. Skip. [7,2,8,5]: max=8,min=2,diff=6. Skip. [4,7,2,8] fails. Try [7,2,8]: diff=6. Hmm. [2,8,5,3]: diff=6. [8,5,3]: diff=5 <= 5, contains 8>=7. Length=3. [4,7,2]: diff=5, contains 7>=7. Length=3. Work through to find true max. ``` ## Follow-ups - How do you maintain running max and min efficiently as the window slides? (monotonic deques) - What is the time complexity of your sliding window approach? - Remove condition 2: how does the problem simplify, and does your approach still work?

## Problem Given a list of transaction amounts in chronological order, find the longest contiguous subarray where the standard deviation of amounts is at most `sigma_max`. This represents the longest "stable" trading period. ```python def longest_stable_period(amounts: list[float], sigma_max: float) -> int: ... ``` **Example:** ``` amounts = [10.0, 11.0, 10.5, 10.8, 50.0, 10.0, 9.5] sigma_max = 1.0 Output: 4 # subarray [10.0,11.0,10.5,10.8] has std ~ 0.46 <= 1.0 ``` **Note:** Use population standard deviation (divide by n, not n-1). ## Approach Brute force O(n^2): for each subarray recompute mean and std. Maintain running sum and sum of squares for O(1) incremental updates: `std = sqrt(sum_sq/n - (sum/n)^2)`. ## Follow-ups - Is a two-pointer / sliding window approach valid here? (std is not monotone as the window grows -- explain why shrinking the window does not always help) - How would you find all maximal stable periods, not just the longest? - Extend to use rolling mean as the reference instead of subarray mean.

## Problem Two numbers form a "magical pair" if their bitwise XOR equals their absolute difference. Given an array, count the number of such pairs `(i, j)` with `i < j`. ```python def count_magical_pairs(nums: list[int]) -> int: ... ``` **Example:** ``` Input: [0, 1, 2, 4] Output: 3 Explanation: (0,1): XOR=1, |0-1|=1. Match! (0,2): XOR=2, |0-2|=2. Match! (0,4): XOR=4, |0-4|=4. Match! (1,2): XOR=3, |1-2|=1. No. (1,4): XOR=5, |1-4|=3. No. (2,4): XOR=6, |2-4|=2. No. ``` **Mathematical insight:** For non-negative integers, `a XOR b == |a - b|` if and only if one number is a prefix of the other in binary (i.e., the larger has all bits of the smaller, plus possibly more -- which means the numbers share no overlapping set bits, i.e., `(a & b) == 0`). ## Follow-ups - Use the insight above to solve in O(n log n) using a trie or bit-grouping. - Does the property hold for negative integers? Why or why not? - Extend to triplets where all three pairwise XORs equal their respective absolute differences.

## Problem Find the longest arithmetic progression subsequence in an array. ## Tags dynamic_programming, arrays

## Problem Simulate memory allocation and deallocation operations, tracking free and occupied blocks efficiently. ## Tags greedy, arrays, other

## Problem Format text into newspaper-style columns of fixed width, distributing words and handling line breaks. ## Tags strings, arrays

## Problem Given an `N x M` matrix of non-negative integers, partition it into exactly `k` non-overlapping horizontal strips (contiguous row groups). The cost of a strip is the sum of all elements in it. Minimize the maximum strip cost. ```python def min_max_strip_cost(matrix: list[list[int]], k: int) -> int: ... ``` **Example:** ``` matrix = [[1,2],[3,4],[5,6]], k = 2 Strip options: [row0] + [row1,row2]: max(3, 18) = 18 [row0,row1] + [row2]: max(10, 11) = 11 Output: 11 ``` ## Approach Binary search on the answer: for a given max cost `mid`, greedily check if the matrix can be partitioned into at most `k` strips where each strip sum <= `mid`. Precompute row sums. ## Follow-ups - What is the time complexity of the binary search + greedy check approach? - Extend to vertical strips (column groups) -- does the greedy check still work in O(M) per candidate cost? - How does the problem change if strips must have equal numbers of rows (i.e., `N` must be divisible by `k`)?