字节跳动-实习面经-基础架构

## 第一轮 2021/2/2

### 操作系统：

- 进程和线程的区别（顺便提了一下协程）
- 进程切换的过程

### Redis：

- 存储在内存中，如何实现快照
- 存储在磁盘上，如何确保事务操作的一致性

### 计算机网络：

- 简要介绍TCP、UDP

### 计算机组成：

- 计算机中负数的表示：补码、反码、原码之类的

### Coding

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

![img]()

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

![img]()

输入: [0,3,0,2,1,0,1,3,2,1,2,1]

输出: 12

```c
#include <stdio.h>
#define LEN (20)
.1point3acres
int main(){
    int height[LEN] = {0,3,0,2,1,0,1,3,2,1,2,1};
    int left_height[LEN];
    int right_height[LEN];
    int i,j;
    left_height[0] = 0;
    right_height[10] = 0;
    for(i = 1;i<11;i++){
        left_height[i] = (left_height[i-1] > height[i-1])? left_height[i-1]: height[i-1];
    }
    for(j = 9;j>=0;j--){
        right_height[j] = (right_height[j+1] > height[j+1]) ? right_height[j+1]: height[j+1];
    }
    for(i = 0; i<11;i++){
        printf("%d ",left_height[i]);
    }
    printf("\n");
    for(i = 0; i<11;i++){
        printf("%d ",right_height[i]);
    }
    printf("\n");
    int sum = 0;
    for(i = 0;i<11;i++){
        int min = (left_height[i] < right_height[i]) ? left_height[i] : right_height[i];
        if(height[i] < min){
            sum += min - height[i];
        }
    }
    //int a;
    //scanf("%d", &a);
    //printf("%d\n", a);
    printf("sum: %d\n",sum);
    return 0;
}
```

## 第二轮 2021/2/3

### 自我介绍

重点问了在实验室的工作，

主要是问了每个项目你担任的职位，以及这个职位为项目做出的贡献，还有你自己的收获、提升之类的。

### 直接开始写代码：

对一个链表进行排序操作，要求空间复杂度O(1)，时间复杂度尽可能小

做法（基于快排）：

```c
#include <stdio.h>
#define LEN (20)
struct Node{
    int value;
    struct Node *next;
};

void PrintList(struct Node *p){
    while(p!=NULL){
        printf("%d ",p->value);
        p = p->next;
    }
    printf("\n");
}
// divide and conquer
struct Node *ListSort(struct Node *begin){
    if(begin == NULL){
        return NULL;
    }
    struct Node *temp = begin;
    struct Node *less=NULL;
    struct Node *greater=NULL;
    struct Node *p,*q;
    int tmp = begin->value;
    begin = begin->next;
    // devide
    while(begin!=NULL){
        if(begin->value > tmp){
            if(greater == NULL){
                greater = q = begin;
            }
            else{
                q->next = begin;
                q = q->next;
            }
            begin = begin->next;
            q->next = NULL;
        }
        else{
            if(less == NULL){
                less = p = begin;  
            }
            else{
                p->next = begin;
                p = p->next;
            }
            begin = begin->next;
            p->next = NULL;
        }
    }
    // conquer
    struct Node *left = ListSort(less);
    struct Node *right = ListSort(greater);
    // combine
    p = left;
    if(p == NULL){
        temp->next = right;
        return temp;
    }
    else{
        while(p->next!=NULL){
            p = p->next;
        }
        p->next = temp;
        temp->next = right;
        return left;
    }
}

int main(){
    int num[LEN] = {3,2,4,1,5,0,1,3,2,1,2,1};
    struct Node *p,*q;
    p = q = NULL;
-baidu 1point3acres    struct Node* list = NULL;
    int i;
    for(i = 0;i<12;i++){
        q = (struct Node *)malloc(sizeof(struct Node));
        q->value = num[i];
        q->next = NULL;
        if(p == NULL){
            list = p = q;
        }
        else{
            p->next = q;
            p = p->next;
        }
    }
    PrintList(list);
    list = ListSort(list);
    PrintList(list);
. 1point 3 acres}
```

对于数据库你了解多少？

为什么要用B+树，B+树有什么优点？

Cookie和Session的区别，如果没有Cookie会怎么样？

给个场景，写出Join和Group By 的例子

```mysql
## 我给的答案：
student_table:
ID NAME COURSE SCORE

SELECT NAME,SCORE from
    student_table
       GROUP BY COURSE HAVING Score = max(score)
## 面试官反馈： 基本意思没问题，但是细节有错误
```

## 第三轮 2021/2/8

上来还是先自我介绍

问了一些实验室工作的问题和未来的研究方向

### coding：构造并合并两个排序链表：

我直接怼了，写的不太好看……

```c
. Χ#include <stdio.h>
struct Node{
    int val;
    struct Node *next;
};

void PrintList(struct Node *p){
    while(p!=NULL){
        printf("%d ",p->val);
        p = p->next;
    }
    printf("\n");
}

struct Node *buildList(int *array){
    struct Node *a,*p,*q;
    a = NULL;
    // build a
    for(int i = 0;i<5;i++){
        q = (struct Node *)malloc(sizeof(struct Node));
        q->val = array[i];
        q->next = NULL;
        if(a == NULL){
            a = p = q;
        }
        else{
            p->next = q;
            p = p->next;
        }

    }
    return a;
}

struct Node *mergeList(struct Node *a,struct Node *b){
    struct Node *begin = NULL;
    struct Node *p;
    while(a!=NULL && b!=NULL){
        if(a->val < b->val){
            if(begin == NULL){
                begin = p = a;   
            }
            else{
                p->next = a;
                p = p->next;
            }
            a = a->next;
        }
        else{
            if(begin == NULL){
                begin = p = b;
            }
            else{
                p ->next = b;
                p = p->next;
            }
            b = b->next;
        }
    }
    p->next = (a==NULL)? b:a;
    PrintList(begin);
    return begin;
}

int main(){
    //int a;
    //scanf("%d", &a);
    //printf("%d\n", a);
    int array_a[10] = {1,3,5,7,9};
    int array_b[10] = {2,4,6,8,10};
    struct Node *a= NULL;
    struct Node *b = NULL;
    struct Node *p,*q;
    int i,length = 5;
    a = buildList(array_a);
    b = buildList(array_b);
    PrintList(a);
    PrintList(b);
    struct Node *res = mergeList(a,b);
    return 0;
}
```

### 场景题：如何维护一个热度排行，比如日排行，周排行，月排行？

答：堆排序+归并排序

然后问了一些实习时间相关的事情。