Datadog Software Engineer Phone Screen Questions

Two classic problems The following content requires a score higher than 188. You can already view it. 1. Given a `bucket_size` and a `bucket_width`, and a set of input numbers, return the number of nu

## Problem "Mado" means window in Japanese. Given an `m x n` integer matrix and a window size `k`, compute the sum of every valid `k x k` submatrix. Return all sums in a result matrix of size `(m-k+1) x (n-k+1)`. Optimize beyond the naive O(m * n * k^2) approach. ```python def mado_sum(matrix: list[list[int]], k: int) -> list[list[int]]: ... ``` ``` Input: matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] k = 2 Output: [ [12, 16], # top-left 2x2: 1+2+4+5=12; top-right: 2+3+5+6=16 [24, 28] # bot-left: 4+5+7+8=24; bot-right: 5+6+8+9=28 ] ``` ## Follow-ups 1. Describe the 2D prefix sum technique. What is its time and space complexity? 2. How does your approach handle matrices where `k > min(m, n)`? 3. What if instead of sum you need the maximum value in each window? How does your approach change? 4. Extend to a 3D tensor with window size `k x k x k`. How does the prefix sum generalize?

## Problem Simulate a change (otsuri) dispenser that returns optimal coin combinations for a given amount. ## Tags greedy, dynamic_programming

## Problem Calculate the total size of files in a directory tree, recursively summing nested folder sizes. ## Tags recursion, binary_tree, hash_table

## Problem Determine if a string follows the same pattern as a given word pattern using a bijective character-to-word mapping. ## Likely LeetCode equivalent LC 290 - word-pattern ## Tags hash_table, strings