
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]intQ10-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, ¶ms)
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