Implement valid 1-D convolution with bias
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Implement a "valid" 1-D convolution function in the cross-correlation sense. Given an input array of numbers, a kernel (filter) array of numbers, and a scalar bias, compute the output only at positions where the kernel **fully overlaps** the input (no padding, stride = 1), adding the bias to every output value.
Concretely, for an input of length `n` and a kernel of length `k` (with `k <= n`), produce an output of length `n - k + 1` where:
```
output[i] = ( sum_{j=0}^{k-1} input[i + j] * kernel[j] ) + bias
```
1. **Define the function signature** and clearly state your assumptions (e.g., stride = 1, no padding).
2. **Use cross-correlation semantics** — do **not** reverse the kernel before sliding it (this differs from textbook mathematical convolution, which flips the kernel).
3. **Apply the scalar bias** to each computed output element.
4. **Handle edge cases**: an empty kernel, a kernel longer than the input, and floating-point input/kernel/bias values.
5. **Analyze the time and space complexity** of your implementation.
Quick Answer: Implement a 'valid' 1-D convolution with a scalar bias: slide a kernel across an input with stride 1, output only where the kernel fully overlaps (length n - k + 1), using cross-correlation semantics. Covers the function signature, edge cases (empty kernel, kernel longer than input, floats), and time/space complexity analysis.
Compute valid stride-1 cross-correlation outputs with a scalar bias, without reversing the kernel.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3], [1,1], 0)
Expected Output: [3, 5]
Explanation: Simple moving sum.
Input: ([1.0,2.0,3.0], [0.5,-1.0], 1.0)
Expected Output: [-0.5, -1.0]
Explanation: Floating point values.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.