2、有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。
3、收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似
其实也很简单！
先说面，每面有四边，因此要建立4个句柄对应：上下左右，四个去面，就像双向链表节点有上下两面一样，然后面里有方块矩阵，2级的数组，加完数组写个方法函数，叫旋转,参数是行列号/旋向 ，旋向上下时行列号为行号，旋向左右时行列号为列号，意思是把某行某列往某方向旋转。
矩阵里有方块，方块有
创建六个面，按照魔方的样子，将第一面为正面，往下是底面（把第二面拿过来），底面往下是背面，背面往下联就是上面，上面往下是正面，现在回到正面，正面往左联就是左面，左面往左联就是后面，后面往左就是右面，右面往左是正面。。。。。。（这里不用罗索了，自己看明白了就知道怎么做了）
六个面创建完并上下左右连通后，这个程序就完成了
下面写下伪代码
类 方块{
颜色类型 颜色,
}
类 面{
(类型)面 上,
(类型)面 下,
(类型)面 左,
(类型)面 右,
(类型)数字 行列宽 = 3, //(3或者什么自己随便设)
(类型)方块 方块矩阵[行列宽][行列宽],
(类型)方块 旋进方块条[行列宽],
方法 旋转（(类型)数字 行列号 ,(类型)字符 璇向 ,(类型)方块 旋进方块条[行列宽])// (1:上 ,2:下,3:左,4:右))
返回
(类型)方块 旋出方块条[行列宽]
{
如果(旋向 == ("左" 或 "右")){
临时方块条 = 方块矩阵[行列号]，
如果(旋向 == "左"){
方块矩阵[行列号] = 旋进方块条,
}
如果(旋向 == "右"){
方块矩阵[行列号] = 旋进方块条,
}
}
否则如果(旋向 ==("上" 或 "下")){
临时方块条 = new 方块矩阵[行列宽],
循环((类型)数字 行列 = 1 到 行列宽){
临时方块条[行列] = 方块矩阵[行列][行列号],
方块矩阵[行列][行列号] = 旋进方块条[行列],
}
}
返回 临时方块条,
}
}
类 魔方{
(类型)面 方面[6],
创建方块()
返回 空
{
循环((类型)数字 方面号 = 1 到 6){
如果 (方面号 < 4){
方面[方面号].下 = 方面[方面号 + 1],
}否则如果 (方面号 < 5 ){
方面[方面号].左 = 方面[5],
方面[方面号]. 右 = 方面[6],
如果 (方面号 == 4 ){
方面[方面号].下 = 方面[1],
}
}否则如果 (方面号 <= 6){
方面[方面号].下 = 方面[2],
方面[方面号].上 = 方面[4],
}
}
}
方法 扭动魔方((类型)数字 面号,(类型)字符 方向,(类型)数字 行列号)
返回 空
{
(类型)字符 开始旋转面名 = 方面[面号]
(类型)面 临时面 = 方面[面号];
(类型)方块 临时方块条[行列宽];
如果(方向 == "上"){
循环((类型)数字 = 1 到 4){
临时方块条 = 临时面.旋转( 方向, 行列号,临时方块条),
临时面 = 临时面 的 上,
}
}
如果(方向 == "下"){
循环((类型)数字 = 1 到 4){
临时方块条 = 临时面.旋转( 方向, 行列号,临时方块条),
临时面 = 临时面.下,
}
}
如果(方向 == "左"){
循环((类型)数字 = 1 到 4){
临时方块条 = 临时面.旋转( 方向, 行列号,临时方块条),
临时面 = 临时面.左,
}
}
如果(方向 == "右"){
循环((类型)数字 = 1 到 4){
临时方块条 = 临时面.旋转( 方向, 行列号,临时方块条),
临时面 = 临时面.右,
}
}
}
}
其次,对每条短信的第i(i从0到70)个字母按ASCII码进行分组,其实也就是创建树.i是树的深度,也是短信第i个字母.
//树结点定义
struct TNode
{
BYTE* pText;//直接指向文件映射的内存地址,使用BYTE而不用char是为符号问题
DWORD dwCount;//计算器,记录此结点的相同短信数
TNode* ChildNodes[256]; //子结点数据,由于一个字母的ASCII值不可能超过256,所以子结点也不可能超过256
TNode()
{
//初始化成员
}
~TNode()
{
//释放资源
}
};
//BYTE* pText直接指向文件映射的内存地址,使用BYTE而不用char是为符号问题
//int nIndex是字母下标
void CreateChildNode(TNode* pNode, const BYTE* pText, int nIndex)
{
if(pNode->ChildNodes[pText[nIndex]] == NULL)
{//如果不存在此子结点,就创建.TNode构造函数应该有初始化代码
//为了处理方便,这里也可以在创建的同时把此结点加到一个数组中.
pNode->ChildNodes[pText[nIndex]] = new TNode;
}
if(pText[nIndex+1] == '/0')
{//此短信已完成,记数器加1,并保存此短信内容
pNode->ChildNodes[pText[nIndex]]->dwCount++;
pNode->ChildNodes[pText[nIndex]]->pText = pText;
}
else //if(pText[nIndex] != '/0')
{//如果还未结束,就创建下一级结点
CreateNode(pNode->ChildNodes[pText[nIndex]], pText, nIndex+1);
}
}
//创建根结点,pTexts是短信数组,dwCount是短信数量(这里是一千万)
void CreateRootNode(const BYTE** pTexts, DWORD dwCount)
{
TNode RootNode;
for(DWORD dwIndex=0;dwIndex <dwCount;dwIndex++)
{
CreateNode(&RootNode, pTexts[dwIndex], 0);
}
//所有结点按dwCount的值进行排序
//代码略...
//取前10个结点,显示结果
//代码略...
}
这样处理看起来很复杂,其实就是为了减少比较次数.我认为大家看了这小段代码应该可以明白我的意思了,其它的不多说了.
最后,就是对这些结点按dwCount的值进行排序,取前面的前10个结点就可以了.
我认为这问题只要是解决两方面的内容,一是内容加载,二是短信内容比较.采用文件内存映射技术可以解决内容加载的性能问题(不仅仅不需要调用文件I/O函数,而且也不需要每读出一条短信都要分配一小块内存),而使用树技术可以有效减少比较的次数.当然基本思路是这样,如果有心情还可以在这基础上做一些优化处理,效果一定不会差的.