Sets and Deduplication

A set answers one question efficiently: have we seen this value before? That question appears everywhere in production software: duplicate events, replayed webhooks, already-sent notifications, selected IDs, unique visitors, fraud signals, autocomplete candidates, and merge pipelines.

A Set Is About Membership, Not Rich Records

A hash map stores key to value. A set stores keys only. If the product needs to know whether an ID exists, a set is enough. If it needs a count, timestamp, status, or payload, use a map. This distinction keeps implementations smaller and answers clearer.

Scenario: Webhook Deduplication

A payment provider sends webhooks to your service. Network retries can deliver the same event more than once. If your handler blindly processes every webhook, a customer might receive duplicate emails, duplicate credits, or duplicate fulfillment actions. A set of processed event IDs prevents repeated side effects.

Same Pattern in Java, Python, and JavaScript

The following examples return unique events in first-seen order. The set tracks membership. The output list preserves order. This is a common combination: a set for lookup plus a sequence for final presentation.

import java.util.*;

record Event(String id, String payload) {}

class EventDedup {
    static List<Event> uniqueInArrivalOrder(List<Event> events) {
        Set<String> seen = new HashSet<>();
        List<Event> result = new ArrayList<>();

        for (Event event : events) {
            if (seen.add(event.id())) {
                result.add(event);
            }
        }
        return result;
    }
}

Set vs Map vs Array

Deduplication Design Questions

• What is the identity key: event ID, user ID, normalized email, document ID, or compound key?
• How long must the system remember the key: request lifetime, session, day, billing period, or forever?
• What happens on process restart: can duplicates be tolerated, or must the set be persisted?
• Does deduplication preserve the first item, latest item, highest-priority item, or merged item?
• Can the set grow without bound, and should it use TTL, windowing, batching, or durable storage?

Cost Model and Limits

Set add, contains, and remove are expected O(1) in common hash-set implementations. But every unique key consumes memory. For a small request-local dedup this is trivial. For a streaming pipeline, unbounded sets become memory incidents unless the key lifetime is bounded.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Given an integer array, return true if any value appears at least twice.
• Given two arrays, return the unique values that appear in both arrays.
• Given a stream/list of event IDs, process each unique event once while preserving first-seen order.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class ContainsDuplicate {
    static boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int value : nums) {
            if (!seen.add(value)) return true;
        }
        return false;
    }
}

import java.util.*;

class ArrayIntersection {
    static int[] intersection(int[] a, int[] b) {
        Set<Integer> values = new HashSet<>();
        for (int value : a) values.add(value);

        Set<Integer> result = new HashSet<>();
        for (int value : b) {
            if (values.contains(value)) result.add(value);
        }

        int[] output = new int[result.size()];
        int i = 0;
        for (int value : result) output[i++] = value;
        return output;
    }
}

import java.util.*;

record Event(String id, String payload) {}

class UniqueEvents {
    static List<Event> unique(List<Event> events) {
        Set<String> seen = new HashSet<>();
        List<Event> result = new ArrayList<>();
        for (Event event : events) {
            if (seen.add(event.id())) result.add(event);
        }
        return result;
    }
}

Solved modelWorked Interview Answer

Return unique events in first-seen order. Use a set for membership and a list for output order. The set answers whether an event ID has appeared; the output list preserves the first accepted event.

import java.util.*;

record Event(String id, String payload) {}

class UniqueEvents {
    static List<Event> unique(List<Event> events) {
        Set<String> seen = new HashSet<>();
        List<Event> result = new ArrayList<>();
        for (Event event : events) {
            if (seen.add(event.id())) result.add(event);
        }
        return result;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using a set when the product actually needs counts or metadata.
• Forgetting that set deduplication may not preserve sorted order.
• Keeping an unbounded set forever in a long-running stream.
• Choosing an identity key that is too broad or too narrow.
• Ignoring restart and distributed-processing behavior for serious side effects.

Execution guardrailQuick-Start Checklist

• Define the membership key.
• Decide whether order matters.
• Decide whether counts or metadata matter.
• Bound the lifetime of stored keys.
• State expected runtime, memory cost, and failure mode.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice contains-duplicate, intersection, and first-duplicate problems.
• Review idempotency and replay protection in event-driven systems.
• Study Bloom filters later for approximate membership under memory pressure.