测试

一.查写复杂度

对象	查找	插入	删除
arrary	O(1)	O(n)	O(n)
link list	O(n)	O(n)	O(n)
stack	O(n)	O(1)	O(1)
queue	O(n)	O(1)	O(1)
hash table	O(1)	O(1)	O(1)
binary treet	O(n)	O(n)	O(n)

二.二叉树

数据结构

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

1.前序遍历

func firstorderTraversal(root *TreeNode) []int {
    arr := make([]int, 0)
    firstorder(root, &arr)
    return arr
}

func firstorder(root *TreeNode, arr *[]int) {
    if root == nil {
        return
    }
    *arr = append(*arr, root.Val)
    firstorder(root.Left, arr)
    firstorder(root.Right, arr)
}

中序遍历

func inorderTraversal(root *TreeNode) []int {
    inorderArr := make([]int, 0)
    inorder(root,&inorderArr)
    return inorderArr
}
func inorder(root *TreeNode,inorderArr *[]int) {
    if root == nil {
        return
    }
    inorder(root.Left,inorderArr)
    *inorderArr = append(*inorderArr, root.Val)
    inorder(root.Right,inorderArr)
}

后续遍历

func postorderTraversal(root *TreeNode) []int {
    arr := make([]int, 0)
    postorder(root, &arr)
    return arr
}

func postorder(root *TreeNode, arr *[]int) {
    if root == nil {
        return
    }
    postorder(root.Left, arr)
    postorder(root.Right, arr)
    *arr = append(*arr, root.Val)
}

BFS

func levelOrder(root *TreeNode) [][]int {
    arr := make([][]int, 0)
    nodeArr := make([]*TreeNode, 0)
    if root != nil {
        nodeArr = append(nodeArr, root)
    }
    for len(nodeArr) > 0 {
        tempArr := make([]int, 0)
        tempNodeArr := make([]*TreeNode, 0)
        for _, value := range nodeArr {
            tempArr = append(tempArr, value.Val)
            if value.Left != nil {
                tempNodeArr = append(tempNodeArr, value.Left)
            }
            if value.Right != nil {
                tempNodeArr = append(tempNodeArr, value.Right)
            }
        }
        arr = append(arr, tempArr)
        nodeArr = tempNodeArr
    }
    return arr
}

DFS
与先序遍历相同

三.概念陈述

UDP/TCP/HTTP/SSL

TCP
面向链接的传输层协议,面向连接就是在正式通信前必须要与对方建立起连接。
UDP
面向非链接的传输层协议
SSL
SSL安全套接字层在传输层与应用层之间对网络连接进行加密认证。介于tcp和http之间
http
超文本传输协议，信息是明文传输。应用层协议

big/little endian

1）Little-endian：将低序字节存储在起始地址（低位编址）
2）Big-endian：将高序字节存储在起始地址（高位编址）

unicode/utf8/ascii

ASCALL
一个字节一共可以用来表示256种不同的状态，每一个状态对应一个符号，就是256个符号，从00000000到11111111。
Unicode
将世界上所有的符号都纳入其中。每一个符号都给予一个独一无二的编码只是一个符号集，它只规定了符号的二进制代码，却没有规定这个二进制代码应该如何存储。
UTF-8
就是在互联网上使用最广的一种 Unicode 的实现方式
1）对于单字节的符号，字节的第一位设为0，后面7位为这个符号的 Unicode 码。因此对于英语字母，UTF-8 编码和 ASCII 码是相同的
2）对于n字节的符号（n > 1），第一个字节的前n位都设为1，第n + 1位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的 Unicode 码。

RPC

RPC是远程过程调用，它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。

thread/process

process
进程是程序系统进行资源分配的独立实体， 且每个进程拥有独立的栈空间和堆空间。
thread
一个进程可以拥有多个线程，每个线程使用其所属进程的栈空间。线程是CPU独立运行和独立调度的基本单位。

compiler

一种语言（通常为高级语言）翻译为另一种语言（通常为低级语言）的程序

design pattern

设计模式是解决问题中抽象出来的通用方法模板,常用的有观察者模式,代理模式,单例模式等

recursion

函数自己调用自己

binary-search

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

quick-sort

快速排序使用分治法策略來把一個序列（list）分為较小和较大的2个子序列，然后递归地排序两个子序列。

linker-loader

链接器
把不同部分代码和数据,收集、组合成一个可加载可执行的文件。
加载器
把可执行文件装入内存并执行。

4.问答

1.解释执行过程

package main
import "fmt"
func main() {
  fmt.Println("hello, world!")
}

通过go run -x hello.go 查看执行过程

• 创建临时目录
• 查找依赖信息
• 执行源代码编译
• 收集链接库文件
• 生成可执行文件
• 加载运行可执行文件
• 通过系统调用将用户态字符拷贝到内核态输出到设备终端

package main

import (
    "context"
    "fmt"
    "os"
    "os/signal"
    "sync"
    "sync/atomic"
    "time"
)

var (
    interval  = 30 * time.Second
    pingCount int64
    pongCount int64
    wg        = &sync.WaitGroup{}
)

func main() {
    wg.Add(3)
    pingC := make(chan string)
    pongC := make(chan string)
    ctx, cancel := context.WithCancel(context.Background())
    go ping(pingC, pongC, ctx)
    go pong(pingC, pongC, ctx)
    go daemon(ctx)
    c := make(chan os.Signal)
    signal.Notify(c, os.Interrupt)
    <-c
    cancel()
    wg.Wait()
    fmt.Printf("all groutine done!\n")

}

func ping(pingC, pongC chan string, ctx context.Context) {
    defer wg.Done()
    for {
        select {
        case <-time.After(interval):
            pingC <- "ping"
        case <-pongC:
            atomic.AddInt64(&pongCount, 1)
        case <-ctx.Done():
            close(pingC)
            fmt.Println("ping End")
            return
        }

    }

}

func pong(pingC, pongC chan string, ctx context.Context) {
    defer wg.Done()
    for {
        select {
        case <-pingC:
            atomic.AddInt64(&pingCount, 1)
            pongC <- "pong"
        case <-ctx.Done():
            close(pongC)
            fmt.Println("pong End")
            return
        }
    }

}

func daemon(ctx context.Context) {
    defer wg.Done()
    second := 0
    input := ""
    for {
        select {
        case <-ctx.Done():
            fmt.Println("daemon End")
            return
        default:
            fmt.Scanln(&input)
            switch input {
            case "pingCount":
                fmt.Println(pingCount)
            case "pongCount":
                fmt.Println(pongCount)
            case "interval":
                fmt.Println("请输入频率")
                fmt.Scanln(&second)
                interval = time.Duration(second) * time.Second
                fmt.Println(interval)

            }
        }
        input = ""
    }
}

package main

import (
    "fmt"
    "strconv"
)

var (
    arr      = make([]string, 0)
    labelArr = []string{"+", "-", "*", "/"}
)

func main() {
    str := "105"
    num := 5
    arr = make([]string, 0)
    len := len(str)
    if len < 2 {
        fmt.Println(arr)
        return
    }
    trase(str, num)
    fmt.Println(arr)
}

func trase(str string, num int) {
    len := len(str)
    if len < 2 {
        return
    }
    for i := 0; i < len-1; i++ {
        index := i + 1
        tempStr := str[index:len]
        preNum, _ := strconv.Atoi(str[0:index])
        lastNum, _ := strconv.Atoi(tempStr)
        if preNum+lastNum != num {
            trase(str[index:len], num-preNum)
        } else {
            arr = append(arr, str[0:index]+"+"+tempStr+"="+strconv.FormatInt(int64(num), 10))
        }
        if preNum-lastNum != num {
            trase(str[index:len], num+preNum)
        } else {
            arr = append(arr, str[0:index]+"-"+tempStr+"="+strconv.FormatInt(int64(num), 10))
        }

        if preNum > 0 && preNum*lastNum != num {
            trase(str[index:len], num/preNum)
        } else {
            if preNum > 0 {
                arr = append(arr, str[0:index]+"*"+tempStr+"="+strconv.FormatInt(int64(num), 10))
            }
        }

        if lastNum > 0 && preNum/lastNum != num {
            trase(str[index:len], num*preNum)
        } else {
            arr = append(arr, str[0:index]+"/"+tempStr+"="+strconv.FormatInt(int64(num), 10))
        }
    }
}