# Storing 1 million phone numbers

Source: https://www.techinterview.org/post/1731330243/storing-1-million-phone-numbers/
Updated: 2026-07-05 · techinterview.org

What is the most efficient way, memory-wise, to store 1 million phone numbers?  Apparently this is an interview question at Google, although this seems like its a bit too easy.

## 2026 Update: Storing Phone Numbers at Scale — Compression and Trie

Storing 1 million 10-digit US phone numbers efficiently tests knowledge of data compression and data structure selection.


```
import array
import bisect

def phone_to_int(phone: str) -> int:
    """Convert formatted phone string to integer."""
    digits = ''.join(c for c in phone if c.isdigit())
    return int(digits)

def int_to_phone(n: int) -> str:
    s = f"{n:010d}"
    return f"({s[:3]}) {s[3:6]}-{s[6:]}"

# Memory comparison
def memory_analysis():
    n = 1_000_000
    string_bytes = n * 12        # "8005551234" ~12 bytes per string
    int64_bytes = n * 8          # 8 bytes per uint64
    packed_bytes = n * 5         # 5 bytes per 34-bit number (ceil(34/8)=5)

    print(f"String storage:   {string_bytes/1e6:.0f} MB")   # 12 MB
    print(f"int64 storage:    {int64_bytes/1e6:.0f} MB")    #  8 MB
    print(f"Packed storage:   {packed_bytes/1e6:.0f} MB")   #  5 MB

memory_analysis()

# Approach 1: Sorted array + binary search
class PhoneBook:
    def __init__(self):
        self.numbers = array.array('Q')  # unsigned long long, 8 bytes each

    def add(self, phone: str) -> None:
        n = phone_to_int(phone)
        pos = bisect.bisect_left(self.numbers, n)
        if pos == len(self.numbers) or self.numbers[pos] != n:
            self.numbers.insert(pos, n)

    def contains(self, phone: str) -> bool:
        n = phone_to_int(phone)
        pos = bisect.bisect_left(self.numbers, n)
        return pos < len(self.numbers) and self.numbers[pos] == n

# Approach 2: Trie (prefix tree) for autocomplete
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class PhoneTrie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, phone: str) -> None:
        digits = ''.join(c for c in phone if c.isdigit())
        node = self.root
        for d in digits:
            if d not in node.children:
                node.children[d] = TrieNode()
            node = node.children[d]
        node.is_end = True

    def search(self, phone: str) -> bool:
        digits = ''.join(c for c in phone if c.isdigit())
        node = self.root
        for d in digits:
            if d not in node.children:
                return False
            node = node.children[d]
        return node.is_end

    def starts_with(self, prefix: str) -> bool:
        digits = ''.join(c for c in prefix if c.isdigit())
        node = self.root
        for d in digits:
            if d not in node.children:
                return False
            node = node.children[d]
        return True  # Prefix exists

# Test
pb = PhoneBook()
pb.add("(800) 555-1234")
pb.add("(212) 867-5309")
print(pb.contains("(800) 555-1234"))  # True
print(pb.contains("(999) 999-9999"))  # False

trie = PhoneTrie()
trie.insert("8005551234")
print(trie.search("8005551234"))   # True
print(trie.starts_with("800"))     # True (area code autocomplete)
```

**2026 context:** This problem type appears in mobile contacts apps, telecom caller-ID lookups, and ad-tech phone number matching. Modern solutions use **delta encoding** (store sorted differences) + variable-length encoding to achieve ~2-3 bytes per phone number. Redis handles phone lookups via sorted sets (O(log n)); Cassandra uses bloom filters to avoid disk reads for non-existent numbers.