当前位置：首页 > news >正文

面试手撕题积累

news 2024/11/29 2:49:33

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

阿里一面题。

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

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

package mainimport ("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 mainimport ("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 := 0num := 0for _, char := range text {if val, ok := numbersMap[char]; ok {if val < 10 {num += val} else {if num == 0 {num = 1}num *= val}} else {total += numnum = 0}}total += numreturn total
}func main() {text := "三千一十万五千零一十"number := chineseToNumber(text)fmt.Println(number)
}

3、用两个队列去模拟栈

package mainimport "fmt"type Stack struct {mainQueue    []intauxQueue     []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.mainQueuereturn popVal
}func main() {stack := NewStack()stack.Push(1)stack.Push(2)stack.Push(3)fmt.Println(stack.Pop()) // Output: 3fmt.Println(stack.Pop()) // Output: 2
}

4、用两个栈模拟队列

package mainimport "fmt"type Queue struct {stack1 []intstack2 []int
}func NewQueue() *Queue {return &Queue{stack1: make([]int, 0),stack2: make([]int, 0),}
}func (q *Queue) Enqueue(val int) {// 将元素推入stack1q.stack1 = append(q.stack1, val)
}func (q *Queue) Dequeue() int {if len(q.stack2) == 0 {// 如果stack2为空，将stack1中的元素依次弹出并推入stack2for 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: 1fmt.Println(queue.Dequeue()) // Output: 2fmt.Println(queue.Dequeue()) // Output: 3
}

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

package mainimport "fmt"type TreeNode struct {Val   intLeft  *TreeNodeRight *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 mainimport ("fmt""time"
)type Timer struct {interval time.Durationticker   *time.Tickerdone     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 mainimport ("fmt""math/rand""time"
)func producer(ch chan int) {for {num := rand.Intn(100)ch <- numtime.Sleep(time.Duration(rand.Intn(1000)) * time.Millisecond)}
}func consumer(ch chan int) {for {num := <-chfmt.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++ {  <-prevChfmt.Printf("%c", letter)nextCh <- struct{}{}}  // 第一个协程必须要退出，因为最后一个协程往管道里面写入数据了，需要破环而出不然就会死锁  if letter == 'a' {<-prevCh}
}func main() {  var wg sync.WaitGroupwg.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()  
}