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

悬赏大牛解答求职题目,有现金和礼物答谢(本月每日更新)

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

    各位程序猿,为了方便大家找工作的时候备考,我们做了一个专门面向IT互联网行业程序员的求职笔试面试备考的题库网站:(牛客网) http://www.nowcoder.com/

    目前,牛客网 http://www.nowcoder.com/ 上积累了谷歌、腾讯、百度、阿里、小米、优酷、网易等几十家互联网公司的笔试面试题目。当前部分题目尚未有最佳答案和解释,为了更好的服务程序猿们,我们做了一个活动,悬赏大牛解答,每道题目根据难度对应一定的现金奖励,最高一道题目奖励100元,还有iPhone、移动硬盘、小米手环等众多好礼相送。

    活动地址猛戳→_→: http://www.nowcoder.com/activity/challenge

    今天开始至1月29日,我们会在论坛持续更新本贴,每天放出1-3道题目,大家可以跟帖解答,最先正确解答出来的朋友将会获得话费充值、笔记本等礼物。获奖的朋友名单会在第二天更新。
    今天的题目如下:
    1、
    假设有以下代码
    String s = "hello";
    String t = "hello";
    char c[] = {'h', 'e', 'l', 'l', '0'};
    下列选项中返回false的语句是:
    A s.equals(t);
    B t.equals(c);
    C s==t;
    D t.equals(new String("hello"));

    2、
    // 请问下面的程序一共输出多少个“-”?为什么?

    #include <stdio.h>
    #include <sys/types.h>
    #include <unistd.h>
    
    int main(void) {
        int i;
        for (i=0; i<2; i++) {
            fork();
            printf("-\n");
        }
        return 0;
    }
    

    3、
    有A、B两个文件,文件格式相同,均为每行一个十进制整型数字,两个文件的行数不一定相等,但均在一千万行左右。A文件中的数字两两不等,B文件中的数字两两不等, 请用一个算法找出A和B两文件中所有相同的数,并且从小到大有序输出。请考虑统计程序如何实现,给出设计思路和关键算法(可使用伪代码),并估计程序核心代码的时间复杂度和空间复杂度。

    牛客网在内测期间得到了V2EX论坛众多朋友的支持和宝贵建议,内测邀请帖子回顾:
    http://v2ex.com/t/134907
    http://v2ex.com/t/137986

    欢迎关注我们,活动结束后我们会把面试题整理成PDF分发给参与的用户
    微薄 http://www.weibo.com/nowcoder
    微信 www_nowcoder_com
    QQ群 157594705
    邮件 [email protected]

    如果你手里有更多的笔试面试题,欢迎联系我们,重金求购

    再次感谢大家!祝大家新年行好运,早日找到女朋友!!
    
    第 1 条附言  ·  2015-01-04 11:19:22 +08:00
    补充:第一个题目是JAVA类型。

    为什么没有人讨论最后一个题目呢,是太难了吗???

    求大牛讨论第三题
    第 2 条附言  ·  2015-01-04 11:55:31 +08:00
    第一个题目20元话费已经充值到Funky。多谢参与。
    大牛们不来试试后面的题目吗? 是不是有点小难。哈哈
    第 3 条附言  ·  2015-01-04 15:30:07 +08:00
    @v2014 20元话费已经充值,请查收。多谢参加活动

    今日题目只剩最后一题啦~小伙伴们加油吧。
    67 条回复    2015-01-05 10:58:48 +08:00
    gooffer
        1
    gooffer  
       2015-01-04 09:47:48 +08:00
    第一题选择C,因为==比较的是指针,所以返回false。 我要话费。
    rainday
        2
    rainday  
       2015-01-04 09:52:03 +08:00
    听说参与的猿猿新年都有女朋友。└(^o^)┘
    Cee
        3
    Cee  
       2015-01-04 09:57:05 +08:00
    第二题为何不去看看 Coolshell 呢(
    fyh1807008
        4
    fyh1807008  
       2015-01-04 10:07:33 +08:00
    这种直接上机就知道答案的题还是别发了吧
    nowcoder
        5
    nowcoder  
    OP
       2015-01-04 10:13:06 +08:00
    @fyh1807008 上机的题目运行下就知道答案,但是具体的原因又是什么呢? 还是要理解fork,equals和==的概念的。
    tnx2014
        6
    tnx2014  
       2015-01-04 10:17:56 +08:00   ❤️ 1
    第二题没接触过Unix的看来是完全抓瞎,这一点太像医生了,只学好自己专业科是不行的,面试一定会全考察。
    cute
        7
    cute  
       2015-01-04 10:23:54 +08:00   ❤️ 1
    第一题没有正确答案,因为那个是0而不是o
    jinyang656
        8
    jinyang656  
       2015-01-04 10:24:11 +08:00
    @gooffer 明显不是 C 啊。。。c[]最后一个元素是数字0.
    jinyang656
        9
    jinyang656  
       2015-01-04 10:25:02 +08:00
    @cute 你都看出来了为何不选B.
    gooffer
        10
    gooffer  
       2015-01-04 10:30:45 +08:00
    @jinyang656 题目是要求返回false的,我说的是选项C
    msg7086
        11
    msg7086  
       2015-01-04 10:37:58 +08:00   ❤️ 1
    第一题不说哪种语言真的没问题吗?
    jinyang656
        12
    jinyang656  
       2015-01-04 10:38:35 +08:00
    @gooffer 字符串常量是在常量池上分配的,所以s和t引用的是同一对象,C选项返回true
    nowcoder
        13
    nowcoder  
    OP
       2015-01-04 10:39:59 +08:00
    @msg7086 不好意思遗漏了,第一题是Java的题目
    liushuaikobe
        14
    liushuaikobe  
       2015-01-04 10:45:45 +08:00
    第一题必然选B啊,JVM常数池啊
    canautumn
        15
    canautumn  
       2015-01-04 10:46:10 +08:00
    c最后一个就算是o还是选B。话说这种题真的很没意思。
    liushuaikobe
        16
    liushuaikobe  
       2015-01-04 10:47:49 +08:00
    第二题子进程里面继续执行循环,又fork出新的子进程,慢慢理一理
    jookr
        17
    jookr  
       2015-01-04 10:48:53 +08:00   ❤️ 1
    故意埋雷还是怎样? ||写成了II
    mysql 写成了mysq1
    thonatos
        18
    thonatos  
       2015-01-04 10:50:44 +08:00
    我得世界里现在基本只有var str = ‘’;String str = ''——这是什么东西?
    wangxiaolin
        19
    wangxiaolin  
       2015-01-04 10:53:04 +08:00
    第二题,耗子老师讲过,见http://coolshell.cn/articles/7965.html
    rainday
        20
    rainday  
       2015-01-04 10:53:53 +08:00
    @liushuaikobe 发现fork一理起来就会乱,哈哈哈
    rainday
        21
    rainday  
       2015-01-04 10:54:27 +08:00
    @thonatos java啦。var是js吧?
    thonatos
        22
    thonatos  
       2015-01-04 10:59:22 +08:00
    @rainday

    ....谢谢解答(我也学过那么几年java...这是让我哭晕在办公室?)
    好吧,我得意思是,现在工作是fe,就算写be的东西也是nodeJs。
    wgwang
        23
    wgwang  
       2015-01-04 10:59:39 +08:00
    第1题, b。原因是,c的最后一个字符是 数字0(零),不是字母o。
    楼主是猴子派来的耍的?
    nowcoder
        24
    nowcoder  
    OP
       2015-01-04 11:00:20 +08:00
    @jookr 多谢纠错,网站上已经更新。
    nowcoder
        25
    nowcoder  
    OP
       2015-01-04 11:03:01 +08:00   ❤️ 1
    @wgwang 如果是o那就不选么?(((o(*゚▽゚*)o)))
    flynngao
        26
    flynngao  
       2015-01-04 11:03:03 +08:00   ❤️ 2
    好无聊的题目,继续去刷leetcode了,最烦各种语法问题了,又记不住有没实际用途,实际中通过编码规范指定只能用某些工具类处理字符串,浮点数就好了
    nowcoder
        27
    nowcoder  
    OP
       2015-01-04 11:05:03 +08:00
    @flynngao 编程题就是爽啊,来试试我们内测的编程题吧 支持在线判题的。

    http://www.nowcoder.com/questionCenter?mutiTagIds=&questionTypes=000100&difficulty=&page=1
    hepin1989
        28
    hepin1989  
       2015-01-04 11:05:54 +08:00
    第一题写个0而不是o真是脑子有病,如果是o的话选择b
    rainday
        29
    rainday  
       2015-01-04 11:08:11 +08:00
    @hepin1989 哈哈哈,你试试把0换成o,在java上跑跑结果是怎么样的,我发现0和o的结果都是false。 是我jvm的问题吗?
    cancan
        30
    cancan  
       2015-01-04 11:24:33 +08:00
    最后一个有点难。。
    wangxiaoxiao
        31
    wangxiaoxiao  
       2015-01-04 11:29:38 +08:00
    最后一题数字有范围嘛?可以用位图来实现吧,用2bit代表一个数的状态,0--代表A和B文件都没有,1--代表A文件有,2--代表有A和B文件都有,然后扫描一遍文件A和B,最后从头开始把位图中状态为2的输出即可~~#给我话费#
    funky
        32
    funky  
       2015-01-04 11:31:03 +08:00   ❤️ 1
    第一题选B,顺便贴上 源码.
    if (this == anObject) {
    return true;
    }
    if (anObject instanceof String) {
    String anotherString = (String) anObject;
    int n = value.length;
    if (n == anotherString.value.length) {
    char v1[] = value;
    char v2[] = anotherString.value;
    int i = 0;
    while (n-- != 0) {
    if (v1[i] != v2[i])
    return false;
    i++;
    }
    return true;
    }
    }
    return false;
    类型不同直接返回flase.
    hepin1989
        33
    hepin1989  
       2015-01-04 11:32:56 +08:00
    @rainday 是o的话选择b,是0的话是出题的人脑子有问题
    nowcoder
        34
    nowcoder  
    OP
       2015-01-04 11:33:19 +08:00
    @funky 正解!,请给[email protected] 发邮件留手机号码我们来充值。
    nowcoder
        35
    nowcoder  
    OP
       2015-01-04 11:34:18 +08:00
    @hepin1989 加班脑子浆糊啦。
    funky
        36
    funky  
       2015-01-04 11:45:41 +08:00
    @nowcoder 卧槽,这都中奖了,邮件已发,用的企鹅446463844 :)
    funky
        37
    funky  
       2015-01-04 11:52:25 +08:00
    @nowcoder 收到。感谢哈。。真金白银呢。
    nowcoder
        38
    nowcoder  
    OP
       2015-01-04 11:52:53 +08:00
    @funky 我们是拿了投资的正规公司。 多谢参加,话费已经充值,请查收
    aheadlead
        39
    aheadlead  
       2015-01-04 12:00:23 +08:00
    第三题两个文件直接排序 比一下不就出来了....
    aheadlead
        40
    aheadlead  
       2015-01-04 12:01:30 +08:00
    第三题数字范围也不知道...
    hustlike
        41
    hustlike  
       2015-01-04 12:32:31 +08:00
    做了几个题,可以等收钱了?:)
    hualuogeng
        42
    hualuogeng  
       2015-01-04 12:36:57 +08:00 via Android
    第三题位图,编程珠玑
    xylophone21
        43
    xylophone21  
       2015-01-04 13:00:20 +08:00
    第三题不到10M个数字,如果不是大数(int64能存的下的话),一个文件不到80M,两个160M内存可以存下.
    存储方面的问题大家想多了吧?

    至于时间问题,绝对不会少于o(n),
    特殊点的如@hualuogeng说的位图
    通用的方法用hash表,都是o(n).
    不过个人更喜欢hash,虽然内存会多一些,但抽象的更好.不过说回来,位图也是更特殊的hash表实现而已
    nowcoder
        44
    nowcoder  
    OP
       2015-01-04 13:11:11 +08:00
    @xylophone21 总共20m的数 hash函数冲突会不会比较高? 位图需要多少的内存?
    nowcoder
        45
    nowcoder  
    OP
       2015-01-04 13:11:56 +08:00
    @hustlike 网站上的活动我们每天会审核,只要答案正确被选为系统推荐就有奖金, 多谢参与。
    PP
        46
    PP  
       2015-01-04 13:39:55 +08:00 via Android
    没有人认识到这种行为其实是作弊吗?
    Esay
        47
    Esay  
       2015-01-04 13:45:05 +08:00
    第三题,

    空间复杂度:如果是整形(32位),位图需要 512MB 空间

    时间复杂度:O(n) 时间可以找出相同的数值,再排序,需要O(nlog(n))
    wog
        48
    wog  
       2015-01-04 13:46:39 +08:00
    第二题6个
    进程p1会创建两个新的进程,第一个进程p2的i=0,第二个p3的i=1,
    p3会打印一个-然后返回,
    p2进程会打印一个 - 然后创建一个i= 1的子进程p4,然后在打印一个 - 然后返回 ;
    p4打印一个 - 然后返回,
    p1本身会打印 两个 -
    一共6个 -
    rainday
        49
    rainday  
       2015-01-04 13:50:23 +08:00
    @Esay 位图遍历一下就已经是排序过度,不需要再排序了,不过需要遍历整个整形范围
    v2014
        50
    v2014  
       2015-01-04 14:24:41 +08:00   ❤️ 1
    第2题,6个”-“
    先看没”\n“的
    #include <stdio.h>
    #include <sys/types.h>
    #include <unistd.h>

    int main(void) {
    int i, forkpid;

    for (i=0; i<2; i++) {
    forkpid=fork();
    printf("i:%d pid:%d forkpid:%d",i, getpid(), forkpid);
    printf("-");
    }
    return 0;
    }
    有8个,加上"\n",就是6个
    因为”\n“消除了printf的缓存
    这里有http://www.dewen.io/q/5944,http://www.oschina.net/question/1014816_133835?sort=time
    看它们打印的pid值,就知道执行顺序了
    i:0 pid:8532 forkpid:8736-i:1 pid:8532 forkpid:8436-i:0 pid:8736 forkpid:0-i:1 pid:8736 forkpid:9100-i:0 pid:8736 forkpid:0-i:1 pid:9100 forkpid:0-i:0 pid:8532 forkpid:8736-i:1 pid:8436 forkpid:0-
    Esay
        51
    Esay  
       2015-01-04 14:36:32 +08:00
    huanghuaxin
        52
    huanghuaxin  
       2015-01-04 14:41:29 +08:00
    好像没有前端题啊… 果然前端不算程序猿的节奏…
    sdysj
        53
    sdysj  
       2015-01-04 14:58:27 +08:00
    天朝傻帽真是多得不够用。。。
    nowcoder
        54
    nowcoder  
    OP
       2015-01-04 15:08:38 +08:00
    @v2014 赞,请给[email protected] 发邮件报手机号,我们给你充值。
    msg7086
        55
    msg7086  
       2015-01-04 15:59:37 +08:00
    第三题

    一种,像上面说的,位图打点。另一种,hashtable打点。
    一千万行数据也不多啊,10m个数用C++的unordered_map打点,1G内存怎么都够了。

    再有一种玩法, divide & conquer
    每次把一个文件分成 > MAX/2 和 < MAX/2 生成4个文件,再分成8个,16个,等等。

    然后每次处理一段,就非常省内存了。

    换我的话我会写个脚本无脑grep,比如把INT_MAX范围内的数字拆成22对文件什么的。

    另外分割开以后还可以充分利用多线程的优势来并行处理。
    最后再merge一下就是要的结果了。
    v2014
        56
    v2014  
       2015-01-04 16:35:42 +08:00
    @nowcoder 已经收到了,3q
    dallaslu
        57
    dallaslu  
       2015-01-04 16:39:37 +08:00
    拿应试教育的经验,来“应面试”
    jasonding
        58
    jasonding  
       2015-01-04 17:05:25 +08:00
    我是菜鸟,如果面试我的话,第三题的答案是这样的

    Map<String,Boolean> a = new HashMap<String,Boolean>();
    //读取文件A的每一行存入A
    a.put("a1", true);
    ...
    a.put("amax", true);
    Map<String,Boolean> b = new HashMap<String,Boolean>();
    //读取文件B的每一行存入B
    b.put("b1", true);
    ...
    b.put("bmax", true);
    Map<String,String> val = new HashMap<String,String>();
    for(Entry<String, Boolean> map:b.entrySet()){
    if(a.get(map.getKey())){
    val.put(map.getKey(), map.getKey());
    }
    }
    val.values()冒泡即可
    xylophone21
        59
    xylophone21  
       2015-01-04 17:28:48 +08:00
    @nowcoder hash冲突看你的hash函数和桶的大小,桶大四倍,160*4M的内存也不是问题.

    位图要看你的最大数字, 还是以int64能存下为例的话, 2^63/8 字节(一个字节表示8个数)

    另外@Esay说的对,这个题目也许是想考察查找,却不小心让排序成了最高时间复杂度. 所以提前优化是万恶之源啊,哈哈.
    nowcoder
        60
    nowcoder  
    OP
       2015-01-04 19:50:18 +08:00
    @xylophone21 2^63/8 看起来很大啊。
    gongweixin
        61
    gongweixin  
       2015-01-04 20:35:27 +08:00
    抽了30次毛都没中..
    nowcoder
        62
    nowcoder  
    OP
       2015-01-04 21:12:11 +08:00
    @gongweixin 下次再试试啦,分享中奖概率低与注册邀请的。
    spacewander
        63
    spacewander  
       2015-01-04 21:19:06 +08:00
    第二道题,能不能采用sort然后merge的思路呢?
    对于其他两种方法(位图和hash),这种方法占用空间最小,运行时间最长。只是不知道到底是节省空间优先还是缩短时间优先?

    话说,三种方法中,位图占用空间最大,运行时间最短;而sort然后merge占用空间最小,运行时间最长。算法真是充满trade-off呢。
    nowcoder
        64
    nowcoder  
    OP
       2015-01-04 21:40:24 +08:00
    @Esay 被中国政府盾了,看不到。。哭啊
    tshwangq
        65
    tshwangq  
       2015-01-04 22:02:43 +08:00
    要注册,不看
    fffe5390
        66
    fffe5390  
       2015-01-05 09:07:05 +08:00
    第三题
    瞎掰一下
    总体思路是两个大文件分别排序后,归并判断重复数字并输出。

    大文件排序处理:
    如果不限制内存,io速度等硬件条件的话,最快的个人觉得是并发多路归并排序,把大文件拆成小文件(也不用太小,具体再权衡),这样可以并行处理,排序所需时间大致就等于小文 件排序时间,分成的小文件随便用什么排序,考虑到是数字并且非重复的,那就桶排或者快排吧。
    实际效果受多方面因素影响,也许还没有其他方案好,纯讨论分析
    xylophone21
        67
    xylophone21  
       2015-01-05 10:58:48 +08:00
    @nowcoder 那没办法,位图本质上是一个桶超大的hash表.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5400 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 06:58 · PVG 14:58 · LAX 23:58 · JFK 02:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.