首页 > 代码库 > 2015百度校招笔试杭州站

2015百度校招笔试杭州站

1:请描述数据结构中栈和队列的区别。并说出3个操作。

答:栈先进后出。队列先进先出。例如(pop() push() empty() back() front());

2:请描述一下C++中多态。举个例子:

我学java的。但我记得多态应该是重载和重写。

重载
Class A
{
    int foo(int a){...}
    int foo(int a,int b){...}
}

重写
Class A
{
    int foo(int a){ return a}
}
Class B:A
{
    int foo(int a){return -a}
}

3:请描述下TCP四次挥手。并说下Time_wait的作用。

四次挥手的图我画对了。但发的包名称乱说了。。。Time_wait我以为是等待时间。时间到了就默认关闭的样子。。。

网上答案:
1。防止上一次连接中的包,迷路后重新出现,影响新连接
  (经过2MSL,上一次连接中所有的重复包都会消失)
2。可靠的关闭TCP连接
  在主动关闭方发送的最后一个ack(fin) ,有可能丢失,这时被动方会重新发
  fin, 如果这时主动方处于CLOSED 状态 ,就会响应rst 而不是ack。所以
  主动方要处于TIME_WAIT 状态,而不能是CLOSED 。
TIME_WAIT 并不会占用很大资源的,除非受到攻击。
还有,如果一方send 或recv 超时,就会直接进入CLOSED 状态

二编程题

1:写个能将整篇文章单词翻转的程序。不允许使用任何函数。这个ACM题库里有不说了。

2:最长递增子序列:

这道题当场傻逼了。不过印象里是dp用LCS做的。后来一直傻逼。暴力做了。。。

其实是把源串排序用排序后的串和源串求LCS。傻逼了


3:写个有限状态机。获得C++代码中所有的注解。


三:系统设计:设计一个同时在线用户量为1亿时。程序要随时能够更新游戏的排名、用户要能查到自己排名。

我设计:

1:根据用户排名设计哈希算法。把1亿用户的数据映射到1W个文件中。这样每个文件有1W的用户。文件加上排名索引。

2:读写分离。即存系统和读系统分离成两部分。

3:用户读取数据时先按索引查到用户当前分数大致的排名文件。再在文件中进行查询。

4:存,因为存不是特别好控制。插入文件后更新所有文件的索引。但可能某个文件会变得特别大。当1个文件的用户量到达2W时候分裂文件。


后记:以上东西不一定正确。但我觉得我一个渣渣大学的本科生。能与这么多研究生在一个考场里笔试还是蛮爽的。继续找工作ing....

2015百度校招笔试杭州站