面试笔记|算法面试真题（二）

前言：曾经遇到过的面试真题

1.已知在一维数组A[m+n]中依次存放两个线性表（a1,a2……am）(b1,b2……bn)。写一个函数，将两个顺序表的位置互换，即将b放到a的前面。

解答
设计思想：首先将A[m+n]的全部元素逆置（bn,bn-1……b1,am,am-1……a1）,再分别逆置b，a。

void revere(DataType A[],int left,int right，int arraySize){
//reverse array from left to right

  int mid = (left + right)/2;
  if(left>=right || right >= arraySize) return;
  for(int i = 0;i < mid - left;i++){

     DataType temp = A[left + i];
     A[left + 1] = A[right - i];
     A[right - i] = temp;  

  }

}

void exchange(DataType A[],int m,int n,int arraySize){
  reverse(A,0,m+n-1,arraySize); //reverse A
  reverse(A,0,n-1,arraySize);   //reverse b
  reverse(A,n,m+n-1,arraySize); //reverse a
}

在此想扩展一个曾遇到的练习,设将n（n>1）个整数存放到一维数组R中，将R中保存的序列循环左移p个位置，即将R中数据由（x0,x1……xn-1）->(xp,xp+1……x0,x1……xp-1).

解答
设计思想：数组ab（a代表前p个，b代表之后的元素），一般应再创建一个数组S[]，先将a放入S中，然后将b左移n-p，然后将S中的a接入A尾部。此算法时间复杂度O(n),空间复杂度O(p)。在这里采用另种高效的方法。
先将a转置为a'b,再将b转置为a'b'，再将整体转置为ba。此算法无需额外开辟空间，时间复杂度O(n)，空间复杂度O（1），因此效率很高。

因此，仍需要编写reverse函数。

void reverse（DataType A[],int left,int right）{
  int i;
  if(left>=right) return;
  int mid = (left + right)/2;
  for(i = 0;i < mid - left;i ++){
     DataType temp = A[left + i];
     A[left + 1] = A[right - i];
     A[right - i] = temp;  
  }
}

void exchange(DataType A[],int p,int n){
   reverse(A,0,p-1);  
  reverse(A,p,n-1);
  reverse(A,0,n-1);
}

---

2.当前已经编程实现函数:int rand100(),该函数可返回0~99的随机整数,且可以保证等概率,请利用该函数实现int rand10000(),要求等概率返回0~9999的随机数

解答

int rand10000()｛
   int a,b；
   a = rand100()*100;
   b = rand100();
   return a+ b;
｝

---

3.汤姆现在要在家里举办宴会，他有很多根长度并不完全相同的筷子。现已知每根筷子的长度，每个客人都能拿到两根相同长度的筷子，求宴会最多可以招待多少名宾客的函数实现int getMax(int arrLength[N])

解答

int getMax(int arrLength[N]) {
      assert(arrLength != NULL && N > 0)
      int count = 0;
      int maxLength = arrLength[0];

      for (int i = 1; i < N; i++) {
          if (maxLength < arrLength[i]) { maxLength = arrLength[i]; }
      }

      char * counter = (char *)malloc(sizeof(char) * (mexLength + 1));
      memset(counter, 0, mexLength+1)
      for (int i = 0; i < N; i++) {
          int idx = arrLength[i];
          if (counter[idx] == 0) {
              counter[idx] = 1;
          } else {
              count++;
              counter[idx] = 0;
        }
      }
      free(counter);
      return count;
   }

---

4.现有一个M行N列的数组，要求按照反向斜对角线（右上角->左下角）的方式进行打印，编程实现int printMatrix[int arrMatrix[M][N]]

解答

void printMatrix(int arrMatrix[M][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = i, k = 0; j >= 0 && k < M; j--, k++) {
            printf("%d->", arrMatrix[k][j]);
        }
    }

    for (int i = 1; i < M; i++) {
        for (int j = N - 1, k = i; j >= 0 && k < M; j--, k++) {
            printf("%d", arrMatrix[k][j]);
            if (j < N - 1 || k < M - 1) {
                printf("->");
            }
        }
    }
}

---

5.假设北京和上海间有一趟专列，两个车站每小时整点都会朝着对方发一辆车。已知北京->上海的列车全程需要13.5小时；上海->北京的列车全程需要15.5小时。如果某人坐在其中一辆北京->上海的列车，请问途中会碰到多少辆迎面而来的列车

解答
乍一看是一道数学题，经过数学的计算是29辆车

---

在查找资料过程中看到算法收录（持续更新）有相同的题目做了一些引荐，很怀疑我们曾面过一家公司。另外欢迎各位大神能够将其优秀的答案私信或评论于下方，共同探讨进步，感谢。