请教两道面试题

如果不hash我确实想不出还有什么比hash好

能用数据库吗？

数据库能快吗?即使是b-tree，也要在磁盘上进行io操作，至少读几次，写1次，还不算其他的性能损失。

    谁说在这个快餐文化横行的社会里钻研技术、刻苦求索之风已泯！能为一个基础技术问题争的面红耳赤，看的实在让人深受鼓舞啊。

    我也发表点拙见，和诸位一起讨论下吧。

    争论的焦点集中在“下一站，火星”同志和“bcccs”同志提出的两种算法之间。先说说“下一站，火星”同志的算法：在最坏的情况下（前9999999条数据不重复，最坏一条和前面的有重复）这样复杂度大概是n2。而“bcccs”同志的算法的复杂度是和信息的平均长度有关的（每次hash并切去key之后如果同时有多条信息“到头了”才能确定这些条信息是重复的）。

    我想可以在“bcccs”同志的算法按“两个字母”为每次的key的基础上改进一下。每次hash的key选取可以按不同的选择方法：

    第一次：以第一个字母、最后一个字母、和字符串长度为key对整个文件分组（string底层是char数组的实现求长度的速度很快）。原因是短信息的开头常常是：hello、dear ....、hi等固定问候语，而后边的内容却千差万别，只用开头字母分组意义不大。还有就是加入信息长度做key应该是有易的，这样一方面减少了后续步骤中每组中字符串长度不同带来的麻烦，而且两条不同内容短信首尾字母相同且长度相同的概率比较小，所以会出现大量的只有一条信息的分组可直接舍弃不予考虑（如果按bcccs同志的方法第一次分组后几乎不可能出现一条记录的分组）。

   第二次：第一次分组后去掉只有一条信息的组，剩下的组内的记录去掉首尾字母再以前n个字母和后n个字母为key（因为此时组内是重复信息的概率已经比较大了所以n的取值可以适当调大，2甚至3也未尝不可）。

   第三次：重复第二次的操作，确定有多条信息相同就记录相同信息的条数。

   按这一方法，在正常的语言环境下算法的复杂度大概能控制在o（n）的水平上。

   不当之处望大家指正。

  所有算法里面， 涉及到string处理， 那么他就是慢的。 我有个巧妙的办法， 就是使用 BloomFilter. 具体怎么用查询去吧， 现成的很多。 不消耗内存， 也不消耗CPU。 这是个非严格算法， 这点需要明确。 这跟GOOGLE抓网页的时候， 要判断一个URL是否已经被收录处理过的算法情形一模一样么。。。。IT公司都会利用这些算法。


第2个题目是个相似度比较的东西， 可以使用俄国一个家伙提出的LD算法。我写的， 代码都贴给你。。。。

int getEditDistance(int src[], int dest[]) {
        if (src == null || dest == null) {
            // 出错
            return -1;
        }
        // 如果src是空串，那么差异度为dest的长度
        if (src.length == 0) {
            return dest.length;
        }

        if (dest.length == 0) {
            return src.length;
        }

        // 排列src的字符串作为竖列，排列dest的字符串作为横列，出现一个二维矩阵
        // 第一维是src，第二维是dest
        int[][] matrix = new int[src.length + 1][dest.length + 1];

        // src和dest都为空串的特殊情况，编辑距离为0
        matrix[0][0] = 0;

        // [1][0]代表src长度为1，而dest为空串时的编辑距离，以此类推
        for (int i = 1; i <= src.length; i++) {
            matrix[i][0] = i;
        }

        // [0][1]代表src为空串，而dest长度为1时的编辑距离，以此类推
        for (int i = 1; i <= dest.length; i++) {
            matrix[0][i] = i;
        }

        // 显然[0][0]是不需要比较的，它的编辑距离为0
        for (int i = 1; i <= src.length; i++) {
            // 取src中的第i个字符
            int i_src = src[i - 1];

            // 假设src的长度已经确定，它是个完整的字符串，长度为i
            // 求整个dest相对于src[i]所有编辑距离，则应：
            // 分别求出dest[0],dest[1]...dest[j]对于src的编辑距离
            for (int j = 1; j <= dest.length; j++) {
                // 取dest中的第j个字符
                int j_dest = dest[j - 1];

                // case 1
                int c1;
                // 设src长度为i-1，dest长度为j-1，它们的编辑距离为k
                // 则长度为i的src与长度为j的dest之间的编辑距离可以通过：
                // a. 将长度i-1的src编辑为长度j-1的dest，这需要代价k
                // b. 长度为i的src相当于长度为i-1的src加上第i个字符
                // c. 将src第i个字符替换成dest第j个字符，需要代价cost
                // d. 如果src第i个字符与dest第j个字符相同，cost=0
                // e. 如果(d)不成立，则cost=1
                // f. 最终长度为i的src与长度为j的dest的编辑距离为k+cost

                // 如src中当前字符与dest中当前字符相等，则无编辑代价，反之为1
                int cost = i_src == j_dest ? 0 : 1;

                // 长度为i的src与长度为j的dest的编辑距离为matrix[i][j]
                c1 = matrix[i - 1][j - 1] + cost;

                // case 2
                int c2;
                // 设src长度为i-1，dest长度为j，它们的编辑距离为k
                // 则长度为i的src与长度为j的dest之间的编辑距离可以通过：
                // a. 将长度i-1的src编辑为长度j的dest，这需要代价k
                // b. 将长度为i的src编辑成长度i-1的src，需要删去第i个字符
                // c. (b)中的代价为1
                // d. 从(b)得到长度为i-1的src，再从(a)得到长度为j的dest
                // e. 最终长度为i的src与长度为j的dest的编辑距离为k+1

                c2 = matrix[i - 1][j] + 1;

                // case 3
                int c3;
                // 设src长度为i，dest长度为j-1，它们的编辑距离为k
                // 则长度为i的src与长度为j的dest之间的编辑距离可以通过：
                // a. 将长度i的src编辑为长度j-1的dest，这需要代价k
                // b. 将长度j-1的dest编辑成长度j的dest需要加上第j个字符
                // c. (b)中的代价为1
                // d. 从(a)得到长度为j-1的dest，再从(b)得到长度为j的dest
                c3 = matrix[i][j - 1] + 1;

                // 综上所述三种可能性，求最小的值做为编辑代价
                matrix[i][j] = c1 <= c2 ? c1 : c2;
                if (matrix[i][j] > c3) {
                    matrix[i][j] = c3;
                }
            }
        }
        // 长度为i的src与长度为j的dest的编辑距离为matrix[i][j]
        return matrix[src.length][dest.length];
    }


这个算法是个严格意义的比较， 如果再要比较深入下去， 就是TF／IDF的一些东西了， cos/gjc 等文档聚合算法。search engine用来删除重复文档的东西， 再继续下去就是， 分词了。。。。一个很高深的题目。。。。。

To sdh5724 :
上来谢一下你的解答，学习了

M/R, BloomFilter, Levenshtein Distance,Hidden Markov Model，能说出这些鸟语，对于大部分不搞搜索的人来说，已经很令人肃然起敬，且能忽悠到一大群人了。

校长，您说对不对？

md还亲自写计算编辑距离的方法，真吃空啊。。。

Cheers,

Shawn