阿里巴巴笔试和面试题

只看该作者 · 2012-9-12 17:46

面试题：
1、hash_map 和map的区别是什么？内部怎么实现的？
2、给你1亿个无序的0--1之间的随机小数（精确到0.001），给定一组N个查询范围[x1,y1] [x2,y2] ......[xi,yi] ......[xn,yn] (xi,yi是0--1之间的小数，xi<=yi，精确到0.001)，对于每个查询范围，输出在其范围内的数字的个数。

笔试题：
1、寻找一个字符串中最长的重复子串。如 abcdabc 最长重复串是abc
2、给你一个wordsList，包含很多英文词组，然后再给你一个description，让你判断是否有wordsList中的词组在description中出现过。
例如 wordsList []={"apple" , "play boys","school"}
description = "play boy in school";
description 包含了school，应该返回true，并没有包含play boys。
bool check(list<string> wordsList, string description);
这个没什么好说的，暴力找出所有子串然后挨个去跟链表里的比较。
3、假设上面的wordsList 的包含的词组很多，长度N很大，而description的长度很小，怎么进行优化？优化后的时间复杂度是多少？？

只看该作者 · 2012-9-12 18:09

笔试题可以先对wordsList建立一棵 Trie 树，然后对description拆分子串来查找 Trie树

只看该作者 · 2012-9-12 18:17

面试题：
1.一个是hash，一个是红黑树？忘了
2.1亿个无序的0--1之间的随机小数（精确到0.001）
  int num[1000];//初始化为0
  1亿个数乘以1000再num[key]++;
  查询的时候也乘以1000查
笔试题：
1.不知道
2.没有说明description多大，子词组是2^N的
3.不知道

阿里巴巴笔试和面试题

相关下载

相关帖子