几个笔试、面试题

| |
| 977 | 4

前段时间去上海参加校园招聘会了，就把期间遇到的几个笔试和面试题跟大家分享一下。

证明：如果一个数介于孪生素数之间且大于等于6，则这个数是6的倍数

这个问题面试的时候没想出来，想了很久，后来一次在等地铁的时候突然想到了怎么证明。这个问题的证明其实是很简单的，既然是孪生素数之间的数，那么这个数必然是偶数了。因为这两个素数必然是奇数，而介于两个奇数之间的数肯定是偶数啦，即这个数能被2整除了，接下来就只需要证明这个数能被3整除就可以了。

假设这个数是Y，两个素数分别是X,Z(5<=X<Z)，则有Z-X=2, X=Y-1, Z=Y+1，即X、Y、Z三个数是连续的。而三个连续的数中必有一个是3的倍数，又X、Z都是素数，即X、Z都不能被3整除，所以Y一定能被3整除，最终得出Y能被6整除，即Y是6的倍数。

实现double pow(double x,int y)函数

这个问题也很简单，不过细节很重要，有以下情况需要判断：x=0, y=0, y<0。下面给代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdlib.h>
double pow(double x,int y){
  double result = 1.0;
  int i;
  if(y >= 0){
    for(i = 0;i < y;i++){
      result *= x;
    }
  }else if(x == 0){
    exit(1);//终止程序
  }else{
    result = 1 / pow(x,-y);
  }
  return result;
}

当然了，上面的实现可以换成非递归，然后大家可以想一想怎么实现double pow(double x,double y)函数。

输出一个字符串中字符的所有排序序列

这个问题也挺简单的，就是对字符重新组合。可以使用递归的思想来考虑，首先取出这个字符串的第一个字符，然后对剩下的字符串求所有排列，再将刚才的字符插入到每个字符串中的每一个位置(这句话不知道表达清楚了没)。例如：对字符串abc,先取出第一个字符a，然后对剩下的字符串bc，求其所有排列（bc,cb），然后将a插入到bc和cb中，得到abc，bac，bca，acb，cab，cba共六种排列。下面给出代码(JavaScirpt)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function showAllSort(str) {
    function getAllSort(str) { //获取函数定义
        if (str.length < = 1) {
            var obj = {};
            obj[str] = 1;
            return obj;
        }
        var allSort = {}, //保存当前str的所有排列
            firstChar = str.slice(0, 1),
            //获取移除第一个字符后的所有排列
            subSort = getAllSort(str.slice(1, str.length));
        for (var substr in subSort) { //插入第一个字符
            for (var i = 0, l = substr.length; i <= l; i++) {
                allSort[substr.slice(0, i) + firstChar + substr.slice(i, l)] = 1;
            }
        }
        return allSort;
    }
    if (typeof str == "string" || str instanceof String || Object.prototype.toString.call(str) == "[object String]") {
        var allSort = getAllSort(str),
            fragment = document.createDocumentFragment();
        for (var s in allSort) {
            var p = document.createElement("p");
            p.innerHTML = s;
            fragment.appendChild(p);
        }
        document.getElementById("strSort").appendChild(fragment);
    }
}

这个实现中，使用了js对象的动态性，可以随时添加js对象的属性，即类似hashmap的特性，不会重复保存相同的排列。然后其中并没有对实现进行优化，没有对字符串进行分析（如有相同字符时的重复计算）。而递归实现也太耗费内存了，尤其是在浏览器中，很容易导致栈溢出等问题。还有在一个对象上添加很多属性应该也会引起性能问题，对于一个没有重复字符长度为10的字符串，其所有排列的个数是10!=3628800，太恐怖了！

所以上面我给的方法都不是最好的，所以我也还要继续研究算法啦！