Bird
Raised Fist0

Implement 2D Convolution Filter from Scratch

CODINGadvancedInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
Naive 2D Convolution vs Optimized 2D Convolution with Stride and Padding

When implementing a 2D convolution filter from scratch, would you choose a naive approach or an optimized one with stride and padding? Justify your choice.

📊
Comparison
DimensionNaive 2D ConvolutionOptimized 2D Convolution with Stride and Padding
implementation simplicityhighmedium
computational efficiencylowhigh
flexibilitylowhigh
memory usagehighmedium
educational valuehighlow
✅
Verdict
Default to optimized convolution for large-scale applications where performance is critical; use naive convolution for educational purposes or small-scale problems where simplicity is key.
💡
Key Insight
Choose naive convolution for clarity and learning, optimized convolution for performance and flexibility.
⚠️
Interview Trap
❌ Wrong: Always use optimized convolution for better performance.
Ignoring the simplicity and educational value of the naive approach for small-scale problems.
✅ Consider the problem scale and educational context before choosing between naive and optimized convolution.
Naive 2D Convolution
"Simplicity and ease of understanding"
Weaknesses
  • Inefficient for large images due to O(n^4) complexity
  • Lacks flexibility with fixed stride and no padding
  • High memory usage for large kernel sizes
Ideal When
  • image_size < 100x100
  • kernel_size < 5x5
  • when educational clarity is prioritized over performance
Educational platforms often use naive convolution to teach the basics of convolution operations.
Optimized 2D Convolution with Stride and Padding
"Efficiency and flexibility for large-scale applications"
Weaknesses
  • Complex implementation compared to naive approach
  • Requires careful handling of edge cases with padding
  • May introduce numerical instability with large strides
Ideal When
  • image_size > 1000x1000
  • kernel_size > 5x5
  • when computational efficiency is critical
Deep learning frameworks like PyTorch and TensorFlow use optimized convolutions for training large neural networks.
🐍
Naive 2D Convolution - Example
▼ Show
Python
import numpy as np

def naive_convolution(image, kernel):
    output_height = image.shape[0] - kernel.shape[0] + 1
    output_width = image.shape[1] - kernel.shape[1] + 1
    output = np.zeros((output_height, output_width))
    for i in range(output_height):
        for j in range(output_width):
            output[i, j] = np.sum(image[i:i+kernel.shape[0], j:j+kernel.shape[1]] * kernel)
    return output
🐍
Optimized 2D Convolution with Stride and Padding - Example
▼ Show
Python
import numpy as np

def optimized_convolution(image, kernel, stride=1, padding=0):
    padded_image = np.pad(image, ((padding, padding), (padding, padding)), mode='constant')
    output_height = (padded_image.shape[0] - kernel.shape[0]) // stride + 1
    output_width = (padded_image.shape[1] - kernel.shape[1]) // stride + 1
    output = np.zeros((output_height, output_width))
    for i in range(output_height):
        for j in range(output_width):
            output[i, j] = np.sum(padded_image[i*stride:i*stride+kernel.shape[0], j*stride:j*stride+kernel.shape[1]] * kernel)
    return output
✅
Use Naive 2D Convolution When
  • •image_size < 100x100
  • •kernel_size < 5x5
  • •when teaching or learning the basics of convolution
✅
Use Optimized 2D Convolution with Stride and Padding When
  • •image_size > 1000x1000
  • •kernel_size > 5x5
  • •when performance and flexibility are required
↳
Nuances
  • For small images, the naive approach can be faster due to lower overhead.
  • Optimized convolutions may introduce edge artifacts if padding is not handled correctly.
  • In educational settings, the naive approach provides clearer insights into convolution mechanics.

Practice

(1/5)
1. What does the following Python code snippet output when implementing linear regression using gradient descent?
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([1, 2, 3])
weights = np.zeros(X.shape[1])
learning_rate = 0.01

for _ in range(1):
    predictions = X.dot(weights)
    errors = predictions - y
    gradient = X.T.dot(errors) / len(y)
    weights -= learning_rate * gradient

print(weights)
easy
A. [0.01, 0.02]
B. [0.1, 0.2]
C. [0.03, 0.04]
D. [0.05, 0.06]

Solution

  1. Step 1: Calculate initial predictions and errors

    Initial predictions are [0, 0, 0] since weights are zeros. Errors are [-1, -2, -3].

  2. Step 2: Compute gradient and update weights

    Gradient is [-3, -6]. Updated weights are [0.01, 0.02].

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Initial weights zero, single update step. [OK]
Hint: Initial weights zero, single update step. [OK]
Common Mistakes:
2. What is the time complexity of a single iteration of gradient descent for linear regression with n samples and d features?
easy
A. O(n)
B. O(d)
C. O(nd)
D. O(n^2)

Solution

  1. Step 1: Identify operations in a single iteration

    Each iteration involves matrix multiplication and gradient computation.

  2. Step 2: Calculate complexity

    Matrix multiplication and gradient computation both require O(nd) operations.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Matrix operations scale with samples and features. [OK]
Hint: Matrix operations scale with samples and features. [OK]
Common Mistakes:
3. What does the following Python code output when implementing logistic regression with a sigmoid activation function?
import numpy as np

def sigmoid(z):
    return 1 / (1 + np.exp(-z))

z = np.array([0, 2, -2])
output = sigmoid(z)
print(output)
easy
A. [0.5, 0.88, 0.12]
B. [0.5, 0.88, 0.11]
C. [0.5, 0.87, 0.12]
D. [0.5, 0.86, 0.12]

Solution

  1. Step 1: Calculate sigmoid for each element

    Sigmoid function is applied element-wise: sigmoid(0) = 0.5, sigmoid(2) ≈ 0.88, sigmoid(-2) ≈ 0.12.

  2. Step 2: Check precision of calculations

    Common mistake is rounding errors. Correct values are [0.5, 0.880797, 0.119203], rounded to [0.5, 0.88, 0.12].

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Sigmoid(0)=0.5, Sigmoid(2)≈0.88, Sigmoid(-2)≈0.12 [OK]
Hint: Sigmoid(0)=0.5, Sigmoid(2)≈0.88, Sigmoid(-2)≈0.12 [OK]
Common Mistakes:
4. In which scenario is gradient checking most useful?
medium
A. When implementing a new custom layer in a neural network.
B. When training a model with a large dataset.
C. When optimizing hyperparameters.
D. When deploying a model to production.

Solution

  1. Step 1: Identify scenarios where gradient checking is applicable

    Gradient checking is crucial when implementing new components to ensure correctness.

  2. Step 2: Eliminate unrelated scenarios

    Options A, C, and D are not directly related to verifying gradient correctness.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Use gradient check for new components. [OK]
Hint: Use gradient check for new components. [OK]
Common Mistakes:
5. 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:
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