2019-09-22 更新

笔试/面试日历

公司 日期 时间 平台
百度 9.17 (周二) 19:00-21:00 赛码
美团 9.18 (周三) 15:00-17:00 赛码
深信服 16:00-18:00 牛客
电信云 20:30-22:30 牛客
微众 9.19 (周四) 16:00-18:00 赛码
滴滴 19:00-20:40 赛码
腾讯 9.20 (周五) 20:00-22:00 牛客
华为 9.21 (周六) 13:00 面试 天河区酒店
字节跳动 9.22 (周日) 8:00-10:00 牛客
招银网络科技 9.24 (周二) 15:00-? 待定
电信云计算 9.25/26 (周三) 面试 待定

待投递

校招官网 微信 时间
平安科技 平安科技招聘 10.9 网申截止，Q&A
京东 京东招聘 京东数科，Q&A
数字广东 数字广东招聘 内推 1，内推 2

其他

已投递

校招官网 微信 时间
腾讯 腾讯招聘 9.15 简历截止
阿里 阿里技术栈 9.12 简历截止，Q&A
字节跳动 字节跳动招聘 9.22 笔试，Q&A
华为 华为招聘 已投递
百度 百度招聘 9.17 19:00 笔试，Q&A
电信云计算 电信云计算校招内推 9.25/26 广州面试，牛客内推
网易游戏 网易游戏综合招聘 9.19 网申截止，Q&A
网易游戏-互娱 网易游戏互娱校园招聘 9.19 内推截止
网易游戏-雷火 网易游戏雷火伏羲招聘 9.12 网申截止，Q&A
滴滴 滴滴出行校园招聘 9.15 网申截止，Q&A
美团点评 美团点评招聘 9.18 15:00 笔试，笔试攻略
深信服 深信服招聘 9.18 笔试，岗位描述
微众银行 WeBank招聘 9.18 网申截止，9.19 笔试
招银网络科技 招银网络科技 9.23 网申截止

已结束

校招官网 微信 时间
网易互联网 网易招聘 已结束
网易有道 有道招聘 9.17 网申截止，已结束
哔哩哔哩 哔哩哔哩招聘 已结束
DJI大疆 DJI大疆招聘 已结束
小米 小米招聘 9.11 笔试，笔试指南
顺丰科技 顺丰科技招聘 已结束
360 360招聘 已结束

笔试题/面经

重点复习

1. 排序算法

常用排序算法复杂度及稳定性：

参见 十大经典排序算法动画与解析，看我就够了 | 五分钟学算法

关于时间复杂度：

  • O(n^2)：各类简单排序，包括直接插入、直接选择、冒泡排序
  • O(nlogn)：快速排序、堆排序、归并排序

关于稳定性：

  • 稳定的排序算法：冒泡、插入、归并、基数
  • 不稳定的排序算法：选择、快速、希尔、堆
2. TCP 三握四挥

TCP 三次握手、四次挥手：

参见：

  1. 网络协议笔记 4：传输层之 TCP 协议 | 苏易北
  2. “三次握手，四次挥手”你真的懂吗？| 码农桃花源
  3. TCP 的那些事儿（上）| 酷壳 CoolShell
  4. TCP 的那些事儿（下）| 酷壳 CoolShell
TCP 头格式
TCP 头格式
  • TCP 的包是没有 IP 地址的，那是 IP 层上的事。但是有源端口src_port和目标端口dst_port
  • 一个 TCP 连接需要四个元组(src_ip, src_port, dst_ip, dst_port)来表示是同一个连接
  • Sequence Number：包的序号seq，用来解决网络包乱序 (reordering) 的问题
  • Acknowledgement Number：就是ACK，表示确认收到了包，用来解决丢包的问题
  • Window：又叫Advertised-Window，也就是著名的滑动窗口 (Sliding Window)，用于解决流量控制问题
TCP 状态机
TCP 状态机
TCP 三次握手与四次挥手
TCP 三次握手与四次挥手

对于建立连接的三次挥手：

  • 主要是初始化Sequence Number的值。通信的双方要互相通知对方自己的初始Sequence Number，缩写为ISN即Initial Sequence Number，所以叫SYN，全称Synchronize Sequence Numbers。这个号要作为以后数据通信的序号，以保证应用层接收到的数据不会因为网络上的传输问题而乱序 (TCP 会用这个序号来拼接数据)
  • 确保双方都能明确自己和对方的收、发能力是正常的 (TCP 连接是全双工的)

对于断开连接的四次挥手：

  • 其实仔细看是两次，因为 TCP 是全双工的，所以发送方和接收方都需要FIN和ACK。当有一方要关闭连接时，会发送指令告知对方，我要关闭连接了，这时对方会返回一个ACK。此时一个方向的连接关闭，但是另一个方向仍然可以继续传输数据，等到发送完所有的数据后，会发送一个FIN来关闭此方向上的连接，最后由接收方发送ACK确认关闭连接
  • 需要注意的是：接收到FIN报文的一方只能回复一个ACK，是无法马上返回给对方一个FIN报文段的，因为是否结束数据传输由上层的应用层控制

为什么关闭时需要四次挥手？

  • 当Server端收到Client端的SYN连接请求报文后，可以直接发送SYN+ACK报文，其中ACK报文是用来应答的，SYN报文是用来同步的
  • 但是关闭连接时，当Server端收到FIN报文时，很可能并不会立即关闭Socket
  • 所以只能先回复一个ACK报文，告诉Client端，你发的FIN报文我收到了，等到我Server端所有的报文都发送完了，才能发送FIN报文
  • 因此Server端的ACK和FIN不能一起发送，故需要四次挥手

为什么不能用两次握手进行连接？

  • 主要是为了防止已失效的连接请求报文段突然又传到了B，避免产生错误
  • 现假定一种异常情况，即A发出的第一个连接请求报文段并没有丢失，而是在某些网络节点长时间滞留了，以致延误到连接释放后的某个时间才到达B。本来这是一个早已失效的报文段。但B受到此失效的连接请求报文段后，就误以为是A又发出一次新的连接请求，于是就向A发出确认报文段，同意建立连接。假定不采用第三次报文握手，那么只要B发出确认，新的连接就建立了
  • 由于现在A并没有发出建立连接的请求，因此不会理睬B的确认，也不会向B发送数据，但B却以为新的运输连接已经建立了，并一直等待A发来的数据。B的许多资源就这样白白浪费了
  • 采用三次握手连接，可以防止上述现象的发生。例如在刚才的异常情况下，A不会向B的确认发出确认，B由于收不到确认，就知道A并没有要求建立连接，于是B就不会再建立连接

为什么 TIME_WAIT 状态需要 2MSL？

  • 保证Client发送的最后一个ACK报文段能够到达Server：Server如果没有收到ACK，将不断重复发送FIN，所以Client不能立即关闭，它必须确认Server接收到了该ACK
  • 防止已失效连接的请求报文段出现在本次连接中：A在发送完最后一个ACK报文段后，再经过2MSL时间，就可以使本连接持续时间内所产生的所有报文段都从网络中消失，这样就可以使下一个新的连接中不会出现旧连接中的请求报文段
3. I/O 多路复用

I/O 多路复用：select、poll、epoll：

参见 聊聊 IO 多路复用之 select、poll、epoll 详解 | 简书

4. IPC 通信

Linux IPC 通信方式：

5. 进程/线程
6. grep/sed/awk
7. Shell 相关
8. KVM
9. Docker
10. K8s
11. Go
package main

import (
    "fmt"
)

type Node struct {
    value int
    left  *Node
    right *Node
}

func main() {
    preOrder := []int{1, 2, 4, 7, 3, 5, 6, 8}
    inOrder := []int{4, 7, 2, 1, 5, 3, 8, 6}

    tree := constructBTree(preOrder, inOrder)

    preCatTree(tree)
    inCatTree(tree)
}

// 重建二叉树
func constructBTree(preOrder, inOrder []int) *Node {
    l := len(preOrder)
    if l == 0 {
        return nil
    }

    root := &Node{
        value: preOrder[0],
    }
    if l == 1 {
        return root
    }

    leftLen, rightLen := 0, 0
    for _, v := range inOrder {
        if v == root.value {
            break
        }
        leftLen++
    }
    rightLen = l - leftLen - 1

    if leftLen > 0 {
        fmt.Println("左子树", preOrder[1:leftLen+1], inOrder[0:leftLen])
        root.left = constructBTree(preOrder[1:leftLen+1], inOrder[0:leftLen])
    }
    if rightLen > 0 {
        fmt.Println("右子树", preOrder[leftLen+1:], inOrder[leftLen+1:])
        root.right = constructBTree(preOrder[leftLen+1:], inOrder[leftLen+1:])
    }

    return root
}

func preCatTree(t *Node) {
    fmt.Println(t.value)
    if t.left != nil {
        preCatTree(t.left)
    }
    if t.right != nil {
        preCatTree(t.right)
    }
}

func inCatTree(t *Node) {
    if t.left != nil {
        inCatTree(t.left)
    }
    fmt.Println(t.value)
    if t.right != nil {
        inCatTree(t.right)
    }
}
12. 算法
13. 数据库
14. 常见面试题
15. 计算机网络

参见 42 道计算机网络面试高频题+答案 | Linux云计算网络

基础知识

面经汇总

电信云笔试 - 牛客

1.落单的数：

package main

import (
    "fmt"
)

func main() {
    n := 0
    ans := 0
    cur := 0

    fmt.Scan(&n)

    for i := 0; i < n; i++ {
        fmt.Scan(&cur)
        ans ^= cur
    }

    fmt.Println(ans)
}

------
7
1 2 2 1 3 4 3

4

2.同构字符串：

package main

import (
    "fmt"
    "strings"
)

func main() {
    var s, s1, s2 string

    fmt.Scan(&s)
    split := strings.Split(s, ";")
    s1, s2 = split[0], split[1]

    len1 := len(s1)
    len2 := len(s2)
    if len1 != len2 {
        fmt.Println("False")
        return
    } else if len1 == 1 {
        fmt.Println("True")
        return
    }

    record := make(map[byte]byte)

    for i := 0; i < len1; i++ {
        if record[s1[i]] == s2[i] {
            continue
        } else if record[s1[i]] == 0 {
            record[s1[i]] = s2[i]
        } else {
            fmt.Println("False")
            return
        }
    }

    fmt.Println("True")
    return
}

------
ababa;ststs

True

3.最大连续子序列的和：

package main

import (
    "fmt"
)

func main() {
    array := make([]int, 0)

    var a int
    var ch byte
    fmt.Scan(&ch)

    for {
        n, err := fmt.Scanf("%d", &a)
        if n == 0 {
            break
        }
        if err != nil {
            fmt.Println(err)
            break
        }
        array = append(array, a)
    }

    fmt.Println(search(array))
}

func search(a []int) int {
    l := len(a)
    curSum := 0
    maxSum := 0

    for i := 0; i < l; i++ {
        curSum = 0
        for j := i; j < l; j++ {
            curSum += a[j]
            if curSum > maxSum {
                maxSum = curSum
            }
        }
    }

    return maxSum
}

------
[2, 4, -2, 5, -6]

9

字节跳动 - 牛客

1.距离最近的厕所：

package main

import (
    "fmt"
)

var (
    n     int
    s     string
    wcDis [1000000]int
)

const (
    maxDistance int = 1000001
)

// 离最近厕所的距离，O代表有厕所，保证至少有一个厕所
//
// [Input]
// 9
// XXOXOOXXX
//
// [Output]
// 2 1 0 1 0 0 1 2 3
func main() {
    fmt.Scan(&n)
    fmt.Scan(&s)

    for i := 0; i < 1000000; i++ {
        wcDis[i] = maxDistance
    }

    for i := 0; i < n; i++ {
        findWC(i)
    }
}

func findWC(cur int) {
    if s[cur] == 'O' {
        wcDis[cur] = 0
        fmt.Printf("%d ", 0)
        return
    }
    curDis := min(searchLeft(cur), searchRight(cur))
    wcDis[cur] = curDis
    fmt.Printf("%d ", curDis)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func searchLeft(cur int) int {
    if cur == 0 {
        return maxDistance
    }
    if s[cur-1] == 'O' {
        return 1
    }
    return wcDis[cur-1] + 1
}

func searchRight(cur int) int {
    disRight := 0

    for i := cur + 1; i < n; i++ {
        disRight++
        if s[i] == 'O' {
            return disRight
        }
    }

    return maxDistance
}

------
9
XXOXOOXXX

2 1 0 1 0 0 1 2 3

2.考试跳过的题目：

package main

import (
    "fmt"
    "sort"
)

// 第一行: 测试用例个数
// 第二行: n, m, 分别代表题目总数、时间总数
// 输出: 至少要跳过前面的几道题
//
// [Input]
// 2
// 5 5
// 1 2 3 4 5
// 4 4
// 4 3 2 1
//
// [Output]
// 0 0 1 2 4
// 0 1 2 2
func main() {
    var total int
    fmt.Scan(&total)
    for i := 0; i < total; i++ {
        solve()
    }
}

func solve() {
    var n, m int
    fmt.Scan(&n, &m)

    questions := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&questions[i])
    }

    var curSum = 0

    for i := 0; i < n-1; i++ {
        curSum += questions[i]
        printAns(questions, i, curSum, n, m)
        fmt.Print(" ")
    }

    curSum += questions[n-1]
    printAns(questions, n-1, curSum, n, m)
    fmt.Println()
}

func printAns(questions []int, curPos, curSum, n, m int) {
    if curSum <= m {
        fmt.Print(0)
        return
    }

    prev := make([]int, curPos)
    copy(prev, questions[0:curPos])

    sort.Slice(prev, func(i, j int) bool {
        return prev[i] > prev[j]
    })

    var curGiveup = 0

    for i := 0; i < curPos; i++ {
        curSum -= prev[i]
        curGiveup++
        if curSum <= m {
            fmt.Print(curGiveup)
            return
        }
    }
}

------
2
5 5
1 2 3 4 5
4 4
4 3 2 1

0 0 1 2 4
0 1 2 2