Design a shared data structure that allows multiple threads to insert numbers and check for two-sum pairs without race conditions.

Requirements:

1. Single Shared Store:

   • A globally accessible collection (e.g., ConcurrentHashMap, HashSet with locks) to store numbers.

2. Two Operations:

   • add(num): Insert a number into the store.

   • checkPair(num, target): Check if (target - num) exists in the store.

3. Thread Safety:

   • Handle concurrent add() and checkPair() calls safely.

Approach:

• Use fine-grained locking (e.g., synchronized blocks, ReentrantLock) or a ConcurrentHashMap.

• Ensure atomicity for compound operations (e.g., check-then-add).

Solution

shared data structure for concurrent two-sum operations using Java's ConcurrentHashMap for thread safety:

import java.util.concurrent.ConcurrentHashMap;

public class TwoSumStore {
    private final ConcurrentHashMap<Integer, Integer> numberCounts;

    public TwoSumStore() {
        this.numberCounts = new ConcurrentHashMap<>();
    }

    /**
     * Adds a number to the store in a thread-safe manner
     * @param num the number to add
     */
    public void add(int num) {
        numberCounts.compute(num, (key, value) -> value == null ? 1 : value + 1);
    }

    /**
     * Checks if there exists a number in the store that can pair with the given num to sum to target
     * @param num the number to check for a complement
     * @param target the desired sum
     * @return true if a complement exists, false otherwise
     */
    public boolean checkPair(int num, int target) {
        int complement = target - num;

        // Special case: num == complement, we need at least two occurrences
        if (num == complement) {
            Integer count = numberCounts.get(complement);
            return count != null && count >= 2;
        }

        return numberCounts.containsKey(complement);
    }
}

Alternative Implementation with ReadWriteLock

For cases where you need more control over locking, here's a version using ReadWriteLock:

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class TwoSumStoreWithLock {
    private final Set<Integer> numbers;
    private final ReadWriteLock lock;

    public TwoSumStoreWithLock() {
        this.numbers = new HashSet<>();
        this.lock = new ReentrantReadWriteLock();
    }

    public void add(int num) {
        lock.writeLock().lock();
        try {
            numbers.add(num);
        } finally {
            lock.writeLock().unlock();
        }
    }

    public boolean checkPair(int num, int target) {
        int complement = target - num;

        lock.readLock().lock();
        try {
            // Special case: num == complement, need at least two occurrences
            if (num == complement) {
                return numbers.contains(complement) && 
                       numbers.stream().filter(n -> n == complement).count() >= 2;
            }
            return numbers.contains(complement);
        } finally {
            lock.readLock().unlock();
        }
    }
}

Key Features

1. Thread Safety:

   • First version uses ConcurrentHashMap which handles concurrency internally

   • Second version uses ReadWriteLock for explicit control

2. Correctness:

   • Handles the special case where a number is its own complement (e.g., 5 + 5 = 10)

   • Operations are atomic and won't cause race conditions

3. Performance:

   • ConcurrentHashMap allows concurrent reads and limited concurrent writes

   • ReadWriteLock allows multiple concurrent readers but exclusive writer access

4. Scalability:

   • Both implementations minimize lock contention

   • ConcurrentHashMap version is generally more scalable for high contention scenarios

Follow-up: (coming in Next Blog)

• How to avoid duplicate pair notifications?

• What if producers overwhelm consumers?