Bird
Raised Fist0

Implement Linear Regression - Gradient Descent from Scratch

CODINGbeginnerInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Linear Regression - Gradient Descent from Scratch
Master linear regression by implementing gradient descent from scratch.
codingbeginnerFreq: very_highClassical ML Coding
Prerequisites:Linear Regression - From Least Squares to Gradient Descent
📝
Problem Statement

Implement linear regression using gradient descent from scratch.

I/O Specification
Input:  A 2D NumPy array X of shape (n_samples, n_features) and a 1D NumPy array y of shape (n_samples,).
Output: A 1D NumPy array of weights of shape (n_features,).
Example
{
  "input": {
    "X": [
      [
        1,
        2
      ],
      [
        2,
        3
      ],
      [
        3,
        4
      ]
    ],
    "y": [
      5,
      7,
      9
    ]
  },
  "expected_output": [
    1,
    1
  ]
}
🎯
Interview Angles
  • Understanding of gradient descent and its application in linear regression.
  • Ability to implement vectorized operations using NumPy.
  • Handling edge cases such as empty datasets or single feature inputs.
  • Optimization of iterative algorithms using vectorization.
🔵
Naive Approach

Use a simple iterative approach to update weights by computing the gradient of the loss function at each step.

Time: O(n_samples * n_features * epochs) - each weight update is O(n_features), repeated for n_samples and epochs. Space: O(n_features) - storing the weights.
Why Insufficient
O(n_samples * n_features * epochs) because it updates weights for each sample individually - inefficient for large datasets.
🐍
Naive Code
Python
import numpy as np

def naive_linear_regression(X, y, learning_rate=0.01, epochs=1000):
    n_samples, n_features = X.shape
    weights = np.zeros(n_features)
    for epoch in range(epochs):
        for i in range(n_samples):
            prediction = np.dot(X[i], weights)
            error = prediction - y[i]
            for j in range(n_features):
                weights[j] -= learning_rate * error * X[i, j]
    return weights

# Driver example
X = np.array([[1, 2], [2, 3], [3, 4]])
y = np.array([5, 7, 9])
weights = naive_linear_regression(X, y)
print(weights)
💡
Key Insight
Use vectorized operations to update weights for all samples simultaneously, reducing the number of iterations.
🐍
Optimized Code
Python
import numpy as np

def optimized_linear_regression(X, y, learning_rate=0.01, epochs=1000):
    n_samples, n_features = X.shape
    weights = np.zeros(n_features)
    for epoch in range(epochs):
        predictions = np.dot(X, weights)
        errors = predictions - y
        gradient = np.dot(X.T, errors) / n_samples
        weights -= learning_rate * gradient
    return weights

# Driver example
X = np.array([[1, 2], [2, 3], [3, 4]])
y = np.array([5, 7, 9])
weights = optimized_linear_regression(X, y)
print(weights)
🔍
Line-by-Line
n_samples, n_features = X.shape
Extracts the number of samples and features to initialize weights correctly.
weights = np.zeros(n_features)
Initializes weights to zero for all features.
predictions = np.dot(X, weights)
Computes predictions for all samples in one vectorized operation.
errors = predictions - y
Calculates the difference between predictions and actual values.
gradient = np.dot(X.T, errors) / n_samples
Computes the gradient of the loss function with respect to weights.
weights -= learning_rate * gradient
Updates weights using the computed gradient and learning rate.
⚡
Complexity
Time: O(n_samples * n_features * epochs) - each epoch involves a matrix multiplication and gradient computation. Space: O(n_features) - storing the weights.
Output
[1. 1.]
🔲
Edge Cases
Empty dataset
Returns zero weights as there are no samples to update from.
n_samples, n_features = X.shape
Single feature
Correctly computes the weight for the single feature.
weights = np.zeros(n_features)
⚠️
Common Mistakes
Not vectorizing the gradient computation.
Symptom: Code runs significantly slower on large datasets.
Incorrectly updating weights outside the loop.
Symptom: Weights do not change after initialization.
Forgetting to divide the gradient by the number of samples.
Symptom: Weights diverge instead of converging.
Using a learning rate that is too high.
Symptom: Weights oscillate and do not converge.

Practice

(1/5)
1. What is the time complexity of the forward pass of batch normalization for a dataset with n samples and d features?
easy
A. O(n + d)
B. O(n^2)
C. O(d^2)
D. O(n * d)

Solution

  1. Step 1: Analyze the operations

    Batch normalization involves computing mean and variance, both O(n * d) operations.

  2. Step 2: Consider the normalization step

    Normalizing each feature is also O(n * d).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Batch norm: O(n * d) for mean/variance [OK]
Hint: Batch norm: O(n * d) for mean/variance [OK]
Common Mistakes:
2. What is the time complexity of performing a train-test split with stratification on a dataset with n samples?
easy
A. O(n)
B. O(n^2)
C. O(n log n)
D. O(log n)

Solution

  1. Step 1: Analyze the operation

    Train-test split with stratification involves iterating over the dataset once to ensure class distribution.

  2. Step 2: Determine complexity

    Since each element is processed once, the complexity is O(n).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stratified split processes each sample once. [OK]
Hint: Stratified split processes each sample once. [OK]
Common Mistakes:
3. You implemented a normalization function for image data, but the model's performance dropped. What is the most likely cause?
medium
A. Normalization was applied after data augmentation.
B. Normalization was applied only to the training set.
C. Normalization was applied using incorrect mean and std values.
D. Normalization was applied using the global mean and std.

Solution

  1. Step 1: Identify normalization issues

    Incorrect mean and std values can skew the data distribution.

  2. Step 2: Eliminate other options

    Normalization was applied after data augmentation. is valid; Normalization was applied only to the training set. would cause a mismatch; Normalization was applied using the global mean and std. is standard practice.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Check mean/std values for normalization. [OK]
Hint: Check mean/std values for normalization. [OK]
Common Mistakes:
4. 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:
5. How can you optimize the implementation of a learning rate scheduler to reduce computational overhead in a large-scale training setup?
hard
A. Use a scheduler that updates every batch instead of every epoch.
B. Increase the step size in StepLR.
C. Switch to a constant learning rate.
D. Use a custom scheduler with fewer updates.

Solution

  1. Step 1: Identify computational overhead sources

    Frequent updates can increase overhead, especially in large-scale setups.

  2. Step 2: Optimize scheduler updates

    Creating a custom scheduler that reduces the frequency of updates can minimize computational costs while maintaining performance.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Custom schedulers can reduce update frequency. [OK]
Hint: Custom schedulers can reduce update frequency. [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