Find Travelers with Zero or One Temporal Anomalies - 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 find travelers who have experienced exactly one anomaly and those with no anomalies.
  • What input is provided?
    • An integer array anomalies where each element is [traveleri, anomalyi].

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Count the number of anomalies for each traveler and classify them based on the count.

1) Initialize a dictionary `anomaly_count` to store the count of anomalies for each traveler.
2) Iterate through `anomalies` to populate the dictionary.
3) Initialize two lists, `no_anomalies` and `one_anomaly`.
4) Iterate over `anomaly_count`:
   - If the count is 1, add the traveler to `one_anomaly`.
   - If the count is 0, add the traveler to `no_anomalies`.
5) Sort the lists and return them as a list of lists.

⚠️ Common Mistakes

• Incorrectly classifying travelers by not properly checking the anomaly count.

I-mplement

def find_travelers(anomalies):
    # Dictionary to store the count of anomalies for each traveler
    anomaly_count = {}
    
    for traveler, anomaly in anomalies:
        if traveler in anomaly_count:
            anomaly_count[traveler] += 1
        else:
            anomaly_count[traveler] = 1
    
    # Lists to store travelers with zero and exactly one anomaly
    no_anomalies = []
    one_anomaly = []
    
    # Consider only travelers that have experienced at least one anomaly
    for traveler, count in anomaly_count.items():
        if count == 1:
            one_anomaly.append(traveler)
        elif count == 0:
            no_anomalies.append(traveler)
    
    # Sort the lists
    no_anomalies.sort()
    one_anomaly.sort()
    
    return [no_anomalies, one_anomaly]