We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Faulty Sensor

Number: 1980

Difficulty: Easy

Paid? Yes

Companies: Meta

Problem Description

Two sensors record a sequence of data points. However, one of the sensors may be faulty: it "drops" exactly one data point from the correct sequence, shifting all later values one position to the left and replacing the final element with a random value (which is guaranteed not to be equal to the dropped value). Given two arrays, sensor1 and sensor2, determine which sensor is defective (i.e. its output can be produced by dropping one data point from the correct sensor’s output). If there is no defect or it is impossible to decide with certainty, return -1.

Key Insights

  • One sensor’s data is correct while the other, if faulty, will equal the correct array with exactly one element missing (and with its last element replaced by an arbitrary value that does not equal the dropped value).
  • For the faulty sensor, the first part of its output will match the correct sensor except that at the drop index, every subsequent element is “shifted left” compared to the correct readings.
  • We can simulate this by iterating over the arrays using two pointers, allowing exactly one “skip” in the correct (supposed) sensor’s array.
  • We must consider both possibilities – sensor1 could be faulty with sensor2 correct, or sensor2 could be faulty with sensor1 correct. If both cases yield a valid explanation, the answer is ambiguous and we return -1.

Space and Time Complexity

Time Complexity: O(n), where n is the number of data points (at most 100).
Space Complexity: O(1)

Solution

We solve the problem by writing a helper routine that checks if an array F (faulty candidate) can be derived from array P (presumed correct) by having exactly one dropped element. The faulty sensor must match P exactly for the first several points and then, at one index, “skip” one element from P so that subsequent elements align, with the last element of F being arbitrary. We perform a two–pointer scan, allowing exactly one skip. We then test both possibilities:

  1. Check if sensor1 can be explained as faulty when sensor2 is assumed correct.
  2. Check if sensor2 can be explained as faulty when sensor1 is assumed correct. If exactly one of these tests passes, return the corresponding sensor number; otherwise, return -1.

Key data structures and techniques:

  • Two pointers (one iterating over the presumed correct array and one for the candidate faulty sensor).
  • A boolean flag to allow exactly one discrepancy (i.e. one skip in the correct array).

Code Solutions

# Function to check if 'faulty' array can be derived from 'correct' array by dropping exactly one element.
def is_faulty(faulty, correct):
    n = len(correct)
    # If both arrays are identical then there is no drop.
    if faulty == correct:
        return False

    skipped = False  # To mark if a drop has already been simulated
    i = 0  # Pointer for correct array
    j = 0  # Pointer for faulty array

    # Iterate until we reach the last element in the faulty array.
    while j < n - 1 and i < n:
        if correct[i] == faulty[j]:
            # Elements match, move both pointers
            i += 1
            j += 1
        else:
            # Mismatch encountered: simulate drop if not already done.
            if not skipped:
                skipped = True  # We simulate dropping correct[i]
                i += 1  # Skip one element from the correct array
            else:
                # Already simulated a drop, so the pattern cannot hold.
                return False

    # Now we are at j == n-1, the last element in the faulty array.
    # If no skip has been used, then the only possibility is that the dropped data point is the last element, 
    # meaning faulty[0..n-2] == correct[0..n-2] and faulty[n-1] is arbitrary but must differ from correct[n-1].
    if not skipped:
        # Check that all elements except the last match and that the last element is indeed different.
        if i == n - 1 and faulty[n - 1] != correct[n - 1]:
            return True
        else:
            return False
    else:
        # Skip was used; our loop should have consumed the correct array exactly.
        return i == n

def faultySensor(sensor1, sensor2):
    # Check two possibilities:
    # 1. Assume sensor2 is correct, sensor1 may be faulty.
    sensor1_faulty = is_faulty(sensor1, sensor2)
    # 2. Assume sensor1 is correct, sensor2 may be faulty.
    sensor2_faulty = is_faulty(sensor2, sensor1)
    
    # If exactly one sensor is identified as faulty, return its number.
    if sensor1_faulty and not sensor2_faulty:
        return 1
    if sensor2_faulty and not sensor1_faulty:
        return 2
    # Ambiguous or no fault at all.
    return -1

# Example test cases
print(faultySensor([2,3,4,5], [2,1,3,4]))   # Output: 1
print(faultySensor([2,2,2,2,2], [2,2,2,2,5])) # Output: -1
print(faultySensor([2,3,2,2,3,2], [2,3,2,3,2,7])) # Output: 2
← Back to All Questions