神刀安全网

面试笔记|算法面试真题(二)

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

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辆车


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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 面试笔记|算法面试真题(二)

分享到:更多 ()