悬赏大牛解答求职题目，有现金和礼物答谢（本月每日更新）

[nowcoder]

各位程序猿，为了方便大家找工作的时候备考，我们做了一个专门面向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]

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

再次感谢大家！祝大家新年行好运，早日找到女朋友！！

补充：第一个题目是JAVA类型。

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

求大牛讨论第三题

第一个题目20元话费已经充值到Funky。多谢参与。
大牛们不来试试后面的题目吗？ 是不是有点小难。哈哈

@v2014 20元话费已经充值，请查收。多谢参加活动

今日题目只剩最后一题啦～小伙伴们加油吧。

[gooffer]

第一题选择C，因为==比较的是指针，所以返回false。 我要话费。

[rainday]

听说参与的猿猿新年都有女朋友。└(^o^)┘

[Cee]

第二题为何不去看看 Coolshell 呢(

[fyh1807008]

这种直接上机就知道答案的题还是别发了吧

[nowcoder]

@fyh1807008 上机的题目运行下就知道答案，但是具体的原因又是什么呢？ 还是要理解fork，equals和＝＝的概念的。

[tnx2014]

第二题没接触过Unix的看来是完全抓瞎，这一点太像医生了，只学好自己专业科是不行的，面试一定会全考察。

[cute]

第一题没有正确答案,因为那个是0而不是o

[jinyang656]

@gooffer 明显不是 C 啊。。。c[]最后一个元素是数字0.

[jinyang656]

@cute 你都看出来了为何不选B.

[gooffer]

@jinyang656 题目是要求返回false的，我说的是选项C

[msg7086]

第一题不说哪种语言真的没问题吗？

[jinyang656]

@gooffer 字符串常量是在常量池上分配的，所以s和t引用的是同一对象，C选项返回true

[nowcoder]

@msg7086 不好意思遗漏了，第一题是Java的题目

[liushuaikobe]

第一题必然选B啊，JVM常数池啊

[canautumn]

c最后一个就算是o还是选B。话说这种题真的很没意思。

[liushuaikobe]

第二题子进程里面继续执行循环，又fork出新的子进程，慢慢理一理

[jookr]

故意埋雷还是怎样？ ||写成了II
mysql 写成了mysq1

[thonatos]

我得世界里现在基本只有var str = ‘’;String str = ''——这是什么东西？

[wangxiaolin]

第二题，耗子老师讲过，见http://coolshell.cn/articles/7965.html

[rainday]

@liushuaikobe 发现fork一理起来就会乱，哈哈哈

[rainday]

@thonatos java啦。var是js吧？

[thonatos]

@rainday

....谢谢解答（我也学过那么几年java...这是让我哭晕在办公室？）
好吧，我得意思是，现在工作是fe，就算写be的东西也是nodeJs。

[wgwang]

第1题， b。原因是，c的最后一个字符是 数字0（零），不是字母o。
楼主是猴子派来的耍的？

[nowcoder]

@jookr 多谢纠错，网站上已经更新。

[nowcoder]

@wgwang 如果是o那就不选么？(((o(*ﾟ▽ﾟ*)o)))

[flynngao]

好无聊的题目，继续去刷leetcode了，最烦各种语法问题了，又记不住有没实际用途，实际中通过编码规范指定只能用某些工具类处理字符串，浮点数就好了

[nowcoder]

@flynngao 编程题就是爽啊，来试试我们内测的编程题吧 支持在线判题的。

http://www.nowcoder.com/questionCenter?mutiTagIds=&questionTypes=000100&difficulty=&page=1

[hepin1989]

第一题写个0而不是o真是脑子有病，如果是o的话选择b

[rainday]

@hepin1989 哈哈哈，你试试把0换成o，在java上跑跑结果是怎么样的，我发现0和o的结果都是false。 是我jvm的问题吗？

[cancan]

最后一个有点难。。

[wangxiaoxiao]

最后一题数字有范围嘛？可以用位图来实现吧，用2bit代表一个数的状态，0--代表A和B文件都没有，1--代表A文件有，2--代表有A和B文件都有，然后扫描一遍文件A和B，最后从头开始把位图中状态为2的输出即可~~#给我话费#

[funky]

第一题选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]

@rainday 是o的话选择b，是0的话是出题的人脑子有问题

[nowcoder]

@funky 正解！，请给[email protected] 发邮件留手机号码我们来充值。

[nowcoder]

@hepin1989 加班脑子浆糊啦。

[funky]

@nowcoder 卧槽,这都中奖了,邮件已发,用的企鹅446463844 :)

[funky]

@nowcoder 收到。感谢哈。。真金白银呢。

[nowcoder]

@funky 我们是拿了投资的正规公司。 多谢参加，话费已经充值，请查收

[aheadlead]

第三题两个文件直接排序 比一下不就出来了....

[aheadlead]

第三题数字范围也不知道...

[hustlike]

做了几个题，可以等收钱了？:)

[hualuogeng]

第三题位图，编程珠玑

[xylophone21]

第三题不到10M个数字,如果不是大数(int64能存的下的话),一个文件不到80M,两个160M内存可以存下.
存储方面的问题大家想多了吧?

至于时间问题,绝对不会少于o(n),
特殊点的如@hualuogeng说的位图
通用的方法用hash表,都是o(n).
不过个人更喜欢hash,虽然内存会多一些,但抽象的更好.不过说回来,位图也是更特殊的hash表实现而已

[nowcoder]

@xylophone21 总共20m的数 hash函数冲突会不会比较高? 位图需要多少的内存？

[nowcoder]

@hustlike 网站上的活动我们每天会审核，只要答案正确被选为系统推荐就有奖金， 多谢参与。

[PP]

没有人认识到这种行为其实是作弊吗？

[Esay]

第三题，

空间复杂度：如果是整形（32位），位图需要 512MB 空间

时间复杂度：O(n) 时间可以找出相同的数值，再排序，需要O(nlog(n))

[wog]

第二题6个
进程p1会创建两个新的进程，第一个进程p2的i=0，第二个p3的i=1，
p3会打印一个-然后返回，
p2进程会打印一个 - 然后创建一个i= 1的子进程p4，然后在打印一个 - 然后返回 ；
p4打印一个 - 然后返回，
p1本身会打印 两个 -
一共6个 -

[rainday]

@Esay 位图遍历一下就已经是排序过度，不需要再排序了，不过需要遍历整个整形范围

[v2014]

第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]

简单写了一下

https://gist.github.com/Jeswang/5f73aaf8625f1ad38d6d

[huanghuaxin]

好像没有前端题啊… 果然前端不算程序猿的节奏…

[sdysj]

天朝傻帽真是多得不够用。。。

[nowcoder]

@v2014 赞，请给[email protected] 发邮件报手机号，我们给你充值。

[msg7086]

第三题

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

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

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

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

另外分割开以后还可以充分利用多线程的优势来并行处理。
最后再merge一下就是要的结果了。

[v2014]

@nowcoder 已经收到了，3q

[dallaslu]

拿应试教育的经验，来“应面试”

[jasonding]

我是菜鸟，如果面试我的话，第三题的答案是这样的

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]

@nowcoder hash冲突看你的hash函数和桶的大小,桶大四倍,160*4M的内存也不是问题.

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

另外@Esay说的对,这个题目也许是想考察查找,却不小心让排序成了最高时间复杂度. 所以提前优化是万恶之源啊,哈哈.

[nowcoder]

@xylophone21 2^63/8 看起来很大啊。

[gongweixin]

抽了30次毛都没中..

[nowcoder]

@gongweixin 下次再试试啦，分享中奖概率低与注册邀请的。

[spacewander]

第二道题，能不能采用sort然后merge的思路呢？
对于其他两种方法（位图和hash），这种方法占用空间最小，运行时间最长。只是不知道到底是节省空间优先还是缩短时间优先？

话说，三种方法中，位图占用空间最大，运行时间最短；而sort然后merge占用空间最小，运行时间最长。算法真是充满trade-off呢。

[nowcoder]

@Esay 被中国政府盾了，看不到。。哭啊

[tshwangq]

要注册，不看

[fffe5390]

第三题
瞎掰一下
总体思路是两个大文件分别排序后，归并判断重复数字并输出。

大文件排序处理：
如果不限制内存，io速度等硬件条件的话，最快的个人觉得是并发多路归并排序，把大文件拆成小文件(也不用太小，具体再权衡)，这样可以并行处理，排序所需时间大致就等于小文 件排序时间，分成的小文件随便用什么排序，考虑到是数字并且非重复的，那就桶排或者快排吧。
实际效果受多方面因素影响，也许还没有其他方案好，纯讨论分析

[xylophone21]

@nowcoder 那没办法,位图本质上是一个桶超大的hash表.