設計搜尋自動補全（Search Autocomplete）

public class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = new();
    public bool IsEndOfWord { get; set; }
    // 預先計算此前綴下的 Top-K 結果，避免查詢時遍歷
    public List<(string Query, long Frequency)> TopK { get; set; } = new();
}
 
public class AutocompleteTrie
{
    private readonly TrieNode _root = new();
    private const int K = 10;
 
    public void Insert(string query, long frequency)
    {
        var node = _root;
        foreach (var ch in query)
        {
            if (!node.Children.ContainsKey(ch))
                node.Children[ch] = new TrieNode();
 
            node = node.Children[ch];
            // 更新每個前綴節點的 Top-K
            UpdateTopK(node, query, frequency);
        }
        node.IsEndOfWord = true;
    }
 
    public List<string> Search(string prefix)
    {
        var node = _root;
        foreach (var ch in prefix)
        {
            if (!node.Children.ContainsKey(ch))
                return new List<string>();
            node = node.Children[ch];
        }
        return node.TopK.Select(x => x.Query).ToList();
    }
 
    private void UpdateTopK(TrieNode node, string query, long freq)
    {
        var existing = node.TopK.FindIndex(x => x.Query == query);
        if (existing >= 0) node.TopK.RemoveAt(existing);
 
        node.TopK.Add((query, freq));
        node.TopK = node.TopK.OrderByDescending(x => x.Frequency)
                             .Take(K).ToList();
    }
}

class AutocompleteClient {
  private cache = new Map<string, string[]>();
  private debounceTimer: ReturnType<typeof setTimeout> | null = null;
 
  onInput(prefix: string, callback: (results: string[]) => void): void {
    // 先檢查本地快取
    if (this.cache.has(prefix)) {
      callback(this.cache.get(prefix)!);
      return;
    }
 
    // Debounce：等用戶停止打字 150ms 再發請求
    if (this.debounceTimer) clearTimeout(this.debounceTimer);
 
    this.debounceTimer = setTimeout(async () => {
      const results = await fetch(`/api/autocomplete?q=${prefix}`)
        .then((res) => res.json());
 
      // 快取結果
      this.cache.set(prefix, results);
      callback(results);
    }, 150);
  }
}

from collections import Counter
from datetime import datetime, timedelta
 
class DataCollectionService:
    """收集搜尋查詢，定期聚合後觸發 Trie 重建"""
 
    def __init__(self):
        self.buffer: list[str] = []
        self.frequency_store: Counter = Counter()
 
    def record_query(self, query: str) -> None:
        """每次搜尋時記錄（寫入 Kafka/Log）"""
        self.buffer.append(query.lower().strip())
 
    def aggregate(self) -> dict[str, int]:
        """每 N 分鐘聚合一次頻率"""
        self.frequency_store.update(self.buffer)
        self.buffer.clear()
 
        # 套用時間衰減：7 天前的搜尋權重降低
        # 實務上用 Exponential Decay 或 Sliding Window
        return dict(self.frequency_store.most_common(100_000))
 
    def trigger_trie_rebuild(self, freq_data: dict[str, int]) -> None:
        """將聚合結果送給 Trie Builder 重建"""
        # 離線建構新 Trie → 原子替換線上 Trie
        pass