大厂面试题目

(Updated: )

1.1.1 如何实现一个高效的单向链表逆序输出？

出题人：阿里巴巴出题专家：昀龙／阿里云弹性人工智能负责人

参考答案：下面是其中一种写法，也可以有不同的写法，比如递归等。供参考。
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
typedef struct node{
    int           data;
    struct node*  next;
    node(int d):data(d), next(NULL){}
}node;

void reverse(node* head)
{
    if(NULL == head || NULL == head->next){
        return;
    }
    
    node* prev=NULL;
    node* pcur=head->next;
    node* next;
    
    while(pcur!=NULL){
        if(pcur->next==NULL){
            pcur->next=prev;
            break;
        }
        next=pcur->next;
        pcur->next=prev;
        prev=pcur;
        pcur=next;
    }
    
    head->next=pcur;
    node*tmp=head->next;
    while(tmp!=NULL){
        cout<<tmp->data<<"\t";
        tmp=tmp->next;
    }
}

1.1.2 题目：已知 sqrt (2)约等于 1.414，要求不用数学库，求 sqrt (2)精确到小数点后 10 位。

出题人：——阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家

考察点

  1. 基础算法的灵活应用能力（二分法学过数据结构的同学都知道，但不一定往这个方向考虑；如果学过数值计算的同学，应该还要能想到牛顿迭代法并解释清楚）
  2. 退出条件设计

解决办法

  1. 已知 sqrt(2)约等于 1.414，那么就可以在(1.4, 1.5)区间做二分
    查找，如：
    a) high=>1.5
    b) low=>1.4
    c) mid => (high+low)/2=1.45
    d) 1.45*1.45>2 ? high=>1.45 : low => 1.45
    e) 循环到 c)

  2. 退出条件
    a) 前后两次的差值的绝对值<=0.0000000001, 则可退出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const double EPSINON = 0.0000000001;

double sqrt2( ){
    double low = 1.4, high = 1.5;
    double mid = (low + high) / 2;
    
    while (high - low > EPSINON){
        if (mid*mid > 2){
            high = mid;
        }
        else{
            low = mid;
        }
        mid = (high + low) / 2;
    }
    
    return mid;
}