2015百度校招笔试真题以及解析(二)

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

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

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

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



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

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

思路1:

1、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 这是一个非常惊人的数字。

2、数据库中自增ID都是建立索引的, 一个请求的tinyurl我们可以很快的将其还原为唯一ID, 然后直接查询数据库即可以获得原始url, 当然我们在这个过程中可以使用redis, leveldb等kv数据库进一步家加快查询过程

3、由于自增ID的特殊性质,我们使用取模轮训的方式完全能够保证这10亿条url能够均匀分布在10个服务器上, 在十台服务器之前加上负载均衡, 根据进制压缩的结果讲请求转发到相应的服务器,每个服务器中有独立cache, 后端公用数据库。

思路2:

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。

时间: 2024-08-03 14:28:01

2015百度校招笔试真题以及解析(二)的相关文章

2015百度校招笔试真题以及解析(一)

1.为分析用户行为,系统常需存储用户的一些 query ,但因 query 非常多,故系统不能全存,设系统每天只存 m 个 query ,现设计一个算法,对用户请求的 query 进行随机选择 m 个,请给一个方案,使得每个 query 被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量. 解析1:思路:如果用户查询的数量小于 m ,那么直接就存起来.如果用户查询的数量大于 m ,假设为 m+i ,那么在 1-–m+i 之间随机产生一个数,如果选择的是前面 m 条查询进行存取,

2013百度校招笔试真题以及解析(内存管理及其优缺点总结)

简述Windows内存管理的几种方式以及优缺点. Windows内存管理方式如下图所示: 1.单一连续分配 所谓单一,是指内存中只驻留一道作业.为便于地址转换,把作业连续的存放在内存中,而不是离散的存放.单一连续区的管理思想主要用在早期的单道批处理系统中,采用静态分配的方式,即作业或进程一进入内存,就要等到它结束后才释放内存. 优点: 方法简单,易于实现 缺点: 仅适合于单道程序 2.分区管理 分区管理是把内存划分成若干个大小不等的区域,除操作系统占用一个区域之外,其余由多道环境下的各并发进程共

2013百度校招笔试真题以及解析(二)

1.一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词.提供一个单词,在字典中找到它的兄弟.描述数据结构和查询过程. 思路1:使用hash_map和链表 (1)首先定义一个key,使得兄弟单词有相同的key,不是兄弟的单词有不同的key.例如,将单词按字母从小到大重新排序后作为其key,比如bad的key为abd,good的key为dgoo. (2)使用链表将所有兄弟单词串在一起,hash_map的key为单词的key,value为链表的起始地址. (3)开始时,先遍历字

2014Microsoft 校招笔试真题(找工作的虾米们赶紧做题晒答案喽)

2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

题目: 给定一个正整数n,求比n大的第一个"不重复数"."不重复数"的定义:如果一个数,任何相邻两个数位上的数字都不相同,则称为不重复数.例如1234是不重复数,而1101不是. 思路一:暴力 数值加一,判断是否是重复数,如果是,继续加一判断,直到找到一个不是重复数的. #include <iostream> #include <cstring> #include <vector> #include <algorithm&g

2013第四届蓝桥杯 C/C++本科A组 真题答案解析【交流帖】

今年的蓝桥杯又已经结束了,做的还是不怎么样,很多题目不难但就是算不出最终的结果,很是纠结,看来路还很长,另外昨天(2013-5-7)也受到了也受到了微软的thank you letter了,哎,都是苦逼的一天.不说了,直接看题吧,如果你对我的做法有异议或者有更好的解法,请给我留言,我会及时更新~~~~~ 1.高斯日记  大数学家高斯有个好习惯:无论如何都要记日记. 他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210 后来人们知道,那个整数就是日期,它表示那一天是高斯

京东2017校园招聘笔试真题(希尔排序)

对关键字{10,20,8,25,35,6,18,30,5,15,28}序列进行希尔排序,取增量d =5时,排序结果为( ) A. {6,18,8,5,15,10,20,30,25,35,28} B. {10,18,8,5,15,6,20,30,25,35,28} C. {10,20,8,5,15,6,18,30,25,35,28} D. {10,20,30,5,8,6,15,18,25,28,35} 希尔排序 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法

备战2016年软考必做真题!

网络规划设计师 2012年下半年网络规划设计师下午案例分析真题+答案解析:http://down.51cto.com/data/1405756 2013年网络规划设计师上午真题及答案解析:http://down.51cto.com/data/1861654 2014年下半年网络规划师下午1案例分析真题及答案:http://down.51cto.com/data/1906669 2015 年下半年网络规划师下午案例分析真题及答案:http://down.51cto.com/data/2117462

JAVA认证历年真题解析二(附答案)

问题描述 我在网上偶然看到一个网站,这个网站里面的资料非常全,除了一些免费的资料,还有网络视频,觉得非常不错,大家有兴趣或者需要,可以去看看[中华IT学习网]www.100itxx.com内容介绍>>本试卷共有45道题,每题后面都有详细解析.例:1.Whichofthefollowingrangeofshortiscorrect?A.-27--27-1B.0--216-1C.?215--215-1D.?231--231-1翻译下面哪些是short型的取值范围.答案 C解析 短整型的数据类型的长