百度笔试题和面试题答案(最新)(2)

更新时间:2018-11-22 15:58作者:王新老师

      顺着百度的笔试不可能那么弱智的想法,同时给出的例子也符合第二种情况的形势,就照着第二种思路往下做。这个题目在从鼓楼到浦口的鼓扬线上最近刚看过,就是编程珠玑II(More Programming Pearls) ,第13章的内容(绝妙的取样)。对于这个题,就是给出abc*2, a*3, de*5,输出随机排列。比较笨的算法就是每次得到一个随机数,如果这个随机数代表的球已经耗尽,那就取下一个随机数。这样的缺点是效率低,越往后效率越低,基本是在拼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

      prefix 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记录,即可以快速得到

    为您推荐

    2019年两会《政府工作报告》养老金新政策,要提高养老保障水平

    《关于2018年中央和地方预算执行情况与2019年中央和地方预算草案的报告》要求,提高养老保障水平。从2019年1月1日起,按平均约5%的幅度提高企业和机关事业单位退休人员基本养老金标准。

    2019-06-13 04:57

    如何在另类面试问题中胜出

    在面试中,有些考官会先提一个不甚友好的问题,或者劈头浇你一盆冷水,让你在委屈和激愤中露出本色。在他看来,击溃你的心理防线,才能筛选出有心理承受能力的智者,找到能面对压力的新鲜血液。要想在压力面试中胜出,只能学会绕开陷阱,奋战到底。

    2019-06-08 03:00

    面试紧张时应该怎么办

    面试是进入公职机关的最后一道主要的门槛,因此可以说每一位进入面试的人,心里就像绷住一根弦一样,也就是说每位考生,都会以高度的精神状态去抓住这次进入角色的机会。出现紧张、焦虑的心情也是不可避免的,只有认识了解,才能完全的克服。

    2019-06-08 02:58

    面对变故 学会自我解嘲

    面对降级、减薪、甚至解雇、离婚、丧子等变故,许多人反应过度,很长时间缓不过劲儿来。而有的人却能很快度过,重返正常的生活轨道。其决定因素是一种特殊的心理素质:心理复原力。有了它,人们不怕挫折;而缺少它,会特别害怕受伤害,不敢付出行动。

    2019-06-06 03:12

    办公室里该与不该谈论的话题

    办公室是一个充满原则、纪律,讲求策略的场合,更是一个充满利益冲突的是非之所。既如此,办公室里谈个人私事是否妥当呢?网上调查显示,尽管九成以上的人认为“办公室里隐私不宜说”,但是她/他们又同时承认有在办公室里谈论涉及私人感情、家庭关系、同事喜恶和上下级关系等隐私性内容的行为。

    2019-06-06 03:10

    面试自我介绍的几大原则

    应聘到外企或其他用人单位时,求职者往往最先被问及的问题就是“请先介绍介绍你自己”。这个问题看似简单,但求职者一定要慎重对待,它是你突出优势和特长,展现综合素质的好机会。回答得好,会给人留下良好的第一印象。

    2019-06-01 03:19

    外企面试必须要注意的五“必要”

    到外企面试前,仅仅准备好一份简历是不够的,还要提前做好面试前的“功课”,这样面试通过的几率就会大大增加。

    2019-06-01 03:16

    加载中...