这道面试题怎么做？

今天面试碰到这样一个题，想不出来，请教牛人啊
有一个文本文件（大小任意），内容为一篇文章（为简化编程难度，假设你的机器可用内存很小，可能会小于文本的大小，试设计一个高效的算法，读取文本文件，能统计中文文本中出现的单词的出现频率，并按由大到小进行统计输出。完成程序后请对的你的程序进行自我评价，指出程序可以改进的地方还有哪些？程序时候还有其他方式实现）

13 个解决方案

#1

该回复于2013-05-29 15:07:05被管理员删除

#2

1. 中文的字符数小于65535个(至于为什么，参考Unicode)，所以创建一个char[65535] chs的数组
2. 读取文件使用BufferedReader按行读取 (有缓冲和无缓冲的读取对性能影响很大，毕竟电脑的瓶颈在IO)
3. 从读取到的行里取得每一个字符ch，然后chs[ch] += 1
4. 对数组排序。
5. 输出数组chs中非0的字符：即文件里的字符。

#3

确定是出现的“单词” 不是 “字符”？
如果是字符，按楼上解，

如果是单词的话 需要先建个字典表。 然后查词，这个算法有点复杂，你可以参考编译原理 的 词法分析器的实现算法。
另外 题目强调内存小于文本。那就不能一次全部读取文件，可以一行一行的读，或一次只读取一部分分字节

#4

额...
这个太复杂了，时间有限啊，2个小时3道题

#5

package test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class test1 {

public static void main(String[] args) throws IOException {
List<Map.Entry<Character, Integer>> mapList = null; 
File file = new File("d:\\a.txt");
FileReader fr = new FileReader(file);
BufferedReader read = null;
StringBuffer sbf = new StringBuffer();
try {
read = new BufferedReader(fr);
String tempString = null;
try {
while ((tempString = read.readLine()) != null) {
sbf.append(tempString);
}
System.out.println(sbf.toString());
mapList = tongji.tj(sbf);
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}finally{
read.close();
fr.close();
}


// 输出统计结果
for (Entry<Character, Integer> mapping : mapList) {
System.out.println(mapping.getKey() + ":" + mapping.getValue());
}
}
}

class tongji {
//统计
public static List<Map.Entry<Character, Integer>> tj(StringBuffer sb) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0, l = sb.length(); i < l; i++) {
char c = sb.charAt(i);
Integer v = map.get(c);
if (null == v) {
map.put(c, 1);
} else {
map.put(c, v + 1);
}
}

List<Map.Entry<Character, Integer>> mapList = new ArrayList<Map.Entry<Character, Integer>>(
map.entrySet());

Collections.sort(mapList,
new Comparator<Map.Entry<Character, Integer>>() {
public int compare(Map.Entry<Character, Integer> mapping1,
Map.Entry<Character, Integer> mapping2) {
return mapping1.getValue().compareTo(
mapping2.getValue());
}
});
return mapList;
}
}

#6

引用 3 楼 rainbowsix 的回复:

确定是出现的“单词” 不是 “字符”？
如果是字符，按楼上解，

如果是单词的话 需要先建个字典表。 然后查词，这个算法有点复杂，你可以参考编译原理 的 词法分析器的实现算法。
另外 题目强调内存小于文本。那就不能一次全部读取文件，可以一行一行的读，或一次只读取一部分分字节

单词是不可能的，中文分词技术不是个人能能力说做就能做好的，搜索引擎里中文分词技术是一大难点

#7

某业务部门根据需要提供多个文本如A、B、C 等等，且文件大小不一，每个文件都有多列，其中每个文件中的列都与我系统中的数据库中某表中的列对应（比如A文件中的列与表ta对应，B文件中的列与表tb对应），但是文件中的列于表中的列对应关系式无序的，设计一个通用程序，能统一处理各文件使其数据持久化到数据库对应表中并保证较高的处理效率，写出关键代码（不用完整代码），但是要写出设计思想（尽可能详细）和采用的主要技术方式以及程序处理过程中需要考虑的问题。

#8

有人能给点建议嘛？

#9

引用 4 楼 zdw1138453189 的回复:

额...
这个太复杂了，时间有限啊，2个小时3道题

晕，你不会是正在面试中吧

#10

引用 6 楼 Inhibitory 的回复:

Quote: 引用 3 楼 rainbowsix 的回复:

确定是出现的“单词” 不是 “字符”？
如果是字符，按楼上解，

如果是单词的话 需要先建个字典表。 然后查词，这个算法有点复杂，你可以参考编译原理 的 词法分析器的实现算法。
另外 题目强调内存小于文本。那就不能一次全部读取文件，可以一行一行的读，或一次只读取一部分分字节

单词是不可能的，中文分词技术不是个人能能力说做就能做好的，搜索引擎里中文分词技术是一大难点

是的，所以我很惊讶 为什么是“单词”

#11

新手路过，学习了。。。。

#12

呵呵,具体思路方向有了就差不多了,不用真全个具体的算法实现,在短时间里那不太可能...

#13

第二道题有建议嘛？