面试题集锦:算法与手写结构

面试题集锦:算法与手写结构

Hello,我是小兔大白糖。 这篇整理面试口述与高频追问要点,方便对照站内同主题通识文。


正文

目标岗位:大型加密货币交易所 · 后端(风控方向)
题目数:15 题
编程语言:Go 为主,通用题目给思路
策略:每题给 5 分钟能写出的完整代码版本


Q1-Q3:数据结构设计型(交易场景)


Q1:线程安全的最近 N 笔成交价缓存

// 需求:高频写入 + 高频读取最近 N 笔成交价
// 方案:环形缓冲区 + sync.RWMutex
 
type PriceCache struct {
    mu     sync.RWMutex
    buf    []float64
    size   int
    cursor int
    count  int  // 已写入数量(< size 时不满)
}
 
func NewPriceCache(n int) *PriceCache {
    return &PriceCache{buf: make([]float64, n), size: n}
}
 
func (c *PriceCache) Add(price float64) {
    c.mu.Lock()
    c.buf[c.cursor] = price
    c.cursor = (c.cursor + 1) % c.size
    if c.count < c.size {
        c.count++
    }
    c.mu.Unlock()
}
 
// GetRecent 返回最近 n 笔(n <= size),按时间正序
func (c *PriceCache) GetRecent(n int) []float64 {
    c.mu.RLock()
    defer c.mu.RUnlock()
    if n > c.count {
        n = c.count
    }
    result := make([]float64, n)
    start := (c.cursor - n + c.size) % c.size
    for i := 0; i < n; i++ {
        result[i] = c.buf[(start+i)%c.size]
    }
    return result
}

复杂度:写入 O(1),读取 O(N)。优化:如果需要最近 N 的平均价,可以在 Add 时增量维护 sum。


Q2:滑动窗口——返回过去 1 分钟内的最高/最低/最新价

// 需求:tick 数据流 → 查询过去 1 分钟的 OHLC
// 方案:Deque(双端队列)维护窗口,保持单调性
 
type Tick struct {
    Price     float64
    Timestamp int64 // 毫秒时间戳
}
 
type SlidingWindow struct {
    windowMs int64
    maxDeque []Tick // 单调递减(队头最大)
    minDeque []Tick // 单调递增(队头最小)
    ticks    []Tick // 所有 tick(用于清理过期)
}
 
func NewSlidingWindow(windowMs int64) *SlidingWindow {
    return &SlidingWindow{windowMs: windowMs}
}
 
func (w *SlidingWindow) Add(t Tick) {
    now := t.Timestamp
    // 1. 清理过期数据
    cutoff := now - w.windowMs
    w.ticks = w.filterExpired(w.ticks, cutoff)
    // 清理 deque 中的过期项(略)
 
    // 2. 加入新 tick
    w.ticks = append(w.ticks, t)
 
    // 3. 维护 max deque:队尾比新值小的全弹出
    for len(w.maxDeque) > 0 && w.maxDeque[len(w.maxDeque)-1].Price <= t.Price {
        w.maxDeque = w.maxDeque[:len(w.maxDeque)-1]
    }
    w.maxDeque = append(w.maxDeque, t)
 
    // 4. 维护 min deque:队尾比新值大的全弹出
    for len(w.minDeque) > 0 && w.minDeque[len(w.minDeque)-1].Price >= t.Price {
        w.minDeque = w.minDeque[:len(w.minDeque)-1]
    }
    w.minDeque = append(w.minDeque, t)
}
 
func (w *SlidingWindow) GetMax() float64 {
    if len(w.maxDeque) == 0 { return 0 }
    return w.maxDeque[0].Price
}
 
func (w *SlidingWindow) GetMin() float64 {
    if len(w.minDeque) == 0 { return 0 }
    return w.minDeque[0].Price
}
 
func (w *SlidingWindow) GetLatest() float64 {
    if len(w.ticks) == 0 { return 0 }
    return w.ticks[len(w.ticks)-1].Price
}

复杂度:每个 tick 均摊 O(1)(每个元素入队出队各一次),查询 O(1)。


Q3:分布式 Rate Limiter

// 需求:每个用户每秒最多 N 个请求,分布式环境
// 方案:Redis 滑动窗口(ZSET)+ 本地预取优化
 
// Redis Lua 版本(分布式精确)
const luaScript = `
local key = KEYS[1]          -- ratelimit:user:123
local now = tonumber(ARGV[1]) -- 毫秒时间戳
local window = tonumber(ARGV[2]) -- 窗口大小 ms
local limit = tonumber(ARGV[3])  -- 限制次数
 
-- 清理窗口外数据
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
local count = redis.call('ZCARD', key)
 
if count < limit then
    redis.call('ZADD', key, now, now .. ':' .. math.random())
    redis.call('PEXPIRE', key, window)
    return 1  -- 允许
else
    return 0  -- 拒绝
end
`
 
// Go 调用版本
func AllowRequest(ctx context.Context, rdb *redis.Client, userID string, limit int) (bool, error) {
    now := time.Now().UnixMilli()
    result, err := rdb.Eval(ctx, luaScript,
        []string{"ratelimit:" + userID},
        now, 1000, limit).Int()
    return result == 1, err
}

分布式优化:100 QPS 限制 → 本地每 100ms 预取 10 个令牌(批量减 count),减少 Redis 调用 99%。


Q4-Q9:经典 LeetCode


Q4:两数之和(Go)

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return []int{j, i}
        }
        seen[v] = i
    }
    return nil
}
// O(N) 时间,O(N) 空间

Q5:合并两个有序链表(Go)

type ListNode struct {
    Val  int
    Next *ListNode
}
 
func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next, l1 = l1, l1.Next
        } else {
            cur.Next, l2 = l2, l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil { cur.Next = l1 }
    if l2 != nil { cur.Next = l2 }
    return dummy.Next
}
// O(M+N),不需要额外空间

Q6 + Q12 + Q13:LRU Cache(Go,get/put O(1))

// 核心:双向链表 + HashMap
 
type Node struct {
    key, value int
    prev, next *Node
}
 
type LRUCache struct {
    cap  int
    size int
    head, tail *Node // 哨兵节点,head.next=最新,tail.prev=最旧
    cache map[int]*Node
}
 
func Constructor(capacity int) LRUCache {
    l := LRUCache{cap: capacity, cache: make(map[int]*Node)}
    l.head, l.tail = &Node{}, &Node{}
    l.head.next, l.tail.prev = l.tail, l.head
    return l
}
 
func (l *LRUCache) Get(key int) int {
    if node, ok := l.cache[key]; ok {
        l.moveToHead(node)
        return node.value
    }
    return -1
}
 
func (l *LRUCache) Put(key, value int) {
    if node, ok := l.cache[key]; ok {
        node.value = value
        l.moveToHead(node)
        return
    }
    node := &Node{key: key, value: value}
    l.cache[key] = node
    l.addToHead(node)
    l.size++
    if l.size > l.cap {
        removed := l.removeTail()
        delete(l.cache, removed.key)
        l.size--
    }
}
 
func (l *LRUCache) moveToHead(node *Node) {
    l.removeNode(node)
    l.addToHead(node)
}
 
func (l *LRUCache) removeNode(node *Node) {
    node.prev.next, node.next.prev = node.next, node.prev
}
 
func (l *LRUCache) addToHead(node *Node) {
    node.next, node.prev = l.head.next, l.head
    l.head.next.prev, l.head.next = node, node
}
 
func (l *LRUCache) removeTail() *Node {
    node := l.tail.prev
    l.removeNode(node)
    return node
}

面试讲解要点:双向链表 O(1) 删除中间节点,HashMap O(1) 定位。head/tail 哨兵简化代码。


Q7:最长不重复子串(Go)

func lengthOfLongestSubstring(s string) int {
    lastPos := make(map[byte]int)
    left, maxLen := 0, 0
    for right := 0; right < len(s); right++ {
        if pos, ok := lastPos[s[right]]; ok && pos >= left {
            left = pos + 1 // 跳过重复字符
        }
        lastPos[s[right]] = right
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
    return maxLen
}
// O(N) 时间,O(字符集大小) 空间。滑动窗口经典。

Q8:二叉树最大宽度(Go)

// 思路:BFS 层序遍历,给每个节点编号(类似堆结构)
// node.idx = 2*parent.idx + (left?1:2),宽度 = 最右 idx - 最左 idx + 1
 
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
 
type nodeWithIdx struct {
    node *TreeNode
    idx  int
}
 
func widthOfBinaryTree(root *TreeNode) int {
    if root == nil { return 0 }
    maxWidth := 0
    queue := []nodeWithIdx{{root, 1}}
    for len(queue) > 0 {
        levelSize := len(queue)
        left, right := queue[0].idx, queue[levelSize-1].idx
        maxWidth = max(maxWidth, right-left+1)
        for i := 0; i < levelSize; i++ {
            n := queue[0]; queue = queue[1:]
            if n.node.Left != nil {
                queue = append(queue, nodeWithIdx{n.node.Left, n.idx * 2})
            }
            if n.node.Right != nil {
                queue = append(queue, nodeWithIdx{n.node.Right, n.idx*2 + 1})
            }
        }
    }
    return maxWidth
}
// O(N),核心技巧:堆式编号(idx*2 和 idx*2+1)可处理空节点

Q9:第一个不重复字符索引(Go)

func firstUniqChar(s string) int {
    freq := make([]int, 26) // 假设只有小写字母
    for _, ch := range s {
        freq[ch-'a']++
    }
    for i, ch := range s {
        if freq[ch-'a'] == 1 {
            return i
        }
    }
    return -1
}
// O(N) 双遍历。若字符集不限 → 用 map[byte]int

Q10-Q14:Go 特化实现


Q10:Worker Pool 控制并发(Go)

func workerPool(jobs <-chan Job, results chan<- Result, concurrency int) {
    var wg sync.WaitGroup
    for i := 0; i < concurrency; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for job := range jobs { // channel 关闭自动退出
                results <- process(job)
            }
        }()
    }
    wg.Wait()
    close(results) // 所有 worker 结束 → 关闭 results
}
 
// 使用
jobs := make(chan Job, 100)
results := make(chan Result, 100)
go workerPool(jobs, results, 10) // 10 个并发 worker

面试要点:用带缓冲 channel 避免 worker 阻塞。close(jobs) → worker 自动退出。WaitGroup 等全部完成再 close(results)。


Q11:解析 JSON-RPC 请求(Go,10 分钟版)

type JSONRPCRequest struct {
    JSONRPC string          `json:"jsonrpc"`
    Method  string          `json:"method"`
    Params  json.RawMessage `json:"params"` // 延迟解析
    ID      interface{}     `json:"id"`
}
 
type JSONRPCResponse struct {
    JSONRPC string      `json:"jsonrpc"`
    Result  interface{} `json:"result,omitempty"`
    Error   *RPCError   `json:"error,omitempty"`
    ID      interface{} `json:"id"`
}
 
type RPCError struct {
    Code    int    `json:"code"`
    Message string `json:"message"`
}
 
func handleJSONRPC(data []byte) []byte {
    var req JSONRPCRequest
    if err := json.Unmarshal(data, &req); err != nil {
        return errorResponse(nil, -32700, "Parse error")
    }
    switch req.Method {
    case "subtract":
        var params []int
        json.Unmarshal(req.Params, &params)
        result := params[0] - params[1]
        return successResponse(req.ID, result)
    default:
        return errorResponse(req.ID, -32601, "Method not found")
    }
}
// 核心:RawMessage 延迟解析,method switch 路由

Q14:Go Channel 实现简单订单撮合

type Order struct {
    ID     string
    Side   string // "buy" or "sell"
    Price  float64
    Amount float64
}
 
func matchEngine(buyOrders <-chan Order, sellOrders <-chan Order, trades chan<- string) {
    buyBook := make(map[float64][]Order)  // price → orders(简化版)
    sellBook := make(map[float64][]Order)
 
    for {
        select {
        case order := <-buyOrders:
            // 尝试匹配卖盘
            if matched := tryMatch(order, sellBook); matched != "" {
                trades <- matched
            } else {
                buyBook[order.Price] = append(buyBook[order.Price], order)
            }
        case order := <-sellOrders:
            if matched := tryMatch(order, buyBook); matched != "" {
                trades <- matched
            } else {
                sellBook[order.Price] = append(sellBook[order.Price], order)
            }
        }
    }
}
 
func tryMatch(order Order, book map[float64][]Order) string {
    // 简化版:买价 >= 卖价 → 成交
    // 真实实现需要排序的价格优先+时间优先
    return ""
}

面试要点:Channel 天然适合订单流。核心 select 多路复用。说明"真实撮合会用 ordered map(red-black tree)保证价格优先"。


Q15:百万级 Metrics 内存数据结构设计

// 需求:每秒百万级写入 + 快速查询任意指标
// 方案:分段无锁 RingBuffer + atomic
 
type MetricPoint struct {
    Timestamp int64
    Value     float64
}
 
type MetricStore struct {
    name    string
    shards  [256]*Shard  // 256 分片,减少竞争
}
 
type Shard struct {
    buffer []MetricPoint // 环形 buffer
    cursor uint64        // atomic,无锁写入
    size   int
}
 
func (s *Shard) Write(timestamp int64, value float64) {
    idx := atomic.AddUint64(&s.cursor, 1) % uint64(s.size)
    s.buffer[idx] = MetricPoint{Timestamp: timestamp, Value: value}
}
 
func (s *Shard) ReadRecent(n int) []MetricPoint {
    cursor := atomic.LoadUint64(&s.cursor)
    // 返回最近 n 个点
    return s.buffer[cursor-uint64(n)+1 : cursor+1]
}
 
// 查询聚合:如 1 分钟内平均值
func (m *MetricStore) QueryAvg(start, end int64) float64 {
    var sum float64
    var count int
    for _, shard := range m.shards {
        for _, p := range shard.buffer {
            if p.Timestamp >= start && p.Timestamp <= end {
                sum += p.Value
                count++
            }
        }
    }
    if count == 0 { return 0 }
    return sum / float64(count)
}

面试要点:256 分片 → 256 路并发写入无竞争。atomic cursor → 无锁。预聚合(可按 1min 增量维护 sum)比实时扫描更快。


总结

缓存结构 → RingBuffer + RWMutex(Q1)
滑动窗口 → Deque 单调维护(Q2)
限流器   → Redis ZSET Lua 滑动窗口(Q3)
LRU      → HashMap + 双向链表(Q6/12/13)
滑动窗口 → 双指针 + map 记位置(Q7)
二叉树宽 → BFS + 堆式编号(Q8)
WorkerPool → 带缓冲 channel + WaitGroup(Q10)
JSON-RPC → RawMessage 延迟解析 + switch 路由(Q11)
撮合     → select 双边 channel(Q14)
Metrics  → 分片 RingBuffer + atomic 无锁(Q15)

🎉 全 17 个 Batch、330 题,全部完成!
文件位置:batch-docs/b1-*.md ~ batch-docs/b17-*.md