悬赏大牛解答求职题目,有现金和礼物答谢(本月每日更新) - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
请不要在回答技术问题时复制粘贴 AI 生成的内容
nowcoder
V2EX    程序员

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

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

    各位程序猿,为了方便大家找工作的时候备考,我们做了一个专门面向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
    yufz
        8
    yufz  
       2015-01-04 10:24:11 +08:00
    @gooffer 明显不是 C 啊。。。c[]最后一个元素是数字0.
    yufz
        9
    yufz  
       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
    第一题不说哪种语言真的没问题吗?
    yufz
        12
    yufz  
       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
    SuYia
        18
    SuYia  
       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吧?
    SuYia
        22
    SuYia  
       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   &nbp; FAQ     Solana     3959 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 28ms UTC 00:17 PVG 08:17 LAX 17:17 JFK 20:17
    Do have faith in what you're doing.
    ubao snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86