Two Out of Three

Two Out of Three

What is this problem about?

The "Two Out of Three coding problem" asks you to identify all unique integers that appear in at least two out of three given arrays. You are provided with three separate lists, and the goal is to find their "partial intersection." This is a set-based logic problem often used in data synchronization and duplicate detection.

Why is this asked in interviews?

This is a popular "EASY" problem because it tests a developer's familiarity with "Set" data structures and "Hash Tables." Companies like Amazon and Booking.com use it to see if you can implement a clean, efficient solution that avoids the complexity of multiple nested loops. It also allows for an interesting discussion on "Bit Manipulation" as a way to track presence across multiple sources.

Algorithmic pattern used

The "Array, Hash Table, Bit Manipulation interview pattern" is the standard approach.

1. Set Approach: Convert each array into a Set to handle duplicates within the same array. Then, iterate through all unique numbers found across all sets and check how many sets contains each number.
2. Frequency Map: Use a single map to store a bitmask for each number. For example, if a number is in array 1, set the 1st bit; if in array 2, set the 2nd bit. At the end, return numbers whose masks have at least two bits set.

Example explanation

• List 1: [1, 2, 2]
• List 2: [4, 3, 2]
• List 3: [5, 1]

1. Number 1: In List 1 and List 3. (Count = 2) -> Keep.
2. Number 2: In List 1 and List 2. (Count = 2) -> Keep.
3. Number 3: In List 2 only. (Count = 1) -> Skip.
4. Number 4: In List 2 only. (Count = 1) -> Skip.
5. Number 5: In List 3 only. (Count = 1) -> Skip. Result: [1, 2].

Common mistakes candidates make

A frequent error is not handling duplicates within an array. If the number '2' appears ten times in the first array but nowhere else, it still only counts as appearing in one array. Another mistake is using an $O(N^2)$ approach to check every element of one array against the others, which is much slower than using a Hash Set.

Interview preparation tip

When solving the "Two Out of Three interview question," try to implement the bitmasking approach. It's a very elegant way to solve the problem with a single pass through each array, and it shows the interviewer that you understand low-level optimizations and bitwise logic.