V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nowcoder
V2EX  ›  程序员

30 家 IT 名企历年笔试面试题集合,( 1 月 9 日更新)

  •  
  •   nowcoder · 2015-01-09 10:41:39 +08:00 · 4056 次点击
    这是一个创建于 3606 天前的主题,其中的信息可能已经有所发展或是发生改变。

    先送上30家IT名企历年笔试面试题集合,请转发分享给身边的码农吧。
    http://weibo.com/2165760972/BEpE59YSp

    我们做了一个专门面向IT互联网行业程序员的求职笔试面试备考的题库网站
    牛客网 http://www.nowcoder.com?from=v2ex
    本月我们会在论坛持续发贴,每天放出1-3道题目,欢迎大家跟帖解答,最先正确解答出来的朋友将会获得话费充值、笔记本等礼物。获奖的朋友名单会在第二天公布。

    今日题目,来自百度

    注意:请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。 
    1. 假设一个 mp3 搜索引擎收录了 2^24 首歌曲,并记录了可收听这些歌曲的 2^30 条 URL,
    但每首歌的 URL 不超过 2^10 个。系统会定期检查这些 URL,如果一个 URL 不可用则不出现
    在搜索结果中。现在歌曲名和 URL 分别通过整型的 SONG_ID 和 URL_ID 唯一确定。对该系统
    有如下需求:
    1) 通过 SONG_ID 搜索一首歌的 URL_ID,给出 URL_ID 计数和列表
    2) 给定一个 SONG_ID,为其添加一个新的 URL_ID 
    3) 添加一个新的 SONG_ID 
    4) 给定一个 URL_ID,将其置为不可用
    限制条件:内存占用不超过 1G,单个文件大小不超过 2G,一个目录下的文件数不超过 128 个。
    为获得最佳性能,请说明设计的数据结构、搜索算法,以及资源消耗。如果系统数据量扩大,该如何
    多机分布处理
    

    这个题目是我们挑战活动的百元难题之一,在牛客网的回答被采纳为系统推荐就可获得100奖金
    来自http://www.nowcoder.com/questionTerminal/d3516831b19c4c608704280d31c4785d?from=v2ex
    更多难题现金求解
    http://www.nowcoder.com/activity/challenge?from=v2ex

    11 条回复    2015-01-11 16:13:33 +08:00
    xcv58
        1
    xcv58  
       2015-01-09 11:13:34 +08:00
    这种读多写少的很适合 mongodb ,但百度的题目 就不答了。
    december
        2
    december  
       2015-01-09 11:47:49 +08:00   ❤️ 1
    既然都允许使用社交账号登陆了。干嘛还非得让用户再填写邮箱呢。
    egrcc
        3
    egrcc  
       2015-01-09 11:52:25 +08:00
    您这是。。天天发呀
    broadliyn
        4
    broadliyn  
       2015-01-09 13:36:09 +08:00
    @egrcc 明显就是广告帖,建议@Livid删除
    Livid
        5
    Livid  
    MOD
       2015-01-09 13:46:33 +08:00
    @broadliyn 如果你不想再看到,可以 Block 这个账号。
    sleeperqp
        6
    sleeperqp  
       2015-01-09 16:01:09 +08:00   ❤️ 1
    //内存
    //SONG的主要数据结构
    struct SONG_NODE{
    int song_id;
    list<int>buffer; //缓存为8个URL_ID;
    string file;
    }
    //这里假设失效URL较少(╭(╯^╰)╮ 不然大部分失效了你还搜什么)
    //根据URL_ID即可该URL知道是否失效
    map<int,bool>IsNotaURL


    //文件为SONG的URL列表
    //SONG的URL列表
    //这个比较多变
    SONG_ID:{URL_ID,...URL_ID}
    //或者使用一些压缩编码比如VB编码等。



    2) 给定一个 SONG_ID,为其添加一个新的 URL_ID
    根据SONG_ID往其buffer中添加URL_ID
    若buffer已满 则先将buffer与SONG的URL列表文件进行合并。
    否则添加URL_ID进buffer
    3) 添加一个新的 SONG_ID
    new SONG_NODE,初始化一下。
    4) 给定一个 URL_ID,将其置为不可用
    在IsURL中设置即可,IsNotaURL(URL_ID) = true;
    1) 通过 SONG_ID 搜索一首歌的 URL_ID,给出 URL_ID 计数和列表
    给定URL_ID,读入URL的URL列表,并结合buffer与IsNotaURL输出URL列表,统计URL_ID计数即可

    细节问题:
    1.题目要求为1G内存,所以buffer大致能用2^30/2^24=2^6 除去一些别的大概能给2^5即8个URL_ID
    2.buffer与SONG合并: 首先是通过SONG_ID的查找SONG的URL列表问题:通过SONG_ID映射比如SONG_ID%128找到SONG所在文件 然后读取信息,合并,在文件中定位写回。
    其次使用压缩编码进行节省空间,VB编码等都可以。这样就不会超过单文件2G的要求了。(只要不把URL_ID都写入一个文件基本就不会超过这个限制)
    3.定时更新:定时将列表,buffer,IsNotaURL合并更新。
    数据量增大:
    一个方法是:通过SONG_ID(这里可能使用long long类型),通过SONG_ID的映射关系(如mod128)将SONG_ID处理对应到相关的机器上。
    PS:这里数据量增大应该是可以加大内存了,╭(╯^╰)╮终于可以加大buffer。
    zhangchioulin
        7
    zhangchioulin  
       2015-01-09 17:16:17 +08:00
    @sleeperqp 看不懂您的回答(哭)看来我离磨练还太少。。。
    cho
        8
    cho  
       2015-01-09 18:13:54 +08:00
    @Livid 哪样的被定义为过度广告 会被删除啊?
    Livid
        9
    Livid  
    MOD
       2015-01-09 18:45:36 +08:00
    @cho 和 V2EX 社区的讨论主题离得太远,同时又在一天内发布 N 条的内容。
    sleeperqp
        10
    sleeperqp  
       2015-01-09 22:19:06 +08:00
    @zhangchioulin 别= = 应该是我没写好吧- -
    mingyun
        11
    mingyun  
       2015-01-11 16:13:33 +08:00
    面试能真正用上吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1119 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 18:43 · PVG 02:43 · LAX 10:43 · JFK 13:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.