百度在线笔试的答案

1， 一个文本文件有多行，每行为一个URL。请编写代码，统计出URL中的文件名及出现次数。
a） 文件名不包括域名、路径和URL参数，例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。
b） 部分URL可能没有文件名，例如http://www.abc.com/，这类统计为“空文件名”。
c） 出现在不同URL中的相同文件名视为同一文件名，例如http://www.ceshi.com/hi.php
和ftp://ftp.cdef.com/hi.php为同一文件名

文件内容示例如下：
http://www.test.com/abc/de/fg.php?id=1&url=http://www.test.com/index.html
http://www.ceshi.com/hi.jsp
ftp://ftp.ceshi.com/hi.jsp
http://www.hello.com/cw/hi.jsp?k=8
http://www.hi.com/jk/l.html?id=1&s=a.html
http://www.rs.com/n.op/q/rs?id=1
http://www.abc.com/


2，一个简单的论坛系统，以数据库储存如下数据：
用户名，email，主页，电话，联系地址，发帖标题，发帖内容，回复标题，回复内容。
每天论坛访问量300万左右，更新帖子10万左右。
请给出数据库表结构设计，并结合范式简要说明设计思路。


3，现有两个文件，
a）数据文件A，格式为：关键词、IP地址、时间，记录条数为1000万左右，该文件是无序排列的。
b）数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。（至少要给出关键算法和设计思路）

呵呵 发现在csdn有篇帖子上引用了我的这个.所以丢着这个成年没写完的东西是在是丢人.我还是把这个答案写完吧.给大家一点提示

1.此处主要是考核对正则的操作能力.其实无论用什么语言.这个用正则是最好的.所以我当时认为这个是最简单的.可以说你只要写出正则表达式即可.我写得是"|\/([^/]*?[^\?\/]{0,4})(\?.*?){0,}$|i"这个正则描述是php.

以下为java代码(嘿嘿...毕竟java才是偶地擅长)

/**
*
*/
package javaText.test;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;


/**
* @author Administrator
*
*/
public class Test {

/**
* @param args
* @throws FileNotFoundException
*/
private final static String UrlPattern = "/([^/]*?[^\\?/]{0,4})(\\?.*?){0,}$";
public static void main(String[] args) throws Exception {
String a = "d:/a.txt";
StringBuffer strbuff = new StringBuffer();
byte[] temp = new byte[1024];

try {
FileInputStream stream = new FileInputStream(new File(a));
while(stream.read(temp)!=-1){
strbuff.append(new String(temp));
temp = new byte[1024];
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

List list = getMatchList(UrlPattern,strbuff.toString().trim());
Map count = new Hashtable();
for(String tempString :list){
if(tempString!=null)
tempString = tempString.trim();

if(count.get(tempString)==null){
count.put(tempString, 1);
}else{
int i = count.get(tempString).intValue();
count.put(tempString, ++i);
}
}
System.out.println(count);
}
public static List getMatchList(String pattern,String PatternTarget) {
Pattern p = Pattern.compile(pattern,Pattern.CASE_INSENSITIVE|Pattern.MULTILINE);
Matcher m = p.matcher(PatternTarget);
List list = new ArrayList();
while (m.find()){
list.add(m.group(1));
}
return list;
}
}
}

2.此题主要是考核web设计中面临数据量较大的表设计
我以mysql为例来设计表(呵呵,最近用得最多)
用户名(username)，email(mail)，主页(homepage)，电话(tel)，联系地址(address)，发帖标题(title)，发帖内容(context)，(回复标题()，回复内容)实际上是对应于发帖的。
由于数据并发量较大.所以表需要尽可能的减少表查询量.我的设计如下

user表
create table usertable{
id int(11) auto_increment,
username varchar(255),
mail varchar(255),
homepage varchar(255),
tel varchar(255),
address varchar(255),
primary key(id),key(username)
}
alter table usertable add index id_idex(id);//给id建立索引
alter table usertable add index username_idex(username);//给id建立索引

帖子表.其中的用户信息是和user表的用户信息同步.这样保证了查询表的次数
create table posttext{
id int(11) auto_increment,
title varchar(255) not null,
context text ,
user_id int(11),
username varchar(255),//此处需要加入页面显示的基本信息.这样每个帖子的查询就只需要涉及一个表的操作
mail varchar(255),
homepage varchar(255),
is_topic enum(1,0) default 0,
primary key(id)
}
alter table posttext add index id_idex(id);//给帖子id建立索引
alter table posttext add index id_idex(user_id);//给用户表id建立索引


3，现有两个文件，
a）数据文件A，格式为：关键词、IP地址、时间，记录条数为1000万左右，该文件是无序排列的。
b）数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。
请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。（至少要给出关键算法和设计思路）

这个程序主要考察的是大容量数据的查询 以及操作..
一般的机器100万的数据打开就很吃力了.何况1000万

如果是我选用的话.那么1000万肯定是做为分段取的一种.
首先肯定会用shell的split拆分它.我觉得拆分为10w一段的去取即可

另外100万的那个文件应该分拆为多个索引数据.
可以采用id分段.比如1-1w分为一个区间段.分拆为100个文件.每个文件保存相对应区间的id记录.这样就可以大大减少查询量 和读入空间.
这类操作最好是采用shell 写因为shell的数据追加比较好..利用awk和sed进行数据操作..嗯~~得查参考书了..shell虽然好用.但是麻烦..


思路(shell和perl都是翻书做,那东西太麻烦了,我基本上是今天写明天忘.写思路好了)

索引文件建立
确认区间段1w一个
这样的话1-100w 分别是1...100w
这个就容易多了.当作文本处理.文本长度为多少位.根据最大位做判断.如果是1 则判断其他位.(好像还是不完美....) 理论上来说 应该有数学方法可以判断得更加完美.可惜..回头再查查

split -10000 ./file //这个写的时候有待商酌，因为文件比较大.会不会太慢.如果慢的话.用more带参数循环处理好了,反正文件的行数大致能知道.那么就有点不太完美...
awk 截取出$1 进行判断.根据判断 取对应的文件循环我们的索引文件.得出结果返回.
累加到新文件