一些有趣的题目

作者: 晓梦蝉君 | 来源:发表于2016-05-04 13:57 被阅读1123次

最近被问到的面试题，算法、语言基础、计算机网络、操作系统相关。

1.假如一个国家实行这样的政策：一对夫妇生孩子，如果是男孩就不能再生；如果是女孩就必须再生一个，直到生出男孩为止。（假设每胎只生一个娃，不考虑多胞胎的情况）最终这个国家男女比例会如何？（概率论）
答：排除人工干预的情况（性别鉴定、打胎等），一对夫妻生的每个孩子都可以看作一次独立的随机实验，假设需要进行N次实验才能得到男孩的期望结果，记为事件X。那么实验结果满足二项分布。根据生物学遗传定律，每次生男生女的概率均为1/2，那么N次伯努利实验的期望为E(X)=Np=N/2。即进行N次实验，会有N/2个结果是男孩，N/2个结果为女孩，所以这个政策最终会导致男女比例接近1:1。
P.S. 据说学过随机过程的用停时理论也能解释，不懂随机过程。。

2.数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字（假设数组很大）（百度面试题）。
答：假设数组是无序排列的。如果是有序的，直接输出第N/2个数就行了。比较直接的思路是使用快速排序将整个数组进行排序，然后输出排序后数组的第N/2个数就是结果。时间复杂度为O(NlogN)。

网络上流行的解法是基于比较和计数器的O(N)时间解法，思路来源是《编程之美》的寻找水王。即，某个数出现次数超过数组元素总数的一半，那么我们比较的过程中每次比较两个数，如果不同，则将他们剔除，剩余数组里该数出现次数仍然超过总数的一半，这样在遍历的过程中就能完成查找，缩小搜索范围。具体算法设计考虑设置变量ref_val存储可能存在的查找数，变量count统计这个数字出现的频数。每次比较的时候如果下一个数和ref_val相同，那么就将count加1，否则减1。当count变为0时，更新ref_val为当前比较的新数，同时将count置为1。遍历完毕整个数组后，ref_val存储的就是要找的数字。这种解法只需要时间复杂度为O(N)，同时需要额外的空间开销为O(1)。

另外一种解法是基于快速排序的改进。实际上我们并不需要对整个数组进行排序，快速排序的partition过程是找到枢轴元素，使得枢轴左边的数字都小于该数，右边的数字都大于该数。所以我们的做法就是不断使用partition方法找到位于N/2位置的枢轴元素。具体算法设计为：设我们最终要找的枢轴元素位置为mid = N/2。一开始先对整个数组进行一次partition过程，找到枢轴位置pivotPos。如果pivotPos == mid，那么直接输出array[pivotPos]；如果pivotPos < N/2，那么我们对[pivotPos+1, end]范围内的数用partition方法调整，得到pivotPos；如果pivotPos > N/2，那么我们对[start, pivotPos-1]范围内的数用partition方法进行调整，得到pivotPos。重复这一过程直到最后pivotPos==N/2时输出array[pivotPos]为结果。这样的解法时间复杂度也是O(N)。

根据题目的描述来看，这个数肯定是存在于数组中的，我认为不需要加一个检验的方法。但考虑到检验的话会更完善一些。即将找到的数作为参考值再次遍历数组，统计该数在数组中出现的次数看是否超过一半。
对于查找结果，如果存在该数的话返回数字，不存在的话返回一个定义的异常值。可以采用climits库中定义的INT_MAX或者INT_MIN这样一个最值的宏表示没有找到对应的数。

基于思路2和思路3的代码如下：

#include<iostream>
#include<climits>
#include<vector>
using namespace std;

class Solution
{
private:
    int searchByCmp(vector<int>& arr){
         if(arr.size() == 0) return INT_MIN; 
         int ref_val = arr[0];
         int count = 1;
         for(int i = 0; i < arr.size(); i++){
               if(count == 0){
                      ref_val = arr[i];
                      count = 1;
               }
               else if(ref_val == arr[i])
                      count++;
               else
                      count--;
         }
         return ref_val;
    }
   
    int partition(vector<int>& arr, int left, int right){
         int pivotKey = arr[left];
         while(left < right){
              while(left < right && arr[right] >= pivotKey)
                      right--;
              arr[left] = arr[right];
              while(left < right && arr[left] <= pivotKey)
                      left++;
              arr[right] = arr[left];
         }
         arr[left] = pivotKey;
         return pivotKey;
    }

    int searchByPartition(vector<int>& arr, int start, int end){
         if(arr.size() == 0) return INT_MIN;
         int pivotPos = partition(arr, start, end);
         int mid = (end - start + 1)/2;
         while(pivotPos != mid){
                if(pivotPos > mid)
                    pivotPos = partition(arr, start, pivotPos - 1);
                else
                    pivotPos = partition(arr, pivotPos+1, end);
         }
         return arr[pivotPos];
    }

    bool validate(vector<int>& arr, int result){
         bool isMoreThanHalf = true;
         int count = 0;
         for(int i = 0; i < arr.size(); i++)
               if(result == arr[i])  count++;
         if(count * 2 <= arr.size()) isMoreThanHalf = false;
         return isMoreThanHalf;
    }

public:
     int findMoreThanHalfNum(vector<int>& arr){
          int result = 0;
          result = searchByCmp(arr);
          // result = searchByPartition(arr, 0, arr.size()-1);
          if(result == INT_MIN) return result;
          if(validate(arr, result))
             return result;
          return INT_MIN;
     }
}

3.单向链表判环。
答：采用快慢指针。设置两个指针pFast和pSlow，都从链表头结点开始遍历链表，pFast一次移动两步，pSlow一次移动一个步，如果链表有环，两个指针最终会相遇。代码如下：

#include<iostream>
using namespace std;

typedef struct LinkedList{
       int value;
       LinkedList* pNext;
       LinkedList(int v): value(v), pNext(NULL){}
} LinkedList;

bool  find_loop(LinkedList* head){
       if(head == NULL) return false;
       LinkedList* pFast = head;
       LinkedList* pSlow = head;
       while(pFast && pFast->pNext){
              pFast = pFast->pNext->pNext;
              pSlow = pSlow->pNext;
              if(pFast == pSlow)
                 return true;
      }
      return false;
}

4.一个盲人面对桌面上七张纸牌，三张正面朝上，四张背面朝上，在没有人帮助的情况下，怎样把这堆牌分成两叠，每叠正面朝上的牌数相同？
答：设1表示正面朝上，0表示背面朝上。一开始的牌面状况为1110000。那么分牌策略为：
第一步，盲人将牌任意分为三张一堆和四张一堆，会有以下四种情况：
1) 111/0000
2) 110/1000
3) 100/1100
4) 000/1110
第二步，将三张的牌堆里面的牌全部翻面，则对应上面四种情况的结果为：
1) 000/0000(两堆0张正面朝上)
2) 001/1000(两堆各有1张正面朝上)
3) 011/1100(两堆各有2张正面朝上)
4) 111/1110(两堆各有3张正面朝上)
实现目标。

5.根据一个结构体对象某成员（非函数）的地址，计算出该结构体对象的首地址。（Linux内核代码用法）
答：没接触过这类的题目。这题的解法比较有技巧性，巧妙的用了一个强制转换来计算偏移量。具体实现有基于宏的也有用函数的，推荐用宏，可以参考这篇文章提出的解法。

6.TCP和UDP协议的不同。
答：

	TCP	UDP
工作模式	基于连接建立连接三次握手断开连接四次握手	无连接
开销	耗时，占用系统资源多	占用资源少
数据量	流模式，用于传输大量数据	数据报模式，用于一次传输少量数据
传输可靠性	保证数据可靠性，保证数据顺序流量控制差错恢复	不可靠传输，速度快，可能丢包

7.操作系统中有哪些内存管理算法，阐述其原理。
答：页面置换算法，段页式管理算法。页面置换算法基于局部性远离，常用的有最佳置换算法(Optimal Page Replacement Algorithm)，最佳置换算法是将未来最久不使用的页替换出去，虽然理论很好，但是无法实现，仅作为衡量其它算法的基准。最近不常使用算法(Not Recently Used Replacement Algorithm)，算法给每个页一个标志位，R表示最近被访问过，M表示被修改过。定期对R进行清零。这个算法的思路是首先淘汰那些未被访问过R=0的页，其次是被访问过R=1,未被修改过M=0的页，最后是R=1,M=1的页。先进先出页面置换算法(First-In,First-Out Page Replacement Algorithm)，算法的思想是淘汰在内存中最久的页，这种算法的性能接近于随机淘汰。并不好。改进型FIFO算法(Second Chance Page Replacement Algorithm)，算法是在FIFO的基础上，为了避免置换出经常使用的页，增加一个标志位R，如果最近使用过将R置1，当页将会淘汰时，如果R为1，则不淘汰页，将R置0.而那些R=0的页将被淘汰时，直接淘汰。这种算法避免了经常被使用的页被淘汰。但由于需要经常移动页，效率并不高。时钟替换算法(Clock Page Replacement Algorithm)，在改进型FIFO算法的基础上，将队列首位相连形成一个环路，当缺页中断产生时，从当前位置开始找R=0的页，而所经过的R=1的页被置0，并不需要移动页。段页式管理算法具体内容参考操作系统教材。

8.给你一个能生成1到5随机数的函数，用它写一个函数生成1到7的随机数。 (即：使用函数rand5()来实现函数rand7())。
答：我们不可能由rand5()直接生成或者经过加减乘除生成rand7()，但我们可以直接由rand7()生成rand5()。解决办法的主要思路是构造一个更大的等概率值域空间。具体办法有线性变换、位运算或者矩阵转换。感觉第一种办法最通用。
1)线性变换
详细分析参考这篇文章。
问题的变式为：给你一个随机生成a到b的函数，用它去实现一个随机生成c到d的函数。
可以先考虑由生成[3,10]的随机函数rand310得到生成[5,7]的随机函数rand57，经过类似的推导可以设计出通用算法如下：
随机函数生成算法：
已知给定随机函数函数Randab可以生成a到b的函数，构造随机函数Randcd。
步骤1：如果a<c且b>d，或者a>d且b>d，进入步骤2；否则，构造Randab2=(b-a+1)Randab + Randab，表示生成a2=(b-a+1)a+a到b2=(b-a+1)b+b之间的数。如果a2，b2仍不满足前述条件，继续构造Randab3=(b-a+1)Randab2+Randab...，直到ak，bk满足前述条件。这时我们得到Randabk，我们记为RandAB。
步骤2：根据步骤1得到的RandAB，满足A<c且B>d，或者A>d且B>d。我们通过如下代码构造Randcd：

//prerequisition: B>d && (A<c || A>d)
int Randcd(){
    int res = ~(1<<31); // res = INT_MAX
    int delta = d-c+1;
    while( (x < delta*ceil(A*1.0/delta)) || (x>delta*(B/delta) - 1) )
         x = RandAB();
    return x % delta + c;
}

2)位运算
把生成的随机数看成二进制串，利用rand5()构造一个随机生成0、1的函数rand01。然后对于每一位调用rand01，将结果拼接得到1~7之间的随机数。代码如下：

// 等概率生成0,1
int rand01()
{
int i = rand5();
while(i > 4) 
{
    i = rand5();
}
return i % 2;
}
// 二进制加法
int bitAdd(int a,int b){
      if(b==0){
         return a;
      }
      int sum,carry;
      sum=a^b;
      carry=(a&b)<<1;
      return Add(sum,carry);
}
// 等概率生成 1~7
int rand7()
{
   int x;
   int high, mid, low;
   do{
       high = rand01() << 2;
       mid = rand01() << 1;
       low = rand01();
       x =  bitAdd(bitAdd(high, mid), low);
   }while(x == 0);
   return x;
}

3)矩阵转换
可以生成一个5*5的矩阵，所以共有25个元素可供随机挑选，由于最接近25的7的倍数是21，所以在矩阵中填充1_{7，每个数字出现3次。使用rand5()来随机选取二维数组的下标得到1}7之间的随机整数。代码如下：

int matrix[5][5];
memset(matrix, 0, sizeof(matrix));
int (*p)[5] = matrix;
int *q = *p;
for(int i = 1; i <=7; ++i)
{
    for(int j = 0; j < 3; ++j)
    {
          *q = i;
        q++;
    }
}

int rand7()
{
    int i;
    do
    {
       i = matrix[rand5() - 1][rand5() - 1];
    }while(i == 0);
    return i;
}

一些有趣的题目

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读