首页 > 蓝汛通讯后端开发社招面经
头像
启之
发布于 2020-07-26 22:59
+ 关注

蓝汛通讯后端开发社招面经

一面:

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).

比如数组为78912345 ,则认为是循环递增的,需要找出最小的元素,就是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

 
4、一个整数数组(int A[]),找里面的整数满足左边的 A[j] - A[i] 和右边的A[m] - A[n]的相加的值最大,求这个最大值。

更多模拟面试

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐