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

[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
邮件 [e-mail]

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

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

[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 赞，请给[e-mail] 发邮件报手机号，我们给你充值。

[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 看起来很大啊。