【100题】第四十四题 腾讯面试三道题

一，设计一个魔方（六面）的程序。 P194

思路：魔方总数9 + 9 + 8 = 26

魔方有六个面，需要定义六个结构体，内容为一个9个点和一个编号，其中每个点包含一个颜色标识；在魔方展开图中根据正方形的相邻关系编号，每个正方形都有四个函数：左翻、右翻、上翻、下翻

根据相邻关系，每个操作都会引起相邻面的相关操作；

比如一个面的左翻会调用右边相邻面的左翻；也就意味着左相邻面的0、1、2三个元素与当前面互换；递归下去，直到所有面都交换完毕；

二，有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。

思路1：

先处理每条短信的得到hash值，然后将其读入map容器中。

Map<hash值，个数>这样可以得到每条短信对应的重复个数。

接下来用O(n)的时间就可以找到做多的前10条

思路2：

首先我们将文本导入数据库，使用Having子句来实现这样的功能,我们利用如下语句
select count(*) ccount

from table
group by messageString having count(*)>1
order by ccount desc
这样得到的第一个记录就是出现重复次数最多的那组数字。

三，收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）

最复杂方法：O(nlogn)

将该条插入，然后按照字符排序，则其上，或者其下一条最相似

改进：O(n)

挨个比较，则得到最为相似的

再改进：用数据库的正则表达式