Bird
Raised Fist0

Implement 2D Convolution Filter from Scratch

CODINGadvancedInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement 2D Convolution Filter from Scratch
Master the implementation of 2D convolution filters using NumPy.
codingadvancedFreq: very_highDeep Learning Coding
Prerequisites:Convolutional Neural Networks
📝
Problem Statement

Implement a 2D convolution filter from scratch using NumPy. The function should take an input image and a kernel, and return the convolved output.

I/O Specification
Example
{
  "input": {
    "image": [
      [
        1,
        2,
        3
      ],
      [
        4,
        5,
        6
      ],
      [
        7,
        8,
        9
      ]
    ],
    "kernel": [
      [
        1,
        0
      ],
      [
        0,
        -1
      ]
    ]
  },
  "expected_output": [
    [
      -4,
      -4
    ],
    [
      -4,
      -4
    ]
  ]
}
🎯
Interview Angles
  • Testing understanding of convolution operations in neural networks.
  • Evaluating ability to optimize naive implementations using NumPy.
  • Assessing knowledge of handling edge cases in image processing.
  • Checking familiarity with matrix operations and broadcasting in NumPy.
🔵
Naive Approach
The naive approach involves iterating over each possible position of the kernel on the image, computing the element-wise product and summing the results.
Time complexity: O(n * m * k * l) where n, m are dimensions of the image and k, l are dimensions of the kernel. Space complexity: O((n-k+1) * (m-l+1)) for the output.
Why Insufficient
O(n * m * k * l) because it involves nested loops over the image and kernel dimensions, making it inefficient for large images or kernels.
🐍
Naive Code
Python
import numpy as np

def naive_convolution_2d(image, kernel):
    image_height, image_width = image.shape
    kernel_height, kernel_width = kernel.shape
    output_height = image_height - kernel_height + 1
    output_width = image_width - kernel_width + 1
    convolved_image = np.zeros((output_height, output_width))
    for i in range(output_height):
        for j in range(output_width):
            for ki in range(kernel_height):
                for kj in range(kernel_width):
                    convolved_image[i, j] += image[i + ki, j + kj] * kernel[ki, kj]
    return convolved_image

# Driver example
image = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
kernel = np.array([[1, 0], [0, -1]])
print(naive_convolution_2d(image, kernel))
💡
Key Insight
Use NumPy's vectorized operations to perform element-wise multiplication and summation, reducing the need for explicit loops.
🐍
Optimized Code
Python
import numpy as np

def optimized_convolution_2d(image, kernel):
    image_height, image_width = image.shape
    kernel_height, kernel_width = kernel.shape
    output_height = image_height - kernel_height + 1
    output_width = image_width - kernel_width + 1
    convolved_image = np.zeros((output_height, output_width))
    for i in range(output_height):
        for j in range(output_width):
            image_patch = image[i:i+kernel_height, j:j+kernel_width]
            convolved_image[i, j] = np.sum(image_patch * kernel)
    return convolved_image

# Driver example
image = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
kernel = np.array([[1, 0], [0, -1]])
print(optimized_convolution_2d(image, kernel))
🔍
Line-by-Line
image_patch = image[i:i+kernel_height, j:j+kernel_width]
Extracts the current patch of the image that the kernel will be applied to.
convolved_image[i, j] = np.sum(image_patch * kernel)
Computes the element-wise multiplication and sums the result to get the convolved value.
output_height = image_height - kernel_height + 1
Calculates the height of the output image based on the input and kernel dimensions.
output_width = image_width - kernel_width + 1
Calculates the width of the output image based on the input and kernel dimensions.
convolved_image = np.zeros((output_height, output_width))
Initializes the output image with zeros to store the convolved results.
⚡
Complexity
Time complexity: O(n * m * k * l) - still involves iterating over the image and kernel, but vectorization reduces overhead. Space complexity: O((n-k+1) * (m-l+1)) for the output.
Output
[[-4. -4.]
 [-4. -4.]]
🔲
Edge Cases
Empty Image
Returns an empty array since there are no pixels to convolve.
output_height = image_height - kernel_height + 1
Kernel Larger Than Image
Returns an empty array because the kernel cannot fit inside the image.
output_height = image_height - kernel_height + 1
⚠️
Common Mistakes
Incorrectly calculating output dimensions.
Symptom: IndexError due to accessing out-of-bounds indices.
Not handling non-square kernels.
Symptom: Incorrect output shape or values.
Using loops instead of vectorized operations.
Symptom: Significantly slower execution time.
Ignoring edge cases like empty images.
Symptom: Runtime errors or incorrect outputs for edge cases.
Practice
(1/5)
1. You implemented early stopping in your training loop, but the model still overfits. What is the most likely reason?
medium
A. The validation set is too small.
B. The learning rate is too high.
C. The patience parameter is too low.
D. The model architecture is too simple.
Solution
  1. Step 1: Analyze early stopping behavior
    Early stopping relies on validation performance to halt training.
  2. Step 2: Identify the root cause of overfitting
    If the validation set is too small, it may not accurately reflect generalization, leading to overfitting despite early stopping.
  3. Final Answer:
    Option A ->  Option A
  4. Quick Check:
    Small validation set can mislead early stopping. [OK]
Hint: Small validation set can mislead early stopping. [OK]
Common Mistakes: 
2. In the implementation of Adam optimizer, the model is not converging. Which line of code is most likely causing the issue?
medium
A. parameter -= learning_rate * m_hat / (np.sqrt(v_hat) + epsilon)
B. v = beta2 * v + (1 - beta2) * (gradient ** 2)
C. m_hat = m / (1 - beta1 ** t)
D. m = beta1 * m + (1 - beta1) * gradient
Solution
  1. Step 1: Identify the potential issue
    The line parameter -= learning_rate * m_hat / (np.sqrt(v_hat) + epsilon) is crucial for parameter updates. If epsilon is not properly set, it can cause division by zero or very small updates.
  2. Step 2: Eliminate other options
    Options A, B, and C are standard parts of the Adam algorithm and unlikely to cause convergence issues unless there's a typo or logical error.
  3. Final Answer:
    Option A -> Option A
  4. Quick Check:
    Check epsilon in Adam's update step [OK]
Hint: Check epsilon in Adam's update step [OK]
Common Mistakes: 
3. How can you optimize the computation of cosine similarity for a large dataset of vectors?
hard
A. Use a recursive function to handle large datasets.
B. Use a loop to compute each pairwise similarity.
C. Precompute norms and use matrix multiplication.
D. Store vectors as lists to save memory.
Solution
  1. Step 1: Identify computational bottlenecks
    Looping over pairs is inefficient for large datasets.
  2. Step 2: Optimize using matrix operations
    Precomputing norms and using matrix multiplication reduces redundant calculations.
  3. Final Answer:
    Option C -> Option C
  4. Quick Check:
    Matrix ops reduce redundancy. [OK]
Hint: Matrix ops reduce redundancy. [OK]
Common Mistakes: 
4. How can you optimize the memory usage of a NumPy-based backpropagation implementation for a large neural network?
hard
A. Use in-place operations to reduce memory overhead.
B. Use Python lists instead of NumPy arrays.
C. Store all intermediate results for debugging.
D. Increase the batch size to reduce iterations.
Solution
  1. Step 1: Identify memory bottlenecks
    Intermediate results can consume significant memory.
  2. Step 2: Optimize memory usage
    In-place operations reduce memory overhead by modifying data directly.
  3. Final Answer:
    Option A ->  Option A
  4. Quick Check:
    In-place operations save memory [OK]
Hint: In-place operations save memory [OK]
Common Mistakes: 
5. How can you optimize the memory usage of a learned positional encoding implementation in PyTorch?
hard
A. Use a sparse matrix for the encoding.
B. Reduce the number of dimensions in the encoding.
C. Share the encoding matrix across multiple layers.
D. Use half-precision floating point for the encoding matrix.
Solution
  1. Step 1: Consider memory optimization techniques
    Using half-precision floating point reduces memory usage while maintaining sufficient precision for many applications.
  2. Step 2: Eliminate wrong options
    Reduce the number of dimensions in the encoding. changes the model architecture. Use a sparse matrix for the encoding. is not applicable as the matrix is dense. Share the encoding matrix across multiple layers. may affect model performance and is not a direct memory optimization.
  3. Final Answer:
    Option D -> Option D
  4. Quick Check:
    Half-precision reduces memory without major precision loss. [OK]
Hint: Half-precision reduces memory without major precision loss. [OK]
Common Mistakes: 
Recommended
Ready to prove it?
Pass the test and this pattern moves unknown  strong while earning +1 Grip toward your certificate.
10 questions~5 mineasy  hard