一面：
1、介绍下你做的项目。介绍完后，面试官就问些项目的情况，他所感兴趣的方面
2、回型打印矩阵里面所有的整数。
比如：矩阵为：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
先打印外围的黄色整数（从左到右，再从上往下，再从右往左，再从下往上，这样打印一个外围环），再打印绿色的整数，一直打印完所有整数。
分析：可以使用二维数组表示矩阵。
#include<iostream>
using namespace std;
void printMatrix(int a[4][5], int n1, int n2, int m1, int m2)
{
if(n1 == n2)
{
for(int i= m1; i <= m2; i++)
cout << a[n1][i] << ",";
return;
}
if(m1 == m2)
{
for(int i= n1; i <= n2; i++)
cout << a[i][m1] << ",";
return;
}
for(int i = m1; i < m2; i++)
cout << a[n1][i] << ",";
for(int i = n1; i < n2; i++)
cout << a[i][m2] << ",";
for(int i = m2; i > m1; i--)
cout << a[n2][i] << ",";
for(int i = n2; i > n1; i--)
cout << a[i][m1] << ",";
printMatrix(a, n1+1, n2-1, m1+1, m2-1);
}
int main()
{
int a[4][5] = {{1,2,3,4,5},{14,15,16,17,6},{13,20,19,18,7},{12,11,10,9,8}};
printMatrix(a, 0, 3, 0, 4);
} 输出结果为：
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
3、递增的整数数组，并且整数可能为正负，找到所有的值等于其位置的整数。
这题最简单的方法是遍历一次，算法复杂度为O(n)，显然面试官不是这个想法，最起码算法复杂度要达到O(lg(n))。
分析：
使用二分法，找到a[k] = k的位置，再左右找所有相等的数。
#include<iostream>
using namespace std;
void printall(int a[], const int n)
{
if(a[0] > 0 || a[n-1] < 0)
return;
int i = 0;
int j = n-1;
int k = -1;
while(i <= j)
{
k = (i+j)/2;
if(a[k] == k)
break;
if(a[k] > k)
j = k -1;
else
return;
}
if(i <= j)
{
for(int ii = k; ii < n-1 && a[ii] == ii; ii ++)
cout << a[ii] << ",";
for(int ii = k-1; ii >= 0 && a[ii] == ii; ii --)
cout << a[ii] << ",";
}
}
int main()
{
int a[10] = {-9,-8,0,3,4,5,8,9,10,11};
printall(a, 10);
} 输出结果为：
4,5,3,
4、缓存系统的设计
二面：
1、先问了下项目的东西，跟上一面差不多；
2、 a,b 是正整数，使用a + sqrt(b)求值，找出这些值黎明的第K大的值，并且求出a 和 b
int findK(int k, int&a, int& b)
{
}
3、一个循环递增数组，找出最小的元素及其位置，要求算法的时间复杂度为O(logn).
比如数组为7，8，9，1，2，3，4，5 ，则认为是循环递增的，需要找出最小的元素，就是1，并且输出其位置。
实现如下：
#include<iostream>
using namespace std;
int findmin_pos(int a[], const int n)
{
int i = 0;
int j = n -1;
int k = 0;
if(a[0] <= a[n-1])
{
return 0;
}
while(i<=j)
{
k = (i+ j)/2;
if(k > 0 && a[k] < a[k-1])
{
return k;
}
if(a[k] > a[n-1])
i = k + 1;
else if(a[k] == a[n-1] && a[k] == a[0])
i = k + 1;
else
j = k - 1;
}
return -1;
}
int main()
{
int a[9] = {7,8,9,1,2,3,4,5,6};
int pos = findmin_pos(a, 9);
if(pos == -1)
cout << "error" << endl;
else
cout << "min pos: " << pos << " min value: " << a[pos] << endl;
} 输出结果为：
min pos: 3 min value: 1
全部评论
(2) 回帖