题目
某地电信局要对业务号码进行梳理，需要检测开通的市话号码是否存在某一个是另一个的前缀的情况，以简化电话交换机的逻辑。例如：某用户号码是“11001100”，但与"110"报警电话产生前缀配对。已知市话号码最长8位，最短3位，并且所有3位的电话号码都以1开头。由于市话号码众多，长度也未必一直，高效的算法可以用O(n)的时间复杂度完成检测（n为开通市话号码个数，数量是千万级的）。那么，该算法最坏情况下需要耗费大约________内存空间
A.5GB
B.500MB
C.50MB
D.5MB
解答
正确答案是 C
最长 8 位, 最短 3 共6种情况：
- 三位都是 1 开头 ,因此有 10^2=100 种
- 四位： 10^4=10，000 种
- 五位： 10^5=100，000 种
- 六位： 10^6=1，000，000 种
- 七位： 10^7=10，000，000 种
- 八位： 10^8=100，000，000种
相加一共为111，110，100种，因为电话号码唯一，所有号码最后1位不用判断，总数除以10 = 11,111,010种
一位号码 4bit（号码 从 0-9 ，所以至少用 4 个 bit 位才能表示 ），8位的号码占 32bit 即 4字节/byte（其实可以只存前7位,3.5byte）
最后：11,111,010 * 4 / 1024 / 1024 = 42.4 Mb
感人，这个类型我终于做对了
好多HR热衷于这样问……
我非科班18年毕业，现在转开发来得及吗，可能要先培训6个月
解析：千万级，也就是10,000,000。市话最长8位，也就是一个字节的空间，那么全部存下这些号码所耗费的空间为：1B*1000*1000*10 = 10MB（不必纠结1000还是1024，只要代表了千万级的数量就行了）。所以是两位数的级别。
最长的号码为8位，最短为3位。平均长度为：（3+8）/2 = 5位；然后号码的每位的取值都是1~9之间，而且一般都是用字符表示的，一个字符占据的空间是1字节（B）.所以一个号码占据的平均的空间大小是5B。号码规模的数量级是千万级别。所以总的空间大小是：
最长 8 位 最短 3 位， 3 位都是 1 开头 , 最短 3 位有 10^2=100 种，四位： 10^4=10000, 五位： 10^5=100000 ，六位： 10^6=1000000 ，七位： 10^7=10000000 ，八位： 10^8=10000000 ， 一位号码 4bit （号码从 0-9 ，所以至少用 4 个 bit 位才能表示） ，
其实是比较前 7 位，相加 11110100*4/8B / 1000 000 = 50MB 。
最长 8 位 最短 3 位， 3 位都是 1 开头 。
相加 111110100*4/8B / 1000 000 = 55.55MB 同一个数量级选50MB
只需要比7位，即把八位号码最后一位扔掉。每一位数字有4bit存储。这样有：
最长8位 最短3位， 3位都是1开头
最短3位有10^2=100种，
四位：10^4=10000,五位：10^5=100000，六位：10^6=1000000，七位：10^7=10000000，八位：10^8=10000000
一位号码4BITE，
其实是比较前7位，相加 11110101*4*8/4/1024(Kb)/1024(Mb)=42MB 取（50Mb）
时间复杂度O(n)条件下需要Trie存储已遍历过的号码。Trie是个10叉树，深度8，节点数为10+10^2+..+10^8, 节点数大约在10^8个，每个结点值为0~9, 可以用4bit二进制来表示，所以，字节数目为(10^8)*4/(1024*1024*8) 约等于50MB