Asteroid Signal Detection — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(N + M)

SpaceO(M)

Problem Description

In a deep-space telemetry system, raw data streams are encoded as continuous strings of alphanumeric characters representing signal bursts. A specific sequence of characters, referred to as a 'signature,' is used to identify critical communication windows from a designated asteroid. Your task is to analyze a given telemetry string and determine the total number of times the signature appears as a contiguous substring.

It is crucial to note that overlapping occurrences must be counted. For instance, if the signature is 'AA' and the telemetry string is 'AAA', the signature appears at index 0 and index 1, resulting in a count of 2. The detection process is case-sensitive, and the signature must match the telemetry string exactly, character by character, without any modifications or wildcards.

Given two strings, telemetry and signature, return an integer representing the count of all valid occurrences of signature within telemetry. If the signature is empty or longer than the telemetry string, the count is 0.

DSA Pattern Breakdown

"Asteroid Signal Detection"

medium

WHY DOES IT MATTER?

String matching is fundamental in data processing, search engines, bioinformatics, and network security. Understanding efficient algorithms like KMP or Rabin-Karp demonstrates proficiency in optimizing for time complexity, which is critical in high-throughput systems.

OPTIMIZATION CHALLENGE

The key insight is to avoid re-checking characters that have already been matched. KMP uses the LPS array to determine how far to shift the pattern when a mismatch occurs, reducing the number of comparisons from O(N*M) to O(N+M).

REAL-WORLD CONNECTION

In network intrusion detection systems (IDS), signatures of malicious traffic patterns are matched against live packet streams. Efficient string matching ensures that threats are detected in real-time without introducing significant latency into the network.

During interviews, start with the naive approach to establish a baseline, then discuss its limitations. Transition to KMP by explaining the concept of 'failure function' or 'prefix function'. Emphasize that the preprocessing step (building the LPS array) is O(M), and the search step is O(N), leading to an overall O(N+M) complexity.

COMPLEXITY AT A GLANCE

⏱ Time:O(N + M)

💾 Space:O(M)

Core Theory — Why This Approach?

The problem of finding the number of occurrences of a pattern (signature) within a text (telemetry string) is a classic string matching challenge. The naive approach involves sliding a window of the pattern's length across the text and comparing characters one by one. This results in a time complexity of O(N*M), where N is the length of the text and M is the length of the pattern. For large telemetry streams (N ~ 10^6) and moderately sized signatures (M ~ 10^3), this leads to 10^9 operations, which is computationally infeasible within typical time limits (1-2 seconds).

Interview Questions on This Problem

Q1At a fintech platform processing high-frequency trading logs, how would you optimize the detection of specific error signatures in a 1GB log file without loading it entirely into memory?

Use the KMP (Knuth-Morris-Pratt) algorithm or Rabin-Karp with rolling hash. Process the file in chunks, maintaining the state of the algorithm across chunk boundaries. KMP ensures O(N) time complexity by avoiding redundant comparisons when a mismatch occurs, leveraging the prefix function to skip ahead efficiently.

Q2In a distributed system at a high-growth startup, multiple nodes need to detect the same signature in different shards of a data stream. How do you ensure consistent counting without double-counting overlapping occurrences?

Define the boundary conditions for overlapping occurrences clearly. If the signature can overlap with itself (e.g., 'aa' in 'aaa'), use an algorithm that allows overlapping matches. If not, adjust the sliding window step to skip past the matched substring. Use a consistent hash-based approach if using Rabin-Karp to ensure identical hash calculations across nodes.

Q3Why is the KMP algorithm preferred over simple substring search in real-time telemetry systems where latency is critical?

KMP guarantees linear time complexity O(N+M) regardless of the input pattern, whereas naive search can degrade to O(N*M) in worst-case scenarios (e.g., text 'aaaa...a' and pattern 'aaab'). In real-time systems, predictable latency is crucial, and KMP provides this by precomputing the longest proper prefix which is also a suffix (LPS) array, allowing the algorithm to skip unnecessary comparisons.

Examples

Example 1

Input

telemetry = "ABABAB", signature = "ABA"

Output

Explanation: We scan the telemetry string for the signature "ABA". 1. At index 0, the substring is "ABA", which matches the signature. Count = 1. 2. At index 1, the substring is "BAB", which does not match. 3. At index 2, the substring is "ABA", which matches the signature. Count = 2. 4. At index 3, the substring is "BAB", which does not match. Total occurrences: 2.

Example 2

Input

telemetry = "AAAA", signature = "AA"

Output

Explanation: We scan the telemetry string for the signature "AA". 1. At index 0, the substring is "AA", which matches. Count = 1. 2. At index 1, the substring is "AA", which matches. Count = 2. 3. At index 2, the substring is "AA", which matches. Count = 3. 4. At index 3, there are not enough characters left to form the signature. Total occurrences: 3.

Example 3

Input

telemetry = "HELLO WORLD", signature = "LO"

Output

Explanation: We scan the telemetry string for the signature "LO". 1. Indices 0-1: "HE" (No match) 2. Indices 1-2: "EL" (No match) 3. Indices 2-3: "LL" (No match) 4. Indices 3-4: "LO" (Match). Count = 1. 5. Indices 4-5: "O " (No match) 6. Indices 5-6: " W" (No match) 7. Indices 6-7: "WO" (No match) 8. Indices 7-8: "OR" (No match) 9. Indices 8-9: "RL" (No match) 10. Indices 9-10: "LD" (No match) Total occurrences: 1.

Example 4

Input

telemetry = "ABC", signature = "ABCD"

Output

Explanation: The length of the signature (4) is greater than the length of the telemetry string (3). Therefore, the signature cannot appear as a substring. Total occurrences: 0.

Constraints

1 <= telemetry.length <= 10^5
1 <= signature.length <= 10^5
telemetry and signature consist of uppercase and lowercase English letters and digits.
The total length of all test cases in a single run will not exceed 10^6.

Optimal Approach & Strategy

Use the KMP algorithm to precompute the LPS array for the pattern. Then, scan the text while using the LPS array to handle mismatches efficiently, ensuring linear time complexity.

Brute Force Approach

Iterate through each position in the text and compare the substring of length M with the pattern. If they match, increment the count. This approach is simple but inefficient for large inputs.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N + M)

/**
 * @param {string} telemetry
 * @param {string} signature
 * @return {number}
 */
function countSignatures(telemetry, signature) {
    if (signature.length === 0 || telemetry.length < signature.length) {
        return 0;
    }
    
    let count = 0;
    const n = telemetry.length;
    const m = signature.length;
    
    for (let i = 0; i <= n - m; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (telemetry[i + j] !== signature[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            count++;
        }
    }
    
    return count;
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', line => {
    lines.push(line);
    if (lines.length === 2) {
        const [telemetry, signature] = lines;
        console.log(countSignatures(telemetry, signature));
        rl.close();
    }
});

#include <iostream>
#include <string>

using namespace std;

int countSignatures(const string& telemetry, const string& signature) {
    if (signature.empty() || telemetry.size() < signature.size()) {
        return 0;
    }
    
    int count = 0;
    int n = telemetry.size();
    int m = signature.size();
    
    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        for (int j = 0; j < m; ++j) {
            if (telemetry[i + j] != signature[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            ++count;
        }
    }
    
    return count;
}

int main() {
    string telemetry, signature;
    cin >> telemetry >> signature;
    cout << countSignatures(telemetry, signature) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int countSignatures(String telemetry, String signature) {
        if (signature.isEmpty() || telemetry.length() < signature.length()) {
            return 0;
        }
        
        int count = 0;
        int n = telemetry.length();
        int m = signature.length();
        
        for (int i = 0; i <= n - m; i++) {
            boolean match = true;
            for (int j = 0; j < m; j++) {
                if (telemetry.charAt(i + j) != signature.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                count++;
            }
        }
        
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String telemetry = scanner.next();
        String signature = scanner.next();
        System.out.println(countSignatures(telemetry, signature));
        scanner.close();
    }
}

def count_signatures(telemetry: str, signature: str) -> int:
    if not signature or len(telemetry) < len(signature):
        return 0
    
    count = 0
    n = len(telemetry)
    m = len(signature)
    
    for i in range(n - m + 1):
        if telemetry[i:i+m] == signature:
            count += 1
    
    return count

if __name__ == "__main__":
    telemetry = input().strip()
    signature = input().strip()
    print(count_signatures(telemetry, signature))

/**
 * @param {string} telemetry
 * @param {string} signature
 * @return {number}
 */
function countSignatures(telemetry, signature) {
    if (signature.length === 0 || telemetry.length < signature.length) {
        return 0;
    }
    
    let count = 0;
    const n = telemetry.length;
    const m = signature.length;
    
    for (let i = 0; i <= n - m; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (telemetry[i + j] !== signature[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            count++;
        }
    }
    
    return count;
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', line => {
    lines.push(line);
    if (lines.length === 2) {
        const [telemetry, signature] = lines;
        console.log(countSignatures(telemetry, signature));
        rl.close();
    }
});

Asked in Top Tech Interviews

Swiggy

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.

Asteroid Signal Detection Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Asteroid Signal Detection — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor