几个笔试、面试题

2011-11-01

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

证明:如果一个数介于孪生素数之间且大于等于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。下面给代码了:

#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):

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,太恐怖了!

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