People walking on a light footbridge push it sideways about twice per second. If the bridge's own sway frequency is close to that, the sway can build up. An engineer fixes an accelerometer to the deck and records N samples at fs samples per second. The reading includes a constant part (the sensor's tilt) and slow and fast waves; the engineer only cares about waves between fmin and fmax hertz.
Bin k of the DFT,
X[k] = sum over n = 0 .. N-1 of x[n] * exp(-2j * pi * k * n / N)
describes the wave at k * fs / N hertz, with amplitude 2 * |X[k]| / N. A long recording has many bins, but only the few whose frequency lies in the band are needed, and each costs one pass over the samples.
Write bridge_sway(x, fs, fmin, fmax) that looks at every bin k with 1 <= k < N / 2 and fmin <= k * fs / N <= fmax, and returns a tuple (frequency, amplitude) for the bin with the largest magnitude (the lowest k if two are equal). Return None if no bin lies in the band.
Examples
Input: x = [0, 1, 0, -1, 0, 1, 0, -1], fs = 8, fmin = 0.5, fmax = 3.5
Output: (2.0, 1.0)
Explanation: bins 1, 2 and 3 (1, 2 and 3 Hz) lie in the band; the signal is a sine
making two cycles in one second, so bin 2 is the strongest, with amplitude 1.
Input: x = [0, 1, 0, -1, 0, 1, 0, -1], fs = 8, fmin = 2.2, fmax = 2.8
Output: None
Explanation: the bins are 1 Hz apart, and none lies between 2.2 and 2.8 Hz.
Input: x = [10, 12, 10, 8], fs = 4, fmin = 0, fmax = 2
Output: (1.0, 2.0)
Explanation: bin 0 (the offset of 10) is never a sway, and bin 2 is not below N / 2.
Constraints
2 <= N <= 6000; at most 250 bins lie in the band, so computing the whole DFT would be too slow for the biggest tests- the band edges never fall exactly on the frequency of a bin with
1 <= k < N / 2 - answers are compared with a tolerance of
1e-6
Goals
- Find the strongest wave in a recording from the magnitudes of its DFT bins
- Compute only the bins inside a frequency band instead of the whole transform
- Leave out bin 0, the offset, which is not a vibration