推荐|腾讯面试题

1、设计一个魔方（六面）的程序。
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){
临时方块条 = 临时面.旋转( 方向, 行列号,临时方块条),
临时面 = 临时面.右,
}
}
}
}

-------------------------------------------------------------------------------------------------------------

首先,一千万条短信按现在的短信长度将不会超过700M(平均情况下应该是350M),使用内存映射文件比较合适.可以一次映射(当然如果更大的数据量的话,可以采用分段映射),由于不需要频繁使用文件I/O和频繁分配小内存,这将大大提高了数据的加载速度.
其次,对每条短信的第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 {
CreateNode(&RootNode, pTexts[dwIndex], 0);
}
//所有结点按dwCount的值进行排序
//代码略...

//取前10个结点,显示结果
//代码略...

}

这样处理看起来很复杂,其实就是为了减少比较次数.我认为大家看了这小段代码应该可以明白我的意思了,其它的不多说了.
最后,就是对这些结点按dwCount的值进行排序,取前面的前10个结点就可以了.

我认为这问题只要是解决两方面的内容,一是内容加载,二是短信内容比较.采用文件内存映射技术可以解决内容加载的性能问题(不仅仅不需要调用文件I/O函数,而且也不需要每读出一条短信都要分配一小块内存),而使用树技术可以有效减少比较的次数.当然基本思路是这样,如果有心情还可以在这基础上做一些优化处理,效果一定不会差的.

评论记录：