Bird
Raised Fist0

Implement 2D Convolution Filter from Scratch

CODINGadvancedInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
▶
Execution Trace
Step 1/4
Top-left corner of input matrix

Convolution at (0,0): (1*1 + 2*0 + 0*0 + 1*-1) = 1

🎯 Understanding how each element of the output is computed from the input and kernel.
for i in range(output_height):
    for j in range(output_width):
        if i < input_height - 1 and j < input_width - 1:
            output[i][j] = (input[i][j] * kernel[0][0] +
                            input[i][j+1] * kernel[0][1] +
                            input[i+1][j] * kernel[1][0] +
                            input[i+1][j+1] * kernel[1][1])
Middle of input matrix

Convolution at (2,2): (1*1 + 2*0 + 0*0 + 1*-1) = 1

🎯 Recognizing the sliding window mechanism of convolution.
for i in range(output_height):
    for j in range(output_width):
        if i < input_height - 1 and j < input_width - 1:
            output[i][j] = (input[i][j] * kernel[0][0] +
                            input[i][j+1] * kernel[0][1] +
                            input[i+1][j] * kernel[1][0] +
                            input[i+1][j+1] * kernel[1][1])
Bottom-right corner of input matrix

Convolution at (4,4): (1*1 + 0*0 + 2*0 + 1*-1) = 0

🎯 Handling edge cases where the kernel partially overlaps the input.
for i in range(output_height):
    for j in range(output_width):
        if i < input_height - 1 and j < input_width - 1:
            output[i][j] = (input[i][j] * kernel[0][0] +
                            input[i][j+1] * kernel[0][1] +
                            input[i+1][j] * kernel[1][0] +
                            input[i+1][j+1] * kernel[1][1])
Edge of input matrix

Convolution at (0,4): (1*1 + 0*0 + 0*0 + 1*-1) = 0

🎯 Understanding boundary conditions in convolution operations.
for i in range(output_height):
    for j in range(output_width):
        if i < input_height - 1 and j < input_width - 1:
            output[i][j] = (input[i][j] * kernel[0][0] +
                            input[i][j+1] * kernel[0][1] +
                            input[i+1][j] * kernel[1][0] +
                            input[i+1][j+1] * kernel[1][1])
📊
Diagram
Diagram
Input Matrix (I)        Kernel (K)        Output Matrix (O)
┌───────────────┐       ┌─────┐           ┌───────────────┐
│ 1  2  3  0  1 │       │ 1  0│           │  1  2  3  0  1│
│ 0  1  2  3  0 │       │ 0 -1│           │  0  1  2  3  0│
│ 1  0  1  2  3 │       └─────┘           │  1  0  1  2  3│
│ 2  1  0  1  2 │                         │  2  1  0  1  2│
│ 3  2  1  0  1 │                         │  3  2  1  0  1│
└───────────────┘                         └───────────────┘
Labels
  • Input Matrix (I): The original data to be convolved.
  • Kernel (K): The filter applied to the input matrix.
  • Output Matrix (O): The result of the convolution operation.
🔑
Key Moments
▲
Q: Why does the output matrix have the same dimensions as the input matrix?
A: The output matrix maintains the same dimensions due to the use of zero-padding, which allows the kernel to slide over the entire input matrix without reducing its size.
Q: How does the kernel affect the values in the output matrix?
A: The kernel acts as a filter that emphasizes certain features in the input matrix by performing element-wise multiplication and summation, affecting the output values based on its weights.
Q: What happens when the kernel overlaps the edge of the input matrix?
A: When the kernel overlaps the edge, zero-padding is used to ensure that the kernel can still perform a valid convolution operation, maintaining the output matrix size.
Trace Summary

This visual trace document explains the implementation of a 2D convolution filter from scratch. The diagram illustrates how a 5x5 input matrix is convolved with a 2x2 kernel to produce a 5x5 output matrix. The trace steps detail the convolution process at various points in the input matrix, highlighting the sliding window mechanism and handling of edge cases with zero-padding. Key moments focus on understanding the role of the kernel, the effect of zero-padding, and the preservation of matrix dimensions. This document provides a comprehensive understanding of manual convolution operations in deep learning.

Primary Focus

✓ Implementing a 2D convolution operation manually

Practice

(1/5)
1. 
import numpy as np

def dcg_at_k(r, k):
    r = np.asfarray(r)[:k]
    if r.size:
        return np.sum(r / np.log2(np.arange(2, r.size + 2)))
    return 0.0

relevance_scores = [3, 2, 3, 0, 1, 2]
k = 3
print(dcg_at_k(relevance_scores, k))
What does this code output?
easy
A. 5.2618595071429155
B. 4.2618595071429155
C. 3.2618595071429155
D. 6.2618595071429155

Solution

  1. Step 1: Understand DCG Calculation

    The DCG is calculated as the sum of relevance scores divided by log base 2 of their positions.

  2. Step 2: Calculate for k=3

    For k=3, the scores are [3, 2, 3]. The calculation is 3/1 + 2/log2(3) + 3/log2(4).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    DCG uses log2 positions. [OK]
Hint: DCG uses log2 positions. [OK]
Common Mistakes:
2. What is the time complexity of computing the softmax function for an input array of size n?
easy
A. O(n^2)
B. O(n log n)
C. O(1)
D. O(n)

Solution

  1. Step 1: Analyze operations

    Softmax involves computing exponentials and a sum, both linear in n.

  2. Step 2: Determine complexity

    Each operation is O(n), so overall complexity is O(n).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Softmax is linear in input size [OK]
Hint: Softmax is linear in input size [OK]
Common Mistakes:
3. In the context of implementing linear regression with gradient descent, how would you handle a dataset with missing values?
medium
A. Impute missing values using the mean of each feature.
B. Ignore missing values during training.
C. Replace missing values with zeros.
D. Remove any samples with missing values.

Solution

  1. Step 1: Consider impact of missing values

    Ignoring or zero-filling can bias results; removing samples reduces data.

  2. Step 2: Choose appropriate imputation

    Mean imputation is a common strategy that maintains dataset size and reduces bias.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Mean imputation balances bias and data retention. [OK]
Hint: Mean imputation balances bias and data retention. [OK]
Common Mistakes:
4. In a Random Forest implementation, how would you apply feature sampling to handle high-dimensional data effectively?
medium
A. Use all features for each tree to ensure accuracy
B. Use a fixed subset of features for all trees
C. Randomly select a small subset of features for each tree
D. Select features based on their correlation with the target

Solution

  1. Step 1: Understand Feature Sampling

    Feature sampling involves selecting a random subset of features for each tree to reduce dimensionality.

  2. Step 2: Evaluate Options

    Using all features (A) or a fixed subset (C) doesn't reduce dimensionality; correlation-based selection (D) isn't random.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Random subsets reduce dimensionality [OK]
Hint: Random subsets reduce dimensionality [OK]
Common Mistakes:
5. How can you optimize the implementation of linear regression using gradient descent for large datasets?
hard
A. Use a single feature at a time.
B. Use a smaller learning rate.
C. Increase the number of iterations.
D. Implement mini-batch gradient descent.

Solution

  1. Step 1: Identify scalability issues

    Full-batch gradient descent is computationally expensive for large datasets.

  2. Step 2: Choose an optimization strategy

    Mini-batch gradient descent reduces computation per iteration and can converge faster.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Mini-batch reduces computation, speeds convergence. [OK]
Hint: Mini-batch reduces computation, speeds convergence. [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