面试手撕题积累

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、

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

原文地址：https://blog.csdn.net/qq_44794715/article/details/144086070

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！