当前位置：网站首页>阿里腾讯面试一二

阿里腾讯面试一二

2022-08-01 09:35:00 【51CTO】

关于腾讯群面：

非技术岗的第一面是群面，无领导小组，6个人一组。一开始签到后就分好组了，一般都是不同学校的，有中大、华工这些名校也有我们普通本科，在候场时候就和组员聊一聊，结合自己性格特点做好分工，具体分工大概有3个角色,leader,时间控制者和总结者。一般带表的同学做Timer有优势点。进入会议室开始面试后，留给大家发题目。

2分钟看题目后，开始是30秒介绍！！！30秒介绍！！！30秒介绍！！！(重要三)介绍很短，你们要在提前准备好，切记不要多介绍多个辉煌事迹，只要讲一个与岗位相关的重点就好了(只是介绍自己最牛逼的事和特点)。然后开始讨论话题，我的话题是设计一个微信支付的应用场景，要求短时间内提高用户使用数量。但是我们组做的不好，3大原因：1.没有明显的Leader，只有一个华工的研究生学姐在领导大家讨论，但是逻辑不清楚，讨论得很混乱；2.Timer没做好，我本来就想做时间控制者但是我没做好分配时间，大家最后8分钟才确定应用场景，只有5分钟讨论问题和解决方案，不够全面。我的建议是大家提前去了解下微信QQ等社交产品，思考一些应用场景，这样讨论时候心理有低。一般如果你提出这个场景很好，无形中就可以成为Leader或者总结者，所以生活中多思考！3.讨论过程中没有强势的组员。我们组员讨论过程中有矛盾，但是大家都搁置矛盾，没有人坚持自己的想法，有不同意见就换了想法，大家都很友好。这一点面试官和我特别说了，这种情况很不好，必须有一些同学把自己的想法支持到最后。最后的结果是我们组只有总结的那个女生(同时也是她提出了大家认可的应用场景)进入了下一轮。

阿里腾讯面试一二_三元组

阿里腾讯面试一二_面试_02

阿里腾讯面试一二_面试_03

阿里腾讯面试一二_最小值_04

阿里腾讯面试一二_数组_05

阿里腾讯面试一二_最小值_06

阿里腾讯面试一二_职场和发展_07

阿里腾讯面试一二_三元组_08

阿里腾讯面试一二_面试_09

阿里腾讯面试一二_三元组_10

阿里腾讯面试一二_最小值_11

阿里腾讯面试一二_面试_12

阿里巴巴算法、数据工程师笔试题选解

1、有三个结点的，可以构成多少个种叉树？

2、一副牌52张(去掉大小王)，从中抽取两张牌，一红一黑的概率是多少？

编程题：

3、设计一个最优算法来查找一n个元素数组中的最大值和最小值。已知一种需要比较2n次的方法，请给一个更优的算法。情特别注意优化时间复杂度的常数。

4、已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素，是的组成的三元组距离最小。三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为:

Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)

请设计一个求最小三元组距离的最优算法，并分析时间复杂度。

5、在黑板上写下50个数字：1至50.在接下来的49轮操作中，每次做如下动作：选取两个黑板上的数字a和b，擦去，在黑板上写|b – a|。请问最后一次动作之后剩下数字可能是什么？为什么？

阿里腾讯面试一二_职场和发展_13

题解：(题解非官方，仅供参考，有错误的地方望指正！谢谢)

1、有三个结点的，可以构成多少个种树形结构？

解：应该是5种；

阿里腾讯面试一二_面试_14

2、一副牌52张(去掉大小王)，从中抽取两张牌，一红一黑的概率是多少？

考察概率论知识

解法一： 52张牌从中抽两张，就是 C(2,52)种情况，一红一黑是C(1,26) * C(1,26)种

P = [C(1,26) * C(1,26) ] / C(2,52) = 26 * 26 / (26 * 51) = 26/51

解法二：全为黑或者全为红是C(2,26)种情况，由于是黑和红两种，所以要乘以2

P = 1 – C(2,26) / C(2,52) – C(2,26) / C(2,52) = 1 – 2 * (26 * 25)/(51 * 52) = 1 – 25/51 = 26/51

解：把数组两两一对分组，如果数组元素个数为奇数，就最后单独分一个，然后分别对每一组的两个数比较，把小的放在左边，大的放在右边，这样遍历下来，总共比较的次数是 N/2 次；在前面分组的基础上，那么可以得到结论，最小值一定在每一组的左边部分找，最大值一定在数组的右边部分找，最大值和最小值的查找分别需要比较N/2 次和N/2 次；这样就可以找到最大值和最小值了，比较的次数为

N/2 * 3 = (3N)/2 次

如图会更加清晰：

代码实现：

阿里腾讯面试一二_职场和发展_16

阿里腾讯面试一二_最小值_17

       
       #include <stdio.h>
       
#include <stdlib.h>
       
#define N 7
       
int main()
       
{
       
    int arr[N] = {4, 1, 5, 9, 9, 7, 10};
       
    int iter = 0;
       
    int cnt = 0;
       
    for(iter = 0; iter <= N / 2 + 1 ; iter += 2)
       
    {
       
        if(++cnt && arr[iter] > arr[iter + 1] )
       
        {
       
            int temp = arr[iter];
       
            arr[iter] = arr[iter + 1];
       
            arr[iter + 1] = temp;
       
        }
       
    }
       
    int myMin = arr[0];
       
    for(iter = 2; iter < N ; iter += 2)
       
    {
       
        if(++cnt && arr[iter] < myMin)
       
        {
       
            myMin = arr[iter];
       
        }
       
    }
       
    int myMax = arr[1];
       
    for(iter = 3; iter < N; iter += 2)
       
    {
       
        if(++cnt && arr[iter] > myMax)
       
        {
       
            myMax = arr[iter];
       
        }
       
    }
       
    if(N % 2 != 0 && ++cnt && myMax < arr[N - 1]) myMax = arr[N - 1];
       
    printf("min is %d\n", myMin);
       
    printf("max is %d\n", myMax);
       
    printf("compare times is %d", cnt);
       
    return 0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.

阿里腾讯面试一二_面试_18

Distance = max(|a[ I ] – b[ j ]|, |a[ I ] – c[ k ]|, |b[ j ] – c[ k ]|)

请设计一个求最小三元组距离的最优算法，并分析时间复杂度。

解：这道题目有两个关键点：

第一个关键点： max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 –公式(1)

我们假设x1=a[ i ]，x2=b[ j ]，x3=c[ k ]，则

Distance = max(|x1 – x2|, |x1 – x3|, |x2 – x3|) = max( max(|x1 – x2|, |x1 – x3|) , |x2 – x3|) –公式(2)

　　根据公式(1)，max(|x1 – x2|, |x1 – x3|) = 1/2 ( |2x1 – x2– x3| + |x2 – x3|)，带入公式(2)，得到

Distance = max( 1/2 ( |2x1 – x2– x3| + |x2 – x3|) , |x2 – x3| )

=1/2 * max( |2x1 – x2– x3| , |x2 – x3| ) + 1/2*|x2 – x3| //把相同部分1/2*|x2 – x3|分离出来

　　　　　　=1/2 * max( |2x1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一个整体，使用公式(1)

=1/2 * 1/2 *((|2x1 – 2x2| + |2x1 – 2x3|) + 1/2*|x2 – x3|

　　　　　　=1/2 *|x1 – x2| + 1/2 * |x1 – x3| + 1/2*|x2 – x3|

　　　　　　=1/2 *(|x1 – x2| + |x1 – x3| + |x2 – x3|) //求出来了等价公式，完毕！

　　第二个关键点：如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值，x1，x2，x3，分别是三个数组中的任意一个数，这一题，我只是做到了上面的推导，后面的算法设计是由csdn上的两个朋友想出来的方法，他们的CSDN的ID分别为 “云梦泽” 和 “shuyechengying ”.

算法思想是：

　　用三个指针分别指向a,b,c中最小的数，计算一次他们最大距离的Distance ，然后在移动三个数中较小的数组指针，再计算一次，每次移动一个，直到其中一个数组结束为止，最慢(l+ m + n)次，复杂度为O(l+ m + n)

代码如下：

阿里腾讯面试一二_面试_19

阿里腾讯面试一二_面试_20

       
       #include <stdio.h>
       
#include <stdlib.h>
       
#include <math.h>
       
#define l 3
       
#define m 4
       
#define n 6
       
int Mymin(int a, int b, int c)
       
{
       
    int Min = a < b ? a : b;
       
    Min = Min < c ? Min : c;
       
    return Min;
       
}
       
int Solvingviolence(int a[], int b[], int c[])
       
{
       
    //暴力解法，大家都会，不用过多介绍了！
       
    int i = 0, j = 0, k = 0;
       
    int MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
       
//    int store[3] = {0};
       
    int Sum = 0;
       
    for(i = 0; i < l; i++)
       
    {
       
        for(j = 0; j < m; j++)
       
        {
       
            for(k = 0; k < n; k++)
       
            {
       
                Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
       
                if(MinSum > Sum)
       
                {
       
                    MinSum = Sum;
       
//                    store[0] = i;
       
//                    store[1] = j;
       
//                    store[2] = k;
       
                }
       
            }
       
        }
       
    }
       
//    printf("the min is %d\n", minABC);
       
//    printf("the three number is %-3d%-3d%-3d\n", a[store[0]], b[store[1]], c[store[2]]);
       
    return MinSum;
       
}
       
int MinDistance(int a[], int b[], int c[])
       
{
       
    int MinSum = 0; //最小的绝对值和
       
    int Sum = 0;  //计算三个绝对值的和，与最小值做比较
       
    int MinOFabc = 0; // a[i] , b[j] ,c[k]的最小值
       
    int cnt = 0;  //循环次数统计，最多是l + m + n次
       
    int i = 0, j = 0, k = 0;  //a,b,c三个数组的下标索引
       
    MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
       
    for(cnt = 0; cnt <= l + m + n; cnt++)
       
    {
       
        Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
       
        MinSum = MinSum < Sum ? MinSum : Sum;
       
        MinOFabc = Mymin(a[i] ,b[j] ,c[k]);//找到a[i] ,b[j] ,c[k]的最小值
       
        //判断哪个是最小值，做相应的索引移动
       
        if(MinOFabc == a[i])
       
        {
       
            if(++i >= l) break;
       
        }//a[i]最小,移动i
       
        if(MinOFabc == b[j])
       
        {
       
            if(++j >= m) break;
       
        }//b[j]最小,移动j
       
        if(MinOFabc == c[k])
       
        {
       
            if(++k >= n) break;
       
        }//c[k]最小,移动k
       
    }
       
    return MinSum;
       
}
       
int main(void)
       
{
       
    int a[l] = {5, 6, 7};
       
    int b[m] = {13, 14, 15, 17};
       
    int c[n] = {19, 22, 24, 29, 32, 42};
       
    printf("\nBy violent solution ,the min is %d\n", Solvingviolence(a, b, c));
       
    printf("\nBy Optimal solution ,the min is %d\n", MinDistance(a, b, c));
       
    return 0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15503184/5531183

当前位置：网站首页>阿里腾讯面试一二

阿里腾讯面试一二

阿里巴巴算法、数据工程师笔试题选解

边栏推荐

猜你喜欢

随机推荐