2015百度校招笔试真题以及解析（二）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54426149

1、static关键字，static全局变量与普通全局变量的区别，static局部变量与普通变量的区别，static函数与普通函数的区别。

　全局变量(外部变量)的说明之前再冠以static 就构成了静态的全局变量。全局变量本身就是静态存储方式， 静态全局变量当然也是静态存储方式。 这两者在存储方式上并无不同。这两者的区别在于非静态全局变量的作用域是整个源程序，当一个源程序由多个源文件组成时，非静态的全局变量在各个源文件中都是有效的。 而静态全局变量则限制了其作用域， 即只在定义该变量的源文件内有效， 在同一源程序的其它源文件中不能使用它。由于静态全局变量的作用域局限于一个源文件内，只能为该源文件内的函数公用， 因此可以避免在其它源文件中引起错误。 １、从以上分析可以看出， 把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期。把全局变量改变为静态变量后是改变了它的作用域， 限制了它的使用范围。

２、static函数与普通函数作用域不同。static函数仅在本文件中使用。只在当前源文件中使用的函数应该说明为内部函数(static)，内部函数应该在当前源文件中说明和定义。对于可在当前源文件以外使用的函数，应该在一个头文件中说明，要使用这些函数的源文件要包含这个头文件

３、 static局部变量和普通局部变量有什么区别：static局部变量只被初始化一次，下一次依据上一次结果值； ４、static函数与普通函数有什么区别：static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝。

2、微博中的url往往很长，发送前要转化为tinyurl

1、url如何转为tinyurl编码 ？ 2、如果用户输入一个已经转换过的URL，如何快速定位到已经生成了的tinyurl？ 3、如果数据为10亿条，需要10个tinyurl服务器，怎么设计？

思路１：

１、url转换为tinyurl编码使用数据库的自增ID, 但是随着url数量的增加可能数字串很长, 所以我们对id进行进制压缩,转换为一个字符串, 这里我们不采用传统的十六进制,而是将所有字母和数字都用上, 其中字母只使用大写字母, 去除数字0和字母O这两个难以分辨, 这样我们可以使用的字符数为 26+10-2=34, 所以我们使用34进制进行压缩。比如我们tinyurl长度限制在5个字符,那么可以标示的url数量为34^1+34^2+34^3+34^4+34^5 这是一个非常惊人的数字。 ２、数据库中自增ID都是建立索引的, 一个请求的tinyurl我们可以很快的将其还原为唯一ID, 然后直接查询数据库即可以获得原始url, 当然我们在这个过程中可以使用redis, leveldb等kv数据库进一步家加快查询过程 ３、由于自增ID的特殊性质,我们使用取模轮训的方式完全能够保证这10亿条url能够均匀分布在10个服务器上, 在十台服务器之前加上负载均衡, 根据进制压缩的结果讲请求转发到相应的服务器,每个服务器中有独立cache, 后端公用数据库。

思路２：

1、使用Hash函数对字符串进行hash，得到一个int值，（32位下int值域是2,147,483,648）。然后采用a-z A-Z 0-9组成的编码，该编码可表示 26+26+10=62进制系统，625=916,132,832，就是说5位编码能容下9亿多条url。只要是hash就免不了会冲突，当hash值冲突时，采用开散列，记录下标，再采用上述编码进行编号。最终编码格式为： 5位hash值编码 + 不定长下标编码简单描述为 Encode(Hash(url)) + Encode(CollideIndex(Hash(url)))重点是挑个均匀点的Hash函数，否则会出现服务器负载不均。然后均匀分到10个服务器， Hash(url)/916,132,84 =服务器编号，最后一个服务器会比其他服务器少8个值，但总体还是均匀的。 2、Decode(tinyurl[:5])/ 916,132,84得到服务器编号，Decode( tinyurl[:5] )是hash值，Decode(tinyurl[5:])是开散列下标。 3、当Hash函数是均匀分布时，10亿条平均散到10台服务器，每台是1亿条，即100M。假设平均url长度为100，那就需要10GB内存。可以考虑按区间将区间内的url写入文件，保留部分热点url在内存中，切换规则可以考虑LRU。