Detect Temporal Anomaly - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To detect if there are two distinct time points such that the same event ID occurs within a given range k.
  • What input is provided?
    • An array time_points and an integer k.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to store the last seen index of each event ID, and check if the difference between the current index and the last seen index is within the allowed range.

1) Initialize a dictionary `last_seen` to store the last seen index of each event ID.
2) Iterate over `time_points`:
   - For each event, check if it has been seen before and if the difference in indices is within `k`.
   - If so, return `True`.
   - Update the last seen index of the event.
3) If no anomalies are found, return `False`.

⚠️ Common Mistakes

• Not updating the last seen index correctly after checking.

I-mplement

def detect_temporal_anomaly(time_points, k):
    # Dictionary to store the last seen index of each event ID
    last_seen = {}
    
    for i, event in enumerate(time_points):
        if event in last_seen:
            if i - last_seen[event] <= k:
                return True
        # Update the last seen index of the event
        last_seen[event] = i
    
    return False