Storing 1 million phone numbers – Tech Interview Dot 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.

💡Strategies for Solving This Problem

System Design Question

Got this at Google. It's not about writing code - it's about discussing data structures, storage, and trade-offs. This is testing your systems thinking.

What They're Really Asking

How would you store them?
How would you search them?
What about memory constraints?
Need to support prefix search? ("Find all numbers starting with 415")

Approach 1: Hash Table

If you just need fast lookup by exact number: O(1) search, O(n) space.

Pros: Super fast exact matches
Cons: Can't do prefix search, can't get sorted order

Approach 2: Trie (Prefix Tree)

If you need prefix search ("all numbers starting with 650"):

Pros: Efficient prefix search, O(k) where k is number length
Cons: More memory than hash table

This is what my interviewer wanted to hear about.

Approach 3: Database

In reality, you'd use a database with indexes. Discuss:

B-tree index for range queries
Partitioning by area code
Replication for availability

Phone Number Specifics

Fixed length (10 digits in US)
Can represent as integer (but watch out for leading zeros!)
Area code provides natural partitioning

My Interview Discussion

I talked about Trie for prefix search. Interviewer asked:

"What's the space complexity?" (O(n × k) where k=10)
"Can you compress it?" (Yes, path compression)
"What if numbers don't fit in memory?" (Disk-based B-tree)

Be ready to dive deep into whichever structure you choose.

✅Solution

Solution: Trie for Phone Numbers

class PhoneNumberTrie {
    constructor() {
        this.root = {};
    }

    // Insert phone number
    insert(number) {
        // Remove non-digit characters
        const digits = number.replace(/D/g, '');

        let node = this.root;
        for (let digit of digits) {
            if (!node[digit]) {
                node[digit] = {};
            }
            node = node[digit];
        }
        node.isEnd = true;
        node.fullNumber = digits;
    }

    // Search for exact number
    search(number) {
        const digits = number.replace(/D/g, '');

        let node = this.root;
        for (let digit of digits) {
            if (!node[digit]) return false;
            node = node[digit];
        }
        return node.isEnd === true;
    }

    // Find all numbers with given prefix
    findByPrefix(prefix) {
        const digits = prefix.replace(/D/g, '');
        const results = [];

        // Navigate to prefix node
        let node = this.root;
        for (let digit of digits) {
            if (!node[digit]) return results;
            node = node[digit];
        }

        // DFS to collect all numbers from this point
        this.collectNumbers(node, results);
        return results;
    }

    collectNumbers(node, results) {
        if (node.isEnd) {
            results.push(node.fullNumber);
        }

        for (let digit = 0; digit <= 9; digit++) {
            if (node[digit]) {
                this.collectNumbers(node[digit], results);
            }
        }
    }
}

// Test
const trie = new PhoneNumberTrie();

// Insert numbers
trie.insert("415-555-0100");
trie.insert("415-555-0101");
trie.insert("415-555-0102");
trie.insert("650-123-4567");
trie.insert("650-123-4568");

// Search exact
console.log(trie.search("415-555-0100"));  // true
console.log(trie.search("999-999-9999"));  // false

// Prefix search
console.log(trie.findByPrefix("415"));     // ['4155550100', '4155550101', '4155550102']
console.log(trie.findByPrefix("650"));     // ['6501234567', '6501234568']
console.log(trie.findByPrefix("415555"));  // All numbers with 415-555

Alternative: Hash Set (Simpler)

class PhoneNumberSet {
    constructor() {
        this.numbers = new Set();
    }

    insert(number) {
        this.numbers.add(number.replace(/D/g, ''));
    }

    search(number) {
        return this.numbers.has(number.replace(/D/g, ''));
    }

    // Prefix search less efficient: O(n)
    findByPrefix(prefix) {
        const digits = prefix.replace(/D/g, '');
        return Array.from(this.numbers)
            .filter(num => num.startsWith(digits));
    }
}

Space Complexity Analysis

Trie:

Each number: 10 digits
Each digit: pointer (8 bytes) + metadata
Shared prefixes save space
Worst case: O(n × 10) where n = number count
Best case (all share prefix): much less

For 1 million numbers with shared area codes: ~40-80 MB

Hash Set:

Each number: 10 digits as string (10 bytes) + hash overhead
Total: ~20-30 MB for 1 million numbers

Real-World Considerations

// Database approach (conceptual)
class PhoneNumberDB {
    constructor() {
        // Would connect to actual database
        this.db = {
            table: 'phone_numbers',
            indexes: [
                'area_code',     // First 3 digits
                'exchange',      // Next 3 digits
                'full_number'    // All 10 digits
            ]
        };
    }

    // SQL would be something like:
    // CREATE TABLE phone_numbers (
    //   id BIGINT PRIMARY KEY,
    //   area_code CHAR(3),
    //   exchange CHAR(3),
    //   number CHAR(4),
    //   full_number CHAR(10) UNIQUE,
    //   INDEX idx_area (area_code),
    //   INDEX idx_full (full_number)
    // );

    searchByAreaCode(areaCode) {
        // SELECT * FROM phone_numbers WHERE area_code = ?
        return []; // Would return matching rows
    }

    searchByPrefix(prefix) {
        // SELECT * FROM phone_numbers
        // WHERE full_number LIKE 'prefix%'
        return [];
    }
}

Scaling Considerations

For billions of numbers:

Sharding: Partition by area code
Caching: Hot numbers in Redis
Compression: Store as integers (4 bytes vs 10)
Replication: Multiple read replicas

Interview tip: Start simple (hash table), then discuss why you might need more (prefix search → trie). Show you can think at multiple scales.