How to Deduplicate 4 Billion QQ IDs with Only 1 GB Memory

Problem analysis

Each QQ number is a 32‑bit unsigned integer (4 bytes). Storing 4 billion IDs directly requires 4000000000 * 4 / 1024 / 1024 / 1024 ≈ 15 GB, which exceeds the 1 GB memory limit.

Solution: BitMap

A BitMap is a contiguous array of bits where each bit represents the presence (1) or absence (0) of a value. For example, IDs 1, 4, 6 can be recorded with a single byte (8 bits) instead of three 4‑byte integers, saving roughly 12× space.

To handle 4 billion IDs with a BitMap:

Allocate a BitMap of 4 billion bits: 4000000000 * 1 / 8 / 1024 / 1024 = 476 M (≈ 500 MB).

Iterate over the input IDs, map each ID to its bit index, and set that bit to 1.

After the scan, traverse the BitMap and output every index whose bit is 1; these indices constitute the deduplicated set.

Advantages

Extreme memory efficiency – roughly one‑eighth of the space required by direct storage.

O(1) time complexity for insertion, lookup, and deduplication.

Simple implementation; only a bit array is needed.

Disadvantages

Can represent only presence/absence; cannot store additional data such as counts.

Requires a known, fixed value range; values outside the range cannot be handled.

Conclusion

The BitMap technique solves the interview problem by deduplicating 4 billion QQ IDs using under 500 MB of memory, well within the 1 GB constraint. The same approach applies to large‑scale deduplication, fast set operations, and underlies Bloom filter implementations.