试题集之一

liwanchun_xd

浏览: 123534 次
来自: ...

最近访客更多访客>>

cty136

402230366

Dreamall

1927105

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (55)

社区版块

存档分类

百度 PHP BBS 数据结构算法

一、一个文本文件有多行，每行为一个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之间(与关键词集合有关)，因此本方法完全可行。

分享到：