面试手撕题积累

1、实现滑动窗口限流，允许每分钟最多有100个请求

阿里一面题。

核心：
时间窗口管理：滑动窗口会根据时间流逝不断更新，需要记录请求的时间戳，并根据当前时间计算窗口内的请求数量。
限流判断：每次请求到来时，判断当前时间窗口内的请求数是否超过限制。如果没有超过限制，允许请求；如果超过限制，拒绝请求。

优化：
队列优化：如果每次都遍历 timestamps 切片来清理过期请求，当请求量大时，性能可能受到影响。为了提升性能，可以考虑使用双端队列（deque）来高效地删除最旧的请求。
并发控制：这个实现使用了 sync.Mutex 来保护共享资源的并发访问。在高并发环境下，如果请求量非常大，可以考虑其他更高效的并发控制机制，例如 sync.RWMutex 或无锁队列。

package main

import (
	"fmt"
	"sync"
	"time"
)

type SlidingWindowLimiter struct {
	// 请求时间戳队列，用来记录每个请求的时间
	timestamps []time.Time
	// 限制的最大请求数
	maxRequests int
	// 限制的时间窗口，单位为秒
	windowDuration time.Duration
	// 锁，保证并发安全
	mu sync.Mutex
}

// 创建一个新的滑动窗口限流器
func NewSlidingWindowLimiter(maxRequests int, windowDuration time.Duration) *SlidingWindowLimiter {
	return &SlidingWindowLimiter{
		timestamps:    []time.Time{},
		maxRequests:   maxRequests,
		windowDuration: windowDuration,
	}
}

// 检查是否允许请求
func (limiter *SlidingWindowLimiter) AllowRequest() bool {
	limiter.mu.Lock()
	defer limiter.mu.Unlock()

	// 当前时间
	now := time.Now()

	// 移除窗口外的请求时间戳
	limiter.cleanUp(now)

	// 如果当前请求时间戳个数小于限制，则允许请求
	if len(limiter.timestamps) < limiter.maxRequests {
		// 将当前请求的时间戳加入队列
		limiter.timestamps = append(limiter.timestamps, now)
		return true
	}

	// 否则，拒绝请求
	return false
}

// 清理过期的请求时间戳
func (limiter *SlidingWindowLimiter) cleanUp(now time.Time) {
	// 移除超出时间窗口的请求
	windowStart := now.Add(-limiter.windowDuration)
	for len(limiter.timestamps) > 0 && limiter.timestamps[0].Before(windowStart) {
		limiter.timestamps = limiter.timestamps[1:]
	}
}

func main() {
	// 创建一个滑动窗口限流器，限制每分钟最多100个请求
	limiter := NewSlidingWindowLimiter(100, time.Minute)

	// 模拟请求
	for i := 0; i < 120; i++ {
		allowed := limiter.AllowRequest()
		if allowed {
			fmt.Printf("Request %d allowed\n", i+1)
		} else {
			fmt.Printf("Request %d denied (too many requests)\n", i+1)
		}

		// 模拟请求间隔，假设每500毫秒发起一个请求
		time.Sleep(500 * time.Millisecond)
	}
}

2、把三千一十万五千零一十转换成对应数字

package main

import (
    "fmt"
)

func chineseToNumber(text string) int {
    numbersMap := map[rune]int{
        '零': 0, '一': 1, '二': 2, '三': 3, '四': 4, '五': 5, '六': 6, '七': 7, '八': 8, '九': 9,
        '十': 10, '百': 100, '千': 1000, '万': 10000,
    }

    total := 0
    num := 0
    for _, char := range text {
        if val, ok := numbersMap[char]; ok {
            if val < 10 {
                num += val
            } else {
                if num == 0 {
                    num = 1
                }
                num *= val
            }
        } else {
            total += num
            num = 0
        }
    }

    total += num
    return total
}

func main() {
    text := "三千一十万五千零一十"
    number := chineseToNumber(text)
    fmt.Println(number)
}

3、用两个队列去模拟栈

package main

import "fmt"

type Stack struct {
    mainQueue    []int
    auxQueue     []int
}

func NewStack() *Stack {
    return &Stack{
        mainQueue: make([]int, 0),
        auxQueue:  make([]int, 0),
    }
}

func (s *Stack) Push(val int) {
    // 将元素推入主队列
    s.mainQueue = append(s.mainQueue, val)
}

func (s *Stack) Pop() int {
    if len(s.mainQueue) == 0 {
        return -1
    }

    // 将主队列中除了最后一个元素外的其他元素依次出队并放入辅助队列
    for len(s.mainQueue) > 1 {
        val := s.mainQueue[0]
        s.mainQueue = s.mainQueue[1:]
        s.auxQueue = append(s.auxQueue, val)
    }

    // 弹出最后一个元素作为栈顶元素
    popVal := s.mainQueue[0]
    s.mainQueue = s.mainQueue[:0]

    // 交换主队列和辅助队列，以便下一次操作
    s.mainQueue, s.auxQueue = s.auxQueue, s.mainQueue

    return popVal
}

func main() {
    stack := NewStack()

    stack.Push(1)
    stack.Push(2)
    stack.Push(3)

    fmt.Println(stack.Pop()) // Output: 3
    fmt.Println(stack.Pop()) // Output: 2
}

4、用两个栈模拟队列

package main

import "fmt"

type Queue struct {
    stack1 []int
    stack2 []int
}

func NewQueue() *Queue {
    return &Queue{
        stack1: make([]int, 0),
        stack2: make([]int, 0),
    }
}

func (q *Queue) Enqueue(val int) {
    // 将元素推入stack1
    q.stack1 = append(q.stack1, val)
}

func (q *Queue) Dequeue() int {
    if len(q.stack2) == 0 {
        // 如果stack2为空，将stack1中的元素依次弹出并推入stack2
        for len(q.stack1) > 0 {
            val := q.stack1[len(q.stack1)-1]
            q.stack1 = q.stack1[:len(q.stack1)-1]
            q.stack2 = append(q.stack2, val)
        }
    }

    if len(q.stack2) == 0 {
        return -1 // 队列为空
    }

    // 弹出stack2的栈顶元素作为出队元素
    popVal := q.stack2[len(q.stack2)-1]
    q.stack2 = q.stack2[:len(q.stack2)-1]

    return popVal
}

func main() {
    queue := NewQueue()

    queue.Enqueue(1)
    queue.Enqueue(2)
    queue.Enqueue(3)

    fmt.Println(queue.Dequeue()) // Output: 1
    fmt.Println(queue.Dequeue()) // Output: 2
    fmt.Println(queue.Dequeue()) // Output: 3
}

5、判断B树是否为A树的子结构

package main

import "fmt"

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

func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil {
        return false
    }

    return isSubTree(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func isSubTree(A *TreeNode, B *TreeNode) bool {
    if B == nil {
        return true
    }
    if A == nil || A.Val != B.Val {
        return false
    }

    return isSubTree(A.Left, B.Left) && isSubTree(A.Right, B.Right)
}

6、实现timer类，功能是注册函数定期执行

package main

import (
	"fmt"
	"time"
)

type Timer struct {
	interval time.Duration
	ticker   *time.Ticker
	done     chan bool
}

func NewTimer(interval time.Duration) *Timer {
	return &Timer{
		interval: interval,
		ticker:   nil,
		done:     make(chan bool),
	}
}

func (t *Timer) Start() {
	t.ticker = time.NewTicker(t.interval)
	go func() {
		for {
			select {
			case <-t.ticker.C:
				fmt.Println("Timer tick")
				// 在这里添加想要执行的函数
			case <-t.done:
				t.ticker.Stop()
				return
			}
		}
	}()
}

func (t *Timer) Stop() {
	t.done <- true
}

func main() {
	timer := NewTimer(1 * time.Second)
	timer.Start()

	time.Sleep(5 * time.Second)
	timer.Stop()

	fmt.Println("Timer stopped")
}

7、生产者消费者

基本实现：

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func producer(ch chan int) {
	for {
		num := rand.Intn(100)
		ch <- num
		time.Sleep(time.Duration(rand.Intn(1000)) * time.Millisecond)
	}
}

func consumer(ch chan int) {
	for {
		num := <-ch
		fmt.Println("Consumed:", num)
		time.Sleep(time.Duration(rand.Intn(1000)) * time.Millisecond)
	}
}

func main() {
	rand.Seed(time.Now().Unix())
	
	ch := make(chan int)

	go producer(ch)
	go consumer(ch)

	time.Sleep(5 * time.Second) // Let the program run for a few seconds
}

8、三个协程轮流打印 abc

参考：https://juejin.cn/post/7262243685898436667

// 使用三个管道实现三个协程同步顺序打印a b c  
func printLetter(letter string, prevCh, nextCh chan struct{}, wg *sync.WaitGroup) {  
    defer wg.Done()  

    for i := 0; i < 10; i++ {  
        // 等待上一个协程通知  
        <-prevCh  
        fmt.Print(letter)  
        // 发送信号给下一个协程  
        nextCh <- struct{}{}  
    }
    
    if letter == "a" {
        <-prevCh
    }
}


func main() {
    var wg sync.WaitGroup  
    wg.Add(3)  

    ch1 := make(chan struct{})  
    ch2 := make(chan struct{})  
    ch3 := make(chan struct{})  

    go printLetter("a", ch1, ch2, &wg)  
    go printLetter("b", ch2, ch3, &wg)  
    go printLetter("c", ch3, ch1, &wg)  

    // 启动第一个协程  
    ch1 <- struct{}{}  

    wg.Wait()
}

进阶：26个字母

// 使用26个协程分别顺序打印字母表  
func printAlphabet(letter rune, prevCh, nextCh chan struct{}, wg *sync.WaitGroup) {  
    defer wg.Done()
    for i := 0; i < 10; i++ {  
        <-prevCh
        fmt.Printf("%c", letter)
        nextCh <- struct{}{}
    }  
    // 第一个协程必须要退出，因为最后一个协程往管道里面写入数据了，需要破环而出不然就会死锁  
    if letter == 'a' {
        <-prevCh
    }
}
  
func main() {  
    var wg sync.WaitGroup
    wg.Add(26)

    var signals []chan struct{}  
    for i := 0; i < 26; i++ {  
        signals = append(signals, make(chan struct{}))  
    }  

    for letter, i := 'a', 0; letter <= 'z'; letter++ {  
        if letter == 'z' {  
            go printAlphabet(letter, signals[i], signals[0], &wg)
            break
        }
        go printAlphabet(letter, signals[i], signals[i+1], &wg)  
        i++
    }

    // 启动第一个协程  
    signals[0] <- struct{}{}  
    wg.Wait()  
}

9、排序

快排：

时间复杂度分析：平均：O(n log n)，因为每次分区将数组大约分成两部分，而每次分区的时间复杂度是 O(n)，递归深度是 O(log n)。最坏：O(n^2)，发生在每次选择的基准元素都非常不理想（如每次选取最小或最大元素）
空间复杂度：O(log n)，因为递归的深度是 O(log n)，每次递归都会使用栈空间。
优化：随机选择基准元素；取中；

package main
import "fmt"

// 快速排序
func quickSort(arr []int) {
    if len(arr) < 2 {
        return // 基本情况：如果数组长度小于2，已经是排序好的
    }

    // 选择基准元素，通常选取数组的最后一个元素
    pivotIndex := len(arr) - 1
    pivot := arr[pivotIndex]

    // 使用分区函数
    left, right := 0, pivotIndex-1
    for left <= right {
        // 找到一个大于等于基准的元素
        for left <= right && arr[left] < pivot {
            left++
        }
        // 找到一个小于等于基准的元素
        for left <= right && arr[right] > pivot {
            right--
        }

        // 如果left和right没有交叉，交换这两个元素
        if left <= right {
            arr[left], arr[right] = arr[right], arr[left]
            left++
            right--
        }
    }

    // 将基准元素放到正确的位置
    arr[left], arr[pivotIndex] = arr[pivotIndex], arr[left]

    // 对基准左边和右边的子数组分别进行递归排序
    quickSort(arr[:left])  // 基准左边部分
    quickSort(arr[left+1:]) // 基准右边部分
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    fmt.Println("原始数组:", arr)

    quickSort(arr)

    fmt.Println("排序后的数组:", arr)
}

堆排：

时间复杂度：构建最大堆：O(n)，因为 heapify 是 O(log n)，但总的操作次数是 O(n)。排序过程：每次将堆顶元素交换到末尾，并进行堆调整，时间复杂度是 O(log n)，总共执行 n-1 次，因此排序的总时间复杂度是 O(n log n)。
空间复杂度： O(1)

package main

import "fmt"

// 堆排序
func heapSort(arr []int) {
    n := len(arr)

    // Step 1: 构建最大堆
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    // Step 2: 排序过程
    for i := n - 1; i > 0; i-- {
        // 将堆顶元素与最后一个元素交换
        arr[0], arr[i] = arr[i], arr[0]
        
        // 调整剩下的堆
        heapify(arr, i, 0)
    }
}

// heapify 是调整堆的函数，确保子树以i为根的部分是最大堆
func heapify(arr []int, n, i int) {
    largest := i       // 假设根节点是最大值
    left := 2*i + 1    // 左子节点的索引
    right := 2*i + 2   // 右子节点的索引

    // 如果左子节点比根节点大
    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    // 如果右子节点比根节点大
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    // 如果最大值不是根节点，交换并递归调整
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    fmt.Println("原始数组:", arr)

    heapSort(arr)

    fmt.Println("排后的数组:", arr)
}

归并排序：

时间复杂度：O(n log n)，其中 n 是数组的长度。每次递归会将数组分成两部分，递归深度为 O(log n)。每次合并操作的时间复杂度是 O(n)，因此总体时间复杂度是 O(n log n)。
空间复杂度：O(n)，因为需要额外的空间来存储合并后的结果数组。

package main

import "fmt"

// 合并两个有序数组
func merge(left, right []int) []int {
    var result []int
    i, j := 0, 0

    // 合并左右两个有序数组
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // 如果左数组还有剩余元素，直接添加到结果中
    for i < len(left) {
        result = append(result, left[i])
        i++
    }

    // 如果右数组还有剩余元素，直接添加到结果中
    for j < len(right) {
        result = append(result, right[j])
        j++
    }

    return result
}

// 归并排序函数
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr // 基本情况：数组长度为0或1，不需要排序
    }

    // 分割数组为左右两部分
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])  // 递归排序左边部分
    right := mergeSort(arr[mid:]) // 递归排序右边部分

    // 合并两部分
    return merge(left, right)
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    fmt.Println("原始数组:", arr)

    sortedArr := mergeSort(arr)

    fmt.Println("排序后的数组:", sortedArr)
}

参考：https://blog.csdn.net/zss192/article/details/138610657#159_32_5898