Faulty Sensor - Practice Coding Problems

Faulty Sensor - Problem

An experiment is being conducted in a lab. To ensure accuracy, there are two sensors collecting data simultaneously.

You are given two arrays sensor1 and sensor2, where sensor1[i] and sensor2[i] are the ith data points collected by the two sensors.

However, this type of sensor has a chance of being defective, which causes exactly one data point to be dropped. After the data is dropped, all the data points to the right of the dropped data are shifted one place to the left, and the last data point is replaced with some random value.

It is guaranteed that this random value will not be equal to the dropped value. For example, if the correct data is [1,2,3,4,5] and 3 is dropped, the sensor could return [1,2,4,5,7] (the last position can be any value, not just 7).

We know that there is a defect in at most one of the sensors. Return the sensor number (1 or 2) with the defect. If there is no defect in either sensor or if it is impossible to determine the defective sensor, return -1.

Input & Output

Example 1 — Sensor1 Missing Element

$ Input: sensor1 = [1,3,4,5], sensor2 = [1,2,3,4]

› Output: 1

💡 Note: Sensor1 is missing element 2. If we remove element 3 from position 1 in sensor1, we get [1,4,5], but this doesn't match sensor2's first 3 elements [1,2,3]. However, sensor1 appears to have dropped element 2, causing all subsequent elements to shift left and the last position to be filled with value 5.

Example 2 — No Defect

$ Input: sensor1 = [1,2,3,4], sensor2 = [1,2,3,4]

› Output: -1

💡 Note: Both sensors have identical readings, so there's no defect in either sensor.

Example 3 — Sensor2 Missing Element

$ Input: sensor1 = [1,2,3,4], sensor2 = [1,3,4,7]

› Output: 2

💡 Note: Sensor2 is missing element 2. The correct sequence should be [1,2,3,4], but sensor2 shows [1,3,4,7] where 2 was dropped and 7 was added at the end.

Constraints

2 ≤ sensor1.length, sensor2.length ≤ 1000
sensor1.length == sensor2.length
1 ≤ sensor1[i], sensor2[i] ≤ 10⁶
At most one sensor is defective

Visualization

Tap to expand

Understanding the Visualization

Input

Two sensor arrays with potential defect in one

Defect Pattern

Dropped element causes left shift and random end value

Detection

Compare and identify which sensor is faulty

Key Takeaway

🎯 Key Insight: A faulty sensor creates a cascade pattern - one missing element causes all subsequent elements to shift left

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to find the first position where sensors differ, then test if skipping that position in either sensor creates a valid match. The optimal approach uses two pointers for O(n) time complexity with early termination on first mismatch detection.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Drop Positions	O(n²)	O(1)	Test every possible drop position in both sensors to see which one could be faulty
Two Pointers - Compare Until Mismatch	O(n)	O(1)	Compare sensors element by element until first mismatch, then determine which sensor is faulty

Brute Force - Try All Drop Positions — Algorithm Steps

Step 1: For sensor1, try dropping each position i and check if remaining matches sensor2
Step 2: For sensor2, try dropping each position i and check if remaining matches sensor1
Step 3: Return the sensor number that has exactly one valid drop position

Visualization

Tap to expand

Step-by-Step Walkthrough

Test Sensor1

Try dropping each position from sensor1

Test Sensor2

Try dropping each position from sensor2

Compare

Find which sensor has exactly one valid drop

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canBeFaulty(int* faulty, int* correct, int n) {
    int validDrops = 0;
    
    for (int dropPos = 0; dropPos < n; dropPos++) {
        bool matches = true;
        int correctIdx = 0;
        
        for (int i = 0; i < n; i++) {
            if (i == dropPos) continue;
            if (correctIdx >= n - 1 || faulty[i] != correct[correctIdx]) {
                matches = false;
                break;
            }
            correctIdx++;
        }
        
        if (matches && correctIdx == n - 1) {
            validDrops++;
        }
    }
    
    return validDrops == 1;
}

int solution(int* sensor1, int* sensor2, int n) {
    bool sensor1Faulty = canBeFaulty(sensor1, sensor2, n);
    bool sensor2Faulty = canBeFaulty(sensor2, sensor1, n);
    
    if (sensor1Faulty && !sensor2Faulty) {
        return 1;
    } else if (sensor2Faulty && !sensor1Faulty) {
        return 2;
    } else {
        return -1;
    }
}

int main() {
    char line[1000];
    int sensor1[500], sensor2[500];
    int n = 0;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 500) {
        if (strlen(token) > 0 && token[0] != '\n') {
            sensor1[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int m = 0;
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL && m < 500) {
        if (strlen(token) > 0 && token[0] != '\n') {
            sensor2[m++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(sensor1, sensor2, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n positions, we compare up to n elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Drop Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler