一、 一个文本文件有多行,每行为一个URL。请编写代码,统计出URL中的文件名及出现次数。
a) 文件名不包括域名、路径和URL参数,例如http://www.ourday.cn/bbs/forumdisplay.php?fid=18中的文件名是forumdisplay。
b) 部分URL可能没有文件名,例如http://www.ourday.cn/,这类统计为“空文件名”。
c) 出现在不同URL中的相同文件名视为同一文件名,例如http://www.ourday.cn/index.php和ftp://ftp.ourday.cn/index.php为同一文件名
文件内容示例如下:
http://www.ourday.cn/bbs/redirect.php?tid=480&goto=lastpost#lastpost
http://www.ourday.cn/index.php
ftp://ftp.ourday.cn/index.php
http://www.ourday.cn/bbs/index.php?k=8
http://www.ourday.cn/bbs/forumdisplay.php?fid=16
http://www.ourday.cn/bbs/viewthread.php?tid=444&extra=page%3D1
http://www.ourday.cn/
http://www.ourday.com.cn/
以上url地址经修改,不影响试题内容。
二、 一个简单的论坛系统,以数据库储存如下数据:
用户名,email,主页,电话,联系地址,发帖标题,发帖内容,回复标题,回复内容。
每天论坛访问量300万左右,更新帖子10万左右。
请给出数据库表结构设计,并结合范式简要说明设计思路。
三、 现有两个文件,
a)数据文件A,格式为:关键词、IP地址、时间,记录条数为1000万左右,该文件是无序排列的。
b)数据文件B是关键词ID到关键词的对应表文件,格式为:ID、关键词,记录条数在100万左右,也是无序排列的。该对应表中的记录是一一对应的,不存在ID或者关键词重复的情况。
要求将数据文件A对应的关键词替换为B中的ID,生成新的数据文件C,数据文件C的格式为:关键词ID、IP地址、时间。
请设计一个程序,实现上述功能,并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G,硬盘足够大。(至少要给出关键算法和设计思路)
以下是该题的java实现,代码如下:
import java.net.*;
import java.io.*;
import java.util.*;
/** * @author tzy * 在j2sdk1.4.2下测试通过 */
public class FileNameStat{
private String srcPath;//要统计的文件路径
private Map statMap;//用于统计的map
public FileNameStat(String srcPath)
{
this.srcPath=srcPath;
statMap=new TreeMap();
}
/*获得要统计的URL的文件名*/
public String getFileName(String urlString)
{
URL url=null;
String filePath=null;
String fileName=null;
try
{
url=new URL(urlString);
filePath=url.getPath();
int index=0;
if ((index=filePath.lastIndexOf(\"/\"))!=-1)
{
fileName=filePath.substring(index+1);
}
else
{
fileName=\"\";
}
}
catch(MalformedURLException e)
{
}
return fileName;
}
/*统计指定文件名的个数*/
public void stat(String filename)
{
Integer count=null;
if(statMap.get(filename)!=null)
{
count=(Integer)statMap.get(filename);
count=new Integer(count.intValue()+1);
}
else
{
count=new Integer(1);
}
statMap.put(filename,count);
}
/*统计的主方法*/
public void start() throws FileNotFoundException,IOException
{
BufferedReader bfin=new BufferedReader(new FileReader(this.srcPath));
String temp=null;
while((temp=bfin.readLine())!=null)
{
stat(getFileName(temp));
}
}
/*输出统计结果*/
public void result()
{
Iterator it=statMap.entrySet().iterator();
while(it.hasNext())
{
Map.Entry entry=(Map.Entry)(it.next());
System.out.println((entry.getKey().equals(\"\")?\"空文件名\":entry.getKey()) + \"的个数是\" + entry.getValue());
}
}
public static void main(String[] args) throws Exception
{
FileNameStat fns=new FileNameStat(\"src.txt\");//指定成待统计文件
fns.start();
fns.result();
}
}
第二题
简评:
这道题也与百度的业务有关,百度现在除了搜索外,还有贴吧,知道,博客等重要产品。 同时也在积极的探索社区化,包括前不久宣布进军电子商务领域,搜索之外的这些产品,其主要功能的实现主要是对数据库的操作。 因此,想进入百度,也需要对数据库有一定的认识。 实现思路及数据库设计: 1,该论坛主要有两个实体对象,用户和帖子;对于帖子对象,有一个问题:回复的帖子是否应该跟主题帖子存放在同一个表里?
考虑到每天更新10万帖子,说明帖子数比较多,为了方便主题的呈现,我一般都把主题贴和回帖分别放在不同的表中,把主题贴和回帖分开可以提高查询效率(300万的访问量每天)。
2,按照1中的思路,该论坛由两个对象(用户和帖子)变成三个实体对象,分别是用户,主题帖子,回复帖子;
3,上述三个对象存在三个关系,分别是:
用户--主题帖,一个用户可以发0个或多个帖子,一个帖子对应一个用户(一对多关系),
主题帖--回复帖:一个主题有0个或多个回复帖子,一个回复帖子对应一个主题(一对多关系);
用户--回复贴:一个用户可以回0个或多个帖,一个帖子对应一个用户(一对多关系)。
还存在对回复贴的回复,这个考虑用fatherId来表示。
4,由于三个关系 “用户--主题帖,主题帖--回复帖,用户--回复贴” 都是一对多关系,根据表设计一般原则,可以将这两个关系独立建立表,也可以不另外建表而将一对多的关系体现在实体表中;然而,表间的连接查询是非常耗资源的,所以应尽量减少表间连接,那么对三个关系不应该分别建表,而是把用户的id作为主题表和回帖表的外键,把主题贴id作为回帖表的外键。
5,鉴于以上考虑,该论坛的三个表如下所示
表名:t_user_info (用户信息表)
字段名 类型 缺省值 中文含义 约束 备注
id Int 用户编号 PRI Auto_increment
Name Varchar(30) 用户名
Email Varchar(50)
Phone Varchar(30)
Addr Varchar(200)
其他字段略,根据需要添加 表名:main_content_info (主题帖信息表)
字段名 类型 缺省值 中文含义 约束 备注
id Int 贴编号 PRI Auto_increment
Title Varchar(200) 发帖标题
Content Text 发帖内容
UserID Int 用户编号 外键
其他字段略,根据需要添加
表名:sub_content_info (回复贴信息表)
字段名 类型 缺省值 中文含义 约束 备注
id Int 贴编号 PRI Auto_increment
Title Varchar(200) 发帖标题
Content Text 发帖内容
UserID Int 用户编号 外键
FatherID Int 父编号
MainID Int 主题帖编号 外键
其他字段略,根据需要添加
6,符合范式分析:
上述表中每个字段不可再分,首先满足1NF;
然后数据库表中的每个实例或行都是可以被惟一地区分(id),不存在部分依赖,因此满足2NF;
t_user_info (用户信息表)和main_content_info (主题帖信息表)不存在任何传递依赖,至少属于BCNF;
但是sub_content_info (回复贴信息表)不满足3NF,因为存在如下传递依赖:id-->FatherID,FatherID-->MainID。
范式并不是越高越好,sub_content_info表只满足2NF却更有效率,也是当今论坛较主流的设计。
第三题
简评:
如何对海量数据进行快速检索,这是搜索引擎的必需考虑的问题。这又涉及到数据结构和算法。 因此,要想进入百度,就必须熟悉一些基本的算法和数据结构。 思路及解决方案如下:
1: 设计用TRIE树实现关键词到其对应id的快速词典查找
TRIE树的每一个节点为一个包含256个元素的数组,同时指针指向其下一级节点
节点定义如下:
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL,说明从跟节点到当前节点的路径构成文件B中的一个关键词,
在其节点的id保存该关键词的id;如果指针不为NULL,则id对应为0或者一个无穷大的整数,标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组,即对于汉字等双字节字符视为两个无符号char型整数,
每个元素的取值范围在0到255之间。
2:生成文件b的TRIE树
步骤1:依次读取文件b的每一行,对每一行执行步骤2到步骤5
步骤2:读取关键词id和关键词,令为key
步骤3:依次读取key的每一个字符,对每一个字符,执行步骤4;
步骤4:如果该字符对应的指针为NULL,则创建其儿子节点;
步骤5:为当前节点的对应字符id置为关键词id
3:根据A文件生成C文件
步骤1:依次读取文件A的每一行,对每一行执行步骤2到步骤5
步骤2:分别获取当前行关键词、ip地址和时间
步骤3:令关键词key=c1c2...cm,对c1到cm每个字符,执行步骤4
步骤4:获取根节点的第c1个元素指针,转移到节点node1,
根据node1的第c2个元素指针,转移到node2...
根据nodem的第cm个元素,获取关键词的id
步骤5:往文件c中写入一行数据,格式为关键词的id、ip地址和时间
4:复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m),其中n为文件b行数,m为文件b关键词的最大长度。TRIE的空间复杂度为O(n*m),n和m含义同上,但由于实际应用中关键词之间可能会有很多前缀相同现象,所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m),n为文件a行数,m为文件a关键词的最大长度,因为有了TRIE树之后,给定一个关键词获得其id的时间复杂度为关键词长度。生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间,空间复杂度为O(1),由于系统有1G的可用内存,TRIE占用的空间在几十兆到200M之间(与关键词集合有关),因此本方法完全可行。
分享到:
相关推荐
蓝桥杯官网系统试题集部分
硬件工程师面试试题集,都有答案,推荐下载阅读! 1、下面是一些基本的数字电路知识问题,请简要回答之。 (1) 什么是Setup 和Hold 时间? 答:Setup/Hold Time 用于测试芯片对输入信号和时钟信号之间的时间要求。 ...
硬件工程师面试试题集,都有答案,推荐下载阅读! 1、下面是一些基本的数字电路知识问题,请简要回答之。 (1) 什么是Setup 和Hold 时间? 答:Setup/Hold Time 用于测试芯片对输入信号和时钟信号之间的时间要求...
湖南大学ACM网试题全集(2) 花了一整天的时间做好的哦...
专业技术人员继续教育之心理健康与心理调适-试题合集一(有答案).pdf
这是我从各大院校的ACM群中搜集来的资料之一
这是一份有管计算机省级考试的习题集,里面包含的内容很完整,希望能给大家带来方便! 一、 单项选择题 下列各题A)、B)、C)、D)四个选项中,只有一个选项是正确的,请选择之。 (一)计算机基础知识 【1】...
Java程序员面试的试题集(1---122) 、面向对象的特征有哪些方面 (1)抽象: 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一...
● 小王购买了一个“海之久”牌活动硬盘,而且该活动硬盘还包含有一项实用新型专利,那么,小王享有(11) 。 (11)A.“海之久”商标专用权 B.该盘的所有权 C.该盘的实用新型专利权 D.前三项权利之全部
本试题集包含多个大题,覆盖了计算机组成原理的各个方面,例如存储器层次结构、指令集架构、流水线设计、多处理器系统等。 特点: 全面性:本试题集涵盖了计算机组成原理课程学习的各个方面,包括存储器层次结构、...
欧美最新500强企业人才测评试题与答案-11页 人才测评 人力资源管理能力的测评 人力资源精品课程《人才测评学》全书 世界第一智商俱乐部-智商测评标准 55页 世界第一智商俱乐部智商测评标准 天际华宇集团招聘选拔测试...
为准备十一届蓝桥杯省赛,我历经千辛万苦收集了部分历年的省赛真题。该试题集供南昌大学以及其他高等院校的同学下载使用,不收取任何积分!
《日语商务函电》之お礼状の书き方.ppt 另类日本史.pdf 听日本NHK新闻必备日语词语_经济篇2010-07-09.doc 商务日语邮件写作.doc 外贸用语.doc 外贸用语2.docx 当代日本语会话(高级下册).pdf 敬语 日本の歴史1.doc ...
式的约定,称之为( ) A. OSI参考模型 B.网络操作系统 C.通信协议 D.网络通信软件 3.衡量网络上数据传输速率的单位是每秒传送多少个二进制位,记为( ) A.BPS B.OSI C.MODEM D.TCP/IP 4.局域网常用的基本拓扑...
DNS服务器和客户机设置完毕后,有三个命令可以测试其设置是否正确,下面( )不是其中之一。 A. PING B. LOGIN C. IPCONFIG D. NSLOOKUP 2. 计算机网络中可以共享的资源包括 ( )。 A. 硬件. 软件. 数据. 通信信道...
1.设 1.设 5.设 为一个有限字母表, 上所有字(包括空字)之集记为 6.设 G 是一个 ( 7.若 G 是一个 8.设 1.设G 是一个恰有两个不邻接的奇
DNS服务器和客户机设置完毕后,有三个命令可以测试其设置是否正确,下面( )不是其中之一。 A. PING B. LOGIN C. IPCONFIG D. NSLOOKUP 2. 计算机网络中可以共享的资源包括 ( )。 A. 硬件. 软件. 数据. 通信...
6. 二零一春季试题 39 6.1. 39 6.1.1. 讨论集中式数据库和分布式数据库各自的优缺点。 39 6.1.2. 讨论在局域网和广域网两种情况下分布库设计的区别。 39 6.1.3. 解释分片透明性、复制透明性和位置透明性等三级透明性...
2009年全国物流师统考试题2009年全国物流师统考试题级答案(主观题部分) (第一部分) 一、判断题:(每题0.5分,共20分)正确划A,错误划B。 1.构成物流服务的子系统功能之间存在着约束关系。 2.在物流...
动态调度算法之一:记分牌 4.2.3 动态调度算法之二:Tomasulo算法 4.3 控制相关的动态解决技术 4.3.1 减少分支延迟:分支预测缓冲技术 4.3.2 进一步减少分支延迟:分支目标缓冲 4.3.3 基于硬件的推断...