要求实现一个北美电话号码的分配系统，即10位的电话号码的注册、注销和查询。有如下的API:
void registerNumber(String number); // 注册一个电话号码
void unregisterNumber(String number); // 注销一个电话号码
boolean isNumberRegistered(String number); // 查询一个电话号码的注册状态
String getAvailableNumber(); // 返回任意一个可用号码"

--

可以用bitset, 前三个都是O(1), 返回任意一个可用号码是O(1000 ＋ 10^7), 相当于O(1)。

struct PhoneBook {
   int ct;
   bitset<10000000> book;
};

class PhoneSystem {
   vector<PhoneBook> Phonebooks(1000);
}

新加phone number, areaCode从1－999, 先在PhoneBooks数组找到对应的PhoneBook[areaCode], 
再把相应的号码设置为1，增加此PhoneBook的计数器ct ++。
删除和查询类似。这三个都是O(1)。

返回任意一个可用号码, 先随机找一个ct < 10000000即未满的PhoneBook, 
再在里边顺序查找空的号码，这是O(1000 +10000000)，相当于O(1)。

需要内存: 1000 * 10^7 bits = 10^10 bits =~ 1.25 * 10^9 bytes = 1.25GB

--


#include <iostream>
#include <vector>
#include <bitset>
#include <cassert>
#include <cmath>
#include <sstream>
using namespace std;


// Total memory needed: 1000 * 10^7 bits = 10^10 bits =~ 1.25 * 10^9 bytes = 1.25GB
// This should be 1000. areaCode is 1-999
#define PHONE_BOOK_NUM 10  
// This should be 1000,0000, or 10^7
#define PHONE_BOOK_SIZE 1000

struct PhoneBook {
    int ct;
    bitset<PHONE_BOOK_SIZE> book;

    PhoneBook() : ct(0) {}
};

class PhoneSystem {
    vector<PhoneBook> p;
    int PhoneLen;
public:
    PhoneSystem() {
        p.resize(PHONE_BOOK_NUM);
        PhoneLen = log10(PHONE_BOOK_SIZE);
    }

    void add(int areaCode, int number) {
        p[areaCode].book.set(number, 1);
        p[areaCode].ct ++;
    }

    void clear(int areaCode, int number) {
        p[areaCode].book.set(number, 0);
        p[areaCode].ct --;
    }

    bool find(int areaCode, int number) {
        return p[areaCode].book.test(number);
    }

    // This can use randomization.
    string getFreeNumber() {
        for (int i = 1; i < PHONE_BOOK_NUM; ++ i) {
            if (p[i].ct == PHONE_BOOK_SIZE) continue;
            for (int j = 1; j < PHONE_BOOK_SIZE; ++ j) {
                if (! p[i].book.test(j)) {
                    return format(i << PhoneLen, j);
                }
            }
        }
    }

    string to_string(int s) {
        stringstream ss;
        ss << s;
        return ss.str();
    }
    string format(int areaCode, int number) {
        string s = string(2 - (int) log10(areaCode), '0') + to_string(areaCode) +
                   "-" + string(6 - (int) log10(number), '0') + to_string(number);
        return s;
    }
};


void test1() {
    PhoneSystem so;

    int areaCode = 1, number = 722;

    cout << so.format(areaCode, number) << endl;
    cout << (so.find(areaCode, number) ? "found" : "not found") << endl;
    so.add(areaCode, number);
    cout << (so.find(areaCode, number) ? "found" : "not found") << endl;
    so.clear(areaCode, number);
    cout << (so.find(areaCode, number) ? "found" : "not found") << endl;

    cout << "An available number: " << so.getFreeNumber() << endl;
}

int main() {
    test1();
    return 0;
}


test1()运行输出:

001-0000722
not found
found
not found
An available number: 008-0000001

北美电话号码的分配系统用bitset, 分两段，如果3/7开慢，5/5开应该够快。测试了一下，笔记本电脑上循环一遍，10^7 要0.4秒，10^6 要0.058秒,  10^5 要0.021秒。就是分桶的思想。如果5/5开还嫌慢， 3/3/4开应该够快了。内存把所有10位电话号码存下只要1.25GB。如果是BST，放所有10位电话号码要10^10 * 4byte ＝ 40GB，考虑到int放不下，可能要long，以及BST左右pointer，就要10^10 * (8 + 4x2)byte ＝ 160GB。

1.25GB 内存并不多，几十美元就可以，个人电脑4G是几乎很低的配置了。北美电话号码的分配系统，不可能因为1.25GB的内存有什么顾虑。