百度笔试题和面试题答案（2019最新）(二)

　　顺着百度的笔试不可能那么弱智的想法，同时给出的例子也符合第二种情况的形势，就照着第二种思路往下做。这个题目在从鼓楼到浦口的鼓扬线上最近刚看过，就是编程珠玑II(More Programming Pearls) ，第13章的内容(绝妙的取样)。对于这个题，就是给出abc2, a3, de5，输出随机排列。比较笨的算法就是每次得到一个随机数，如果这个随机数代表的球已经耗尽，那就取下一个随机数。这样的缺点是效率低，越往后效率越低，基本是在拼RP。还是拿例子说事儿，如果随机数为1-2，则输出abc，3-5输出a，6-10输出de。如果到了第9次，还剩下一个abc没输出，则要一直随机到出现1，2为止才结束。

　　第二种办法是Floyd提出来的(似乎就是那个Floyd-Warshall)。算法如下：

　　S = []

　　for j= 1 to N do

　　T = RandInt(1, j);

　　if T is not in S then

　　Pfix T to S

　　else

　　insert J in S after T

　　不过这个题目还有一个问题：对于每个字符串，生成的期望个数并不一定为整数。例子中的N改成5的话，那就是期望输出1.5个a和2.5个de，随机序列自然没法搞。这个时候回到第一个方法仍然可以做，不过题目也因此解释不通了。同学的解释是，如果是期望输出1.4个a和2.6个de，这一个a和de的争议值，在2/5的情况下输出a，剩下的情况输出b。不过我们其实是没有理由把这个不确定的情况限制在一个整数单位区间里的，即对于1.4个a和2.6个 de，必须输出1a+3de或者2a+2de才算合法输出，而把4de，3a+1de的情况定位非法。我觉得这块说不同，所以不需要考虑非整数的不确定情况(如果直接四舍五入到整数，还是算整数的确定情况的)。

　　设有n个正整数

　　设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

　　程序输入：n个数

　　程序输出：联接成的多位数

　　例如：

　　n=2时，2个整数32，321连接成的最小整数为：32132，

　　n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

　　[题目要求]

　　1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。

　　2. 给出算法的时间空间复杂度。

　　3. 证明你的算法。(非常重要)

　　解答:

　　这题我没怎么考虑。同学的思想在于，把n个正整数按优先级排个序，然后按照排序的结果从小到大排列组成最小的整数。注意这个排序并不是普通的算术排序，而是基于一定的规则。比较的时候把两个数字当成字符串进行字典排序，如果一个数字正好是另外一个数字的前缀的时候，去掉较长字符串的前缀，继续进行比较，直到分出胜负。当然也有旗鼓相当的时候，比如31和313131，这两者的优先级即相同。

　　时间复杂度，每次比较的平均时间复杂度为O(1)，假设输入为随机整数;排序使用快排，复杂度为O(nlgn)，所以最终时间复杂度为O(nlgn)。空间复杂度就是O(n)。

　　算法证明的话我倒是一时半会儿没搞出来。

　　在一个有1000万用户的系统中

　　在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概念

　　1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简写为uid);则uid的范围是从1到1000万的正整数。

　　2、好友：用户之间可以形成好友关系，好友是双向的;比如说uid为3和uid为4的两个用户可以互为好友。每个用户好友的上限是500个;用户之间的好友关系可以被解除

　　3、活动：每个用户只能发文章;文章可以被作者删除，其他人不能删除非自己发表的文章;每篇文章通过一个blogid表示。

　　4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系统中就是所有好友的文章更新列表。

　　5、访问量要求：所有feed访问量每天在1亿量级;所有的blogid增加量每天在百万量级。

　　题目：请在以上限制条件下，设计一个高效的feed访问系统。

　　要求：

　　1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed;feed的展现按照时间倒排序，最新的在最前面

　　2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友feed都是未被删除的

　　3、尽可能高效。

　　解答:

　　考虑了很久还是决定用数据库做，设计表。完全没有海量数据的表结构设计的经验，因此都是靠感觉来。没用什么技巧，除了数据库的水平分库。

　　数据库结构设计为4张表，结构如下(引用只是表示关联关系，并非加上外键约束)：

　　User

　　int uid#主键

　　char(12) username

　　Friend

　　int uid#用户uid，引用User.uid，加索引

　　int fuid#朋友uid，引用User.uid，加索引

　　Blog

　　int blogid#主键

　　int uid#发表用户uid，引用User.uid，加索引

　　varchar(60) title

　　text content

　　datetime publish_time

　　Feed#存储每个用户的好友feed列表

　　int uid#引用User.uid，加索引

　　int blogid#引用Blog.blogid，加索引

　　varchar(60) title#可有可无，根据生成Feed是否需要Feed标题决定

　　在存储方面，Friend表和Feed表数量较大，因此采用水平分库存储的形式。即Friend表分散在几个数据库内，按照第一个uid的最后几位进行划分。如有10个数据库，即可根据个位数映射到0-9号数据库上。同理可得Feed表的存储方式，按照uid进行水平分库。

　　如果用户a和用户b是好朋友，则在Friend表中添加(a,b)和(b,a)两条记录，分别添加到a，b所属的库里。解除关系的话删除这两条记录。

　　用户发表文章的时候，首先在Blog表添加一条记录;第二，查询Friend表得出当前用户的所有好友，然后给Feed表添加记录，格式为(好友id, blogid, title)，一共添加好友个数条记录。第三查询所有好友的Feed数记录，如果Feed超过了1000条，则删除该好友最早的一条Feed。第二第三步可以根据好友uid，把存储在相同库的好友Feed在同一次操作里批量添加/查询/删除。

　　用户要得到自己的Feed列表，只需要先计算自己的uid属于哪个数据库，然后从该数据库里取出所有的Feed记录，即可以快速得到