郁闷..下午收到了百度的拒信，大家帮我分析分析原因
我们很遗憾的通知您，您未在指定的时间内答题，或未能通过我们的笔试(Java软件工程师)。您的简历和笔试记录将被转入您所申请的备选职位，并进入百度人才库保存。
百度 人力资源部
==========================================================
题目居然跟这个一模一样，早知道先搜着看看了。虽然事先有协议，但这不能算我发的吧
http://hi.baidu.com/termite/blog/item/67f652c2b33c9434e4dd3b62.html
不知道百度怎么阅卷的，我觉得做得还可以的，唉，谁帮我看看为什么没通过..
是不是编程题应该调试一下再发的？我写好了直接发的，今天调试了一下还发现了几个错误，后悔当初没直接在IDE里写。
1、保存URL的文件为C:\url.txt
//假设文件记录数量不是非常大（1万条之内）
代码如下：
import java.io.*;
void readfile()
{
String line = " ";
FileReader fr = new FileReader(c:\url.txt);
BufferedReader br = new BufferedReader(fr);
ArrayList filelist = new ArrayList();
try
{
line = br.readLine();
while(line!=null)
{
String tempStr = line;
urlFile= " ";
if(tempStr.contains( '? '))//带有参数
{
tempStr = tempStr.substring(0,tempStr.indexOf( "? ")-1) //将？后面的字符串去掉
urlFile = tempStr.substring(tempStr.lastIndexOf( "/ ")+1);
}
else
if(tempStr.lastIndexOf( "/ ")==tempStr.length-1)//以域名结尾无文件名，”/“在URL最后
{
urlFile = "空文件名 ";
line = br.readLine(); //读下一行
continue;
}
else //不带参数且不是域名
{
urlFile = tempStr.substring(tempStr.lastIndexOf( "/ ")+1);
}
///////////以下进行数量记录////////////////////////
int position = filelist.indexOf(urlFile); //查找是否有相同的文件名
int count = 0;
if(position==-1) //没有相同的文件名
{
filelist.add(urlFile); //增加文件名
count = 1;
filelist.add(count); //增加数量
}
else //有相同的文件名
{
count = filelist.get(position);
count++;
filelist.set(position,count); //数量加1
}
}
resultPrint(filelist); //结果输出
}
catch(FileNotFoundException e)
{
system.out.println( "file not found! ");
}
}
void resultPrint(ArrayList al)
{
for(int i = 0; i <al.size();i++)
{
system.out.println(al.get(i).toString); //结果打印
}
}
2、设计三个数据表：userInfo,userTitle,userReplyTitle;结构如下：
userInfo: userName,email,homePage,phone,address. 存储用户基本信息
userTitle: userName,title,context. 存储发帖信息
userReplyTitle: userName,rtitle,rcontext. 存储回复信息
分析：首先userName与其他数据项都有联系，
其次（title,context）（email,homePage,phone,address）（rtitle,rcontext）这三组数据互相没有联系。
分成三个表不会造成传递依赖，三个表以userName连接查找。这样的设计是符合第三范式的。
3、设计思路：考虑先将数据文件B进行内排序，再对A替换关键词后生成新的文件C。
基本算法：
1、读文件B到内存中（ID和关键词的大小*100万 < 1G），可以用数组B保存。
2、根据关键词的Unicode码进行排序（假设数据文件的编码为unicode码），采用快速排序算法。
3、读数据文件A的一条记录，跟据关键词在排好序的数组B中查找ID（二分查找），
4、替换这条记录的关键词为ID。
5、追加到数据文件C中。
6、重复步骤3，直至读完文件A。
空间复杂度：主要是读文件B所占用的空间。
时间复杂度：快速排序的复杂度为O（log2 n）、二分查找为O（log n）和读取文件A的I/O操作时间。
其他时间基本可以忽略。
[解决办法]
感觉userTitle与userReplyTitle应该通过titleId关联
[解决办法]
第一题感觉放到HashMap处理起来更方便速度更快。
[解决办法]
第三题还有种方式将文件B放到hashmap中，相比数组排序处理，排序时只是调整引用的指向而不是交换数据内容。
100万的记录测试了下大概占用200M空间，插入时间入10秒，取1万条的时间为0.7秒，不考虑文件A的读取时间，排序查找时间为700多秒，应该还是比较快的。
[解决办法]
不过一般在笔试中能做到楼主这样已经不错了，不知楼主那天有没面试？如果没有只能说百度要求有些高（现在进去期权也没了）。
[解决办法]
第一题是想考你正则表达式的能力，所以第一题上你没有合格。
第二题你的论述没有涉及到性能，人家已经写了访问量什么的，肯定想要你写性能方面的东西。
第三个么，你说的不详细，由于内存只有1G，空间有限，需要多次读取数据用来存储，另外，快速排序是很消耗内存的事情，你也没有提及，人家可能觉得你算法上还是有欠缺。
总之，我的观点是小细节上没有注意好，baidu是一个大公司，可能会注重这些小细节，毕竟写代码很多人都会，但是这些小细节上的功底，就不是一天两天练成的了。
我只是就事论事，希望搂主不要生气哈。
[解决办法]
把广告放在别人贴子里，这么不尊重人还希望别人访问吗？
[解决办法]
第一题看出来了 是要考你正则表达式，可惜你。。。。。
后面两道没看出是什么意图
[解决办法]
感觉上第一题，只要用正则匹配首个\\\\[^(\\\\|?)+]?
取中间就可以了，不知我说得对么？
[解决办法]
是不是算发不是最优算法
[解决办法]
我也觉得楼主很不错了,你一定要更强啊.以后多教教小弟啊.
[解决办法]
已经不错了，不要放弃
[解决办法]
第一道题，用正则表达式+TreeMap
第三道题，用散列表。前提是要设计一个好的散列函数。
[解决办法]
感觉第一题应该是你没有调试 还有错误 就提交 有问题，至于正则的话倒是次要的，题目要求不是很复杂，用了正则的话执行速度可能还是会慢些。baidu应该会更看重效率的
第三题的应该可以对文件b生成hash，然后就好处理了，对类似的大容量数据hash很常用的
[解决办法]
第二道题，用户和发贴是一对多的，帖子和回复又是一对多的。
还有，最好表的内键和外键不要和数据参合在一块儿，各单独建个ID字段就可以了。
[解决办法]
第2题暴露了你没有设计大流量论坛系统底层的经验，首先是表结构问题，其实是关系的效率问题，用userName这种char类型字段来关联table会让你种设计慢如虫爬。
考虑这样：
userInfo: userId,userName,email,homePage,phone,address. 存储用户基本信息
userTitle: titleID,userId,userName,title,context,isTopic. 存储发帖/回帖信息,主题帖的isTopic为NULL,回帖的isTopic为主题帖ID
为什么不把userName做为关联内容，而要在userTitle表中也放一个userName呢，因这样可以令读取帖子列表及帖子内容时只读userTitle表而不用inner join，只有点击查看用户资料时才取userInfo表。效率第一，牺牲几个字节存放userName，是可以的吧
[解决办法]
为什么不把userName做为关联内容，而要在userTitle表中也放一个userName呢，因这样可以令读取帖子列表及帖子内容时只读userTitle表而不用inner join，只有点击查看用户资料时才取userInfo表。效率第一，牺牲几个字节存放userName，是可以的吧
=========================================================
万一发贴后人家改名了呢？还得去更新所有他发过的帖子，抑或显示错误的名字？
[解决办法]
第三题应该是考怎样对B结构化处理。关键字是非结构化数据，设计一个HASH函数，将关键字映射到一个值上（认为DWORD比较合适），以该值为索引结构化B，使用有序二叉树存储（方便查找），利用HASH table处理冲突。替换A就比较简单，就是根据关键字查找对应ID，复杂度应该是O(m*logn)，结构化B复杂度为O（n*logn），空间复杂度为 (len(keyword)+len(ID))*n,取决于ID长度。如果ID长度在100位以内，则内存占用可控制在100M以内。
设计一个冲突少HASH函数是提高效率的关键
[解决办法]
如果关键ID全部由数字组成的话还可以将其转化为数值形式存储，进一步压缩存储空间，这样内存占用率可以降到十几M大小
[解决办法]
为什么不把userName做为关联内容，而要在userTitle表中也放一个userName呢，因这样可以令读取帖子列表及帖子内容时只读userTitle表而不用inner join，只有点击查看用户资料时才取userInfo表。效率第一，牺牲几个字节存放userName，是可以的吧
=========================================================
万一发贴后人家改名了呢？还得去更新所有他发过的帖子，抑或显示错误的名字？
=============================================================================
在一定的时间，都需要对数据库进行维护，在这个时候进行改名
[解决办法]
第三题可用位示图解决
[解决办法]
呵呵 大的公司看中的是算法 效率
而不是仅仅的一个code
空间换时间 时间换空间 特定的时候特定的选择
Baidu的出题还是考虑的比较好 很喜欢这种出题方式
如果是ACM的队员 我想应该能够做的很好
[解决办法]
第一道题，不一定是要考正折表达式的，因为他慢。
第二道题的表结构都设计的不合理
首先发帖、发帖回复的回复其实是一类的东西，不应该分表，帖子内容和标题等的摘要信息不应该放到一个表中，
第三道题、说实话，太高深，不会。
[解决办法]
http://blog.csdn.net/hy_lihuan/archive/2007/05/08/1600034.aspx
这个是我对第二道题目的详细分析，不知道是否对错，有错误请提出
[解决办法]
我觉得第一题还是考正则式，因为虽然正则式慢一点，但是这题并没有性能要求啊。而后面两题都写了性能方面的东西，所以肯定后面两题要你重点注意性能。
[解决办法]
为什么不把userName做为关联内容，而要在userTitle表中也放一个userName呢，因这样可以令读取帖子列表及帖子内容时只读userTitle表而不用inner join，只有点击查看用户资料时才取userInfo表。效率第一，牺牲几个字节存放userName，是可以的吧
=========================================================
万一发贴后人家改名了呢？还得去更新所有他发过的帖子，抑或显示错误的名字？
=============================================================================
在一定的时间，都需要对数据库进行维护，在这个时候进行改名
===================
这种设计是现实的。
关于改名的问题，这个频率较低，可以说非常低。。。 如果数据库支持触发器的话，建议用这个
[解决办法]
表结构同意litcat(里子)，补充一点：
如果考虑性能等因素还应设计历史信息表，定期将一个月前的帖子信息导入历史表，毕竟这部分帖子访问量较小。
另外，提出改名问题的网友，应该回头看看数据库教材，特别是关于外键的部分。
