各位程序猿,为了方便大家找工作的时候备考,我们做了一个专门面向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
gooffer 2015-01-04 09:47:48 +08:00
第一题选择C,因为==比较的是指针,所以返回false。 我要话费。
|
2
rainday 2015-01-04 09:52:03 +08:00
听说参与的猿猿新年都有女朋友。└(^o^)┘
|
3
Cee 2015-01-04 09:57:05 +08:00
第二题为何不去看看 Coolshell 呢(
|
4
fyh1807008 2015-01-04 10:07:33 +08:00
这种直接上机就知道答案的题还是别发了吧
|
5
nowcoder OP @fyh1807008 上机的题目运行下就知道答案,但是具体的原因又是什么呢? 还是要理解fork,equals和==的概念的。
|
6
tnx2014 2015-01-04 10:17:56 +08:00 1
第二题没接触过Unix的看来是完全抓瞎,这一点太像医生了,只学好自己专业科是不行的,面试一定会全考察。
|
7
cute 2015-01-04 10:23:54 +08:00 1
第一题没有正确答案,因为那个是0而不是o
|
8
jinyang656 2015-01-04 10:24:11 +08:00
@gooffer 明显不是 C 啊。。。c[]最后一个元素是数字0.
|
9
jinyang656 2015-01-04 10:25:02 +08:00
@cute 你都看出来了为何不选B.
|
10
gooffer 2015-01-04 10:30:45 +08:00
@jinyang656 题目是要求返回false的,我说的是选项C
|
11
msg7086 2015-01-04 10:37:58 +08:00 1
第一题不说哪种语言真的没问题吗?
|
12
jinyang656 2015-01-04 10:38:35 +08:00
@gooffer 字符串常量是在常量池上分配的,所以s和t引用的是同一对象,C选项返回true
|
14
liushuaikobe 2015-01-04 10:45:45 +08:00
第一题必然选B啊,JVM常数池啊
|
15
canautumn 2015-01-04 10:46:10 +08:00
c最后一个就算是o还是选B。话说这种题真的很没意思。
|
16
liushuaikobe 2015-01-04 10:47:49 +08:00
第二题子进程里面继续执行循环,又fork出新的子进程,慢慢理一理
|
17
jookr 2015-01-04 10:48:53 +08:00 1
故意埋雷还是怎样? ||写成了II
mysql 写成了mysq1 |
18
thonatos 2015-01-04 10:50:44 +08:00
我得世界里现在基本只有var str = ‘’;String str = ''——这是什么东西?
|
19
wangxiaolin 2015-01-04 10:53:04 +08:00
第二题,耗子老师讲过,见http://coolshell.cn/articles/7965.html
|
20
rainday 2015-01-04 10:53:53 +08:00
@liushuaikobe 发现fork一理起来就会乱,哈哈哈
|
22
thonatos 2015-01-04 10:59:22 +08:00
|
23
wgwang 2015-01-04 10:59:39 +08:00
第1题, b。原因是,c的最后一个字符是 数字0(零),不是字母o。
楼主是猴子派来的耍的? |
26
flynngao 2015-01-04 11:03:03 +08:00 2
好无聊的题目,继续去刷leetcode了,最烦各种语法问题了,又记不住有没实际用途,实际中通过编码规范指定只能用某些工具类处理字符串,浮点数就好了
|
27
nowcoder OP @flynngao 编程题就是爽啊,来试试我们内测的编程题吧 支持在线判题的。
http://www.nowcoder.com/questionCenter?mutiTagIds=&questionTypes=000100&difficulty=&page=1 |
28
hepin1989 2015-01-04 11:05:54 +08:00
第一题写个0而不是o真是脑子有病,如果是o的话选择b
|
29
rainday 2015-01-04 11:08:11 +08:00
@hepin1989 哈哈哈,你试试把0换成o,在java上跑跑结果是怎么样的,我发现0和o的结果都是false。 是我jvm的问题吗?
|
30
cancan 2015-01-04 11:24:33 +08:00
最后一个有点难。。
|
31
wangxiaoxiao 2015-01-04 11:29:38 +08:00
最后一题数字有范围嘛?可以用位图来实现吧,用2bit代表一个数的状态,0--代表A和B文件都没有,1--代表A文件有,2--代表有A和B文件都有,然后扫描一遍文件A和B,最后从头开始把位图中状态为2的输出即可~~#给我话费#
|
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. |
34
nowcoder OP @funky 正解!,请给[email protected] 发邮件留手机号码我们来充值。
|
39
aheadlead 2015-01-04 12:00:23 +08:00
第三题两个文件直接排序 比一下不就出来了....
|
40
aheadlead 2015-01-04 12:01:30 +08:00
第三题数字范围也不知道...
|
41
hustlike 2015-01-04 12:32:31 +08:00
做了几个题,可以等收钱了?:)
|
42
hualuogeng 2015-01-04 12:36:57 +08:00 via Android
第三题位图,编程珠玑
|
43
xylophone21 2015-01-04 13:00:20 +08:00
第三题不到10M个数字,如果不是大数(int64能存的下的话),一个文件不到80M,两个160M内存可以存下.
存储方面的问题大家想多了吧? 至于时间问题,绝对不会少于o(n), 特殊点的如@hualuogeng说的位图 通用的方法用hash表,都是o(n). 不过个人更喜欢hash,虽然内存会多一些,但抽象的更好.不过说回来,位图也是更特殊的hash表实现而已 |
44
nowcoder OP @xylophone21 总共20m的数 hash函数冲突会不会比较高? 位图需要多少的内存?
|
46
PP 2015-01-04 13:39:55 +08:00 via Android
没有人认识到这种行为其实是作弊吗?
|
47
Esay 2015-01-04 13:45:05 +08:00
第三题,
空间复杂度:如果是整形(32位),位图需要 512MB 空间 时间复杂度:O(n) 时间可以找出相同的数值,再排序,需要O(nlog(n)) |
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个 - |
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- |
51
Esay 2015-01-04 14:36:32 +08:00
|
52
huanghuaxin 2015-01-04 14:41:29 +08:00
好像没有前端题啊… 果然前端不算程序猿的节奏…
|
53
sdysj 2015-01-04 14:58:27 +08:00
天朝傻帽真是多得不够用。。。
|
54
nowcoder OP @v2014 赞,请给[email protected] 发邮件报手机号,我们给你充值。
|
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一下就是要的结果了。 |
57
dallaslu 2015-01-04 16:39:37 +08:00
拿应试教育的经验,来“应面试”
|
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()冒泡即可 |
59
xylophone21 2015-01-04 17:28:48 +08:00
|
60
nowcoder OP @xylophone21 2^63/8 看起来很大啊。
|
61
gongweixin 2015-01-04 20:35:27 +08:00
抽了30次毛都没中..
|
62
nowcoder OP @gongweixin 下次再试试啦,分享中奖概率低与注册邀请的。
|
63
spacewander 2015-01-04 21:19:06 +08:00
第二道题,能不能采用sort然后merge的思路呢?
对于其他两种方法(位图和hash),这种方法占用空间最小,运行时间最长。只是不知道到底是节省空间优先还是缩短时间优先? 话说,三种方法中,位图占用空间最大,运行时间最短;而sort然后merge占用空间最小,运行时间最长。算法真是充满trade-off呢。 |
65
tshwangq 2015-01-04 22:02:43 +08:00
要注册,不看
|
66
fffe5390 2015-01-05 09:07:05 +08:00
第三题
瞎掰一下 总体思路是两个大文件分别排序后,归并判断重复数字并输出。 大文件排序处理: 如果不限制内存,io速度等硬件条件的话,最快的个人觉得是并发多路归并排序,把大文件拆成小文件(也不用太小,具体再权衡),这样可以并行处理,排序所需时间大致就等于小文 件排序时间,分成的小文件随便用什么排序,考虑到是数字并且非重复的,那就桶排或者快排吧。 实际效果受多方面因素影响,也许还没有其他方案好,纯讨论分析 |
67
xylophone21 2015-01-05 10:58:48 +08:00
@nowcoder 那没办法,位图本质上是一个桶超大的hash表.
|