Unique Signal Frequencies — Problem Statement & Solution Guide
Problem Description
You are provided with an array of integers representing a stream of signal frequencies captured by a sensor. The goal is to identify the distinct frequency values present in the stream. The order of the distinct values in the output must match the order of their first occurrence in the input array.
Implement a function that processes the input array and returns a new array containing only the unique frequencies. If a frequency appears multiple times, it should be included only once in the result, at the position corresponding to its first appearance.
For instance, if the input stream is [4, 7, 4, 9, 7], the distinct frequencies in order of first appearance are 4, 7, and 9. The function should return [4, 7, 9].
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Signal Frequencies"
WHY DOES IT MATTER?
Order‑preserving uniqueness is fundamental for data cleaning, log aggregation, and any scenario where duplicate events must be eliminated without losing temporal context. Mastering this pattern demonstrates a candidate's ability to balance correctness with performance constraints.
OPTIMIZATION CHALLENGE
The key insight is to replace the linear search for prior occurrences with a constant‑time hash lookup, turning an O(n²) brute‑force scan into a linear‑time pass that scales to millions of entries.
REAL-WORLD CONNECTION
Consider a distributed telemetry system where sensors emit frequency readings; before analytics, the pipeline must drop repeated readings while keeping the chronological order, mirroring the deduplication logic required here.
In interviews, use language‑provided ordered dictionaries (e.g., LinkedHashSet in Java, dict in Python 3.7+) to automatically handle both uniqueness and order, reducing boilerplate and minimizing bug surface.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem of extracting distinct elements while preserving their first‑appearance order is a classic example of order‑preserving deduplication. A naive solution scans each element and checks all previously seen values, leading to O(n²) time on large inputs because each membership test is linear. The optimal paradigm leverages a hash‑based set (or hash map) to achieve constant‑time membership checks, allowing a single pass through the array. By recording each element the first time it is encountered and appending it to the result list, we maintain the original ordering while guaranteeing O(n) time and O(n) auxiliary space, which scales gracefully for massive streams.
Interview Questions on This Problem
Q1How would you modify the algorithm to return the distinct frequencies in the order of their last occurrence instead of the first?
Traverse the array from right to left, using a hash set to record seen values; prepend each unseen element to the result or build the list and reverse it at the end, achieving O(n) time and O(n) space.
Q2If the input were a singly linked list instead of an array, how would you implement order‑preserving deduplication?
Iterate through the list while maintaining a hash set of seen values; for each node, if its value is already in the set, unlink it; otherwise, add the value to the set. This runs in O(n) time with O(n) extra space for the set.
Q3What strategies can you use when the data stream is too large to fit into memory, yet you need to emit distinct values in order?
Employ external memory techniques such as chunked processing combined with a Bloom filter or disk‑based hash table; alternatively, use a streaming algorithm that writes unique values to a file while maintaining a bounded in‑memory cache for recent elements.
Examples
Input
[12, 5, 12, 8, 5, 3]
Output
[12, 5, 8, 3]
Explanation: 1. Start with an empty result list and a set to track seen values. 2. Process 12: Not in set. Add to set and result. Result: [12]. 3. Process 5: Not in set. Add to set and result. Result: [12, 5]. 4. Process 12: Already in set. Skip. 5. Process 8: Not in set. Add to set and result. Result: [12, 5, 8]. 6. Process 5: Already in set. Skip. 7. Process 3: Not in set. Add to set and result. Result: [12, 5, 8, 3]. Final output: [12, 5, 8, 3].
Input
[100, 100, 100]
Output
[100]
Explanation: 1. Process 100: Not in set. Add to set and result. Result: [100]. 2. Process 100: Already in set. Skip. 3. Process 100: Already in set. Skip. Final output: [100].
Input
[7, 2, 9, 4, 1, 6, 3, 8, 5]
Output
[7, 2, 9, 4, 1, 6, 3, 8, 5]
Explanation: 1. All elements are distinct. 2. Each element is added to the result in the order it appears. Final output: [7, 2, 9, 4, 1, 6, 3, 8, 5].
Input
[42, 17, 42, 17, 42, 17]
Output
[42, 17]
Explanation: 1. Process 42: Not in set. Add to set and result. Result: [42]. 2. Process 17: Not in set. Add to set and result. Result: [42, 17]. 3. Process 42: Already in set. Skip. 4. Process 17: Already in set. Skip. 5. Process 42: Already in set. Skip. 6. Process 17: Already in set. Skip. Final output: [42, 17].
Constraints
- 1 <= frequencies.length <= 10^5
- 1 <= frequencies[i] <= 10^9
- The input array will not be empty.
- The output array must preserve the order of first occurrence.
Optimal Approach & Strategy
Maintain a hash set of seen values and build the result in a single pass, adding an element only when it is not already in the set.
Brute Force Approach
For each element, scan all previous elements to see if it has appeared before; if not, copy it to the output.
Verified Code Solutions
/**
* @param {number[]} frequencies
* @return {number[]}
*/
function uniqueSignalFrequencies(frequencies) {
const seen = new Set();
const result = [];
for (const freq of frequencies) {
if (!seen.has(freq)) {
seen.add(freq);
result.push(freq);
}
}
return result;
}
// Example usage
const input = [12, 5, 12, 8, 5, 3];
console.log(uniqueSignalFrequencies(input));#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
vector<int> uniqueSignalFrequencies(vector<int>& frequencies) {
vector<int> result;
unordered_set<int> seen;
for (int freq : frequencies) {
if (seen.find(freq) == seen.end()) {
seen.insert(freq);
result.push_back(freq);
}
}
return result;
}
int main() {
vector<int> input = {12, 5, 12, 8, 5, 3};
vector<int> result = uniqueSignalFrequencies(input);
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << (i < result.size() - 1 ? " " : "");
}
cout << endl;
return 0;
}import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Main {
public static List<Integer> uniqueSignalFrequencies(List<Integer> frequencies) {
Set<Integer> seen = new HashSet<>();
List<Integer> result = new ArrayList<>();
for (int freq : frequencies) {
if (seen.add(freq)) {
result.add(freq);
}
}
return result;
}
public static void main(String[] args) {
List<Integer> input = List.of(12, 5, 12, 8, 5, 3);
List<Integer> result = uniqueSignalFrequencies(input);
System.out.println(result);
}
}def unique_signal_frequencies(frequencies):
"""
:param frequencies: List[int]
:return: List[int]
"""
seen = set()
result = []
for freq in frequencies:
if freq not in seen:
seen.add(freq)
result.append(freq)
return result
# Example usage
if __name__ == "__main__":
input_list = [12, 5, 12, 8, 5, 3]
print(unique_signal_frequencies(input_list))/**
* @param {number[]} frequencies
* @return {number[]}
*/
function uniqueSignalFrequencies(frequencies) {
const seen = new Set();
const result = [];
for (const freq of frequencies) {
if (!seen.has(freq)) {
seen.add(freq);
result.push(freq);
}
}
return result;
}
// Example usage
const input = [12, 5, 12, 8, 5, 3];
console.log(uniqueSignalFrequencies(input));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.