Typeahead: tries and top-k per prefix

Python 3.14 · main.py

K = 3
LOG = [
    ("bluetooth speaker", 9400),
    ("black shoes", 8100),
    ("backpack", 7300),
    ("blue jeans", 6900),
    ("blue shirt", 4700),
    ("battery", 4400),
    ("bag", 3900),
    ("blue saree", 3300),
    ("cable", 8800),
    ("camera", 7700),
    ("candle", 2100),
]


class Node:
    def __init__(self) -> None:
        self.children: dict[str, Node] = {}
        self.top: list[tuple[int, str]] = []


def insert(root: Node, query: str, count: int) -> None:
    # Offer the query to every node on its path, and keep each node's best K.
    node = root
    for ch in query:
        node = node.children.setdefault(ch, Node())
        node.top = sorted([*node.top, (count, query)], key=lambda e: (-e[0], e[1]))[:K]


def find(root: Node, prefix: str) -> Node | None:
    node = root
    for ch in prefix:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node


def size(node: Node) -> int:
    return 1 + sum(size(child) for child in node.children.values())


root = Node()
for query, count in LOG:
    insert(root, query, count)
print(f"{len(LOG)} queries, {size(root) - 1} trie nodes, top {K} kept at each node")
for prefix in ["b", "bl", "blu", "blue ", "c", "x"]:
    node = find(root, prefix)
    if node is None:
        print(f'  "{prefix}" -> no suggestions')
    else:
        shown = ", ".join(f"{q} ({c})" for c, q in node.top)
        print(f'  "{prefix}" -> {shown}; {size(node)} nodes below')

In Python: sorted with the key (-count, query) puts the most searched first and breaks ties by query, and slicing keeps the best K; setdefault creates a child the first time a character appears.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const K = 3;
const LOG = [
  ["bluetooth speaker", 9400],
  ["black shoes", 8100],
  ["backpack", 7300],
  ["blue jeans", 6900],
  ["blue shirt", 4700],
  ["battery", 4400],
  ["bag", 3900],
  ["blue saree", 3300],
  ["cable", 8800],
  ["camera", 7700],
  ["candle", 2100],
];

const newNode = () => ({ children: new Map(), top: [] });
const better = (a, b) => b[0] - a[0] || (a[1] < b[1] ? -1 : 1);

function insert(root, query, count) {
  // Offer the query to every node on its path, and keep each node's best K.
  let node = root;
  for (const ch of query) {
    if (!node.children.has(ch)) node.children.set(ch, newNode());
    node = node.children.get(ch);
    node.top.push([count, query]);
    node.top.sort(better);
    if (node.top.length > K) node.top.pop();
  }
}

function find(root, prefix) {
  let node = root;
  for (const ch of prefix) {
    node = node.children.get(ch);
    if (!node) return null;
  }
  return node;
}

const size = (node) => [...node.children.values()].reduce((n, child) => n + size(child), 1);

const root = newNode();
for (const [query, count] of LOG) insert(root, query, count);
console.log(`${LOG.length} queries, ${size(root) - 1} trie nodes, top ${K} kept at each node`);
for (const prefix of ["b", "bl", "blu", "blue ", "c", "x"]) {
  const node = find(root, prefix);
  if (!node) {
    console.log(`  "${prefix}" -> no suggestions`);
    continue;
  }
  const shown = node.top.map(([count, query]) => `${query} (${count})`).join(", ");
  console.log(`  "${prefix}" -> ${shown}; ${size(node)} nodes below`);
}

In JavaScript: A Map per node holds its children, and the comparator better breaks ties by comparing the query strings, so the order never depends on the engine's sort.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
  static final int K = 3;

  record Entry(String query, int count) {}

  static final class Node {
    final Map<Character, Node> children = new HashMap<>();
    final List<Entry> top = new ArrayList<>();
  }

  static final Comparator<Entry> BEST =
      Comparator.comparingInt(Entry::count).reversed().thenComparing(Entry::query);

  static void insert(Node root, Entry entry) {
    // Offer the query to every node on its path, and keep each node's best K.
    Node node = root;
    for (char ch : entry.query().toCharArray()) {
      node = node.children.computeIfAbsent(ch, c -> new Node());
      node.top.add(entry);
      node.top.sort(BEST);
      if (node.top.size() > K) {
        node.top.remove(K);
      }
    }
  }

  static Node find(Node root, String prefix) {
    Node node = root;
    for (char ch : prefix.toCharArray()) {
      node = node.children.get(ch);
      if (node == null) {
        return null;
      }
    }
    return node;
  }

  static int size(Node node) {
    return 1 + node.children.values().stream().mapToInt(Main::size).sum();
  }

  public static void main(String[] args) {
    List<Entry> log =
        List.of(
            new Entry("bluetooth speaker", 9400),
            new Entry("black shoes", 8100),
            new Entry("backpack", 7300),
            new Entry("blue jeans", 6900),
            new Entry("blue shirt", 4700),
            new Entry("battery", 4400),
            new Entry("bag", 3900),
            new Entry("blue saree", 3300),
            new Entry("cable", 8800),
            new Entry("camera", 7700),
            new Entry("candle", 2100));
    Node root = new Node();
    log.forEach(entry -> insert(root, entry));
    String counts = log.size() + " queries, " + (size(root) - 1) + " trie nodes";
    System.out.println(counts + ", top " + K + " kept at each node");
    for (String prefix : List.of("b", "bl", "blu", "blue ", "c", "x")) {
      Node node = find(root, prefix);
      String head = "  \"" + prefix + "\" -> ";
      if (node == null) {
        System.out.println(head + "no suggestions");
        continue;
      }
      var shown = new ArrayList<String>();
      node.top.forEach(e -> shown.add(e.query() + " (" + e.count() + ")"));
      System.out.println(head + String.join(", ", shown) + "; " + size(node) + " nodes below");
    }
  }
}

In Java: Comparator.comparingInt(Entry::count).reversed().thenComparing(Entry::query) states the order in one line, and computeIfAbsent creates a child node on first use.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <format>
#include <map>
#include <memory>
#include <print>
#include <string>
#include <utility>
#include <vector>

constexpr std::size_t K = 3;
using Entry = std::pair<int, std::string>; // minus the count, then the query

struct Node {
  std::map<char, std::unique_ptr<Node>> children;
  std::vector<Entry> top;
};

void insert(Node &root, const std::string &query, int count) {
  // Offer the query to every node on its path, and keep each node's best K.
  Node *node = &root;
  for (const char ch : query) {
    auto &child = node->children[ch];
    if (!child)
      child = std::make_unique<Node>();
    node = child.get();
    node->top.emplace_back(-count, query);
    std::ranges::sort(node->top);
    if (node->top.size() > K)
      node->top.pop_back();
  }
}

const Node *find(const Node &root, const std::string &prefix) {
  const Node *node = &root;
  for (const char ch : prefix) {
    if (!node->children.contains(ch))
      return nullptr;
    node = node->children.at(ch).get();
  }
  return node;
}

int size(const Node &node) {
  int n = 1;
  for (const auto &[ch, child] : node.children)
    n += size(*child);
  return n;
}

int main() {
  const std::vector<std::pair<std::string, int>> log = {
      {"bluetooth speaker", 9400},
      {"black shoes", 8100},
      {"backpack", 7300},
      {"blue jeans", 6900},
      {"blue shirt", 4700},
      {"battery", 4400},
      {"bag", 3900},
      {"blue saree", 3300},
      {"cable", 8800},
      {"camera", 7700},
      {"candle", 2100}};
  Node root;
  for (const auto &[query, count] : log)
    insert(root, query, count);
  std::println("{} queries, {} trie nodes, top {} kept at each node",
               log.size(), size(root) - 1, K);
  for (const std::string prefix : {"b", "bl", "blu", "blue ", "c", "x"}) {
    const Node *node = find(root, prefix);
    if (node == nullptr) {
      std::println("  \"{}\" -> no suggestions", prefix);
      continue;
    }
    std::string shown;
    for (const auto &[minus_count, query] : node->top)
      shown += std::format("{}{} ({})", shown.empty() ? "" : ", ", query,
                           -minus_count);
    std::println("  \"{}\" -> {}; {} nodes below", prefix, shown, size(*node));
  }
}

In C++: Children are owned by std::unique_ptr in a std::map, so the trie is freed when root goes out of scope; each list holds pairs of minus the count and the query, so plain std::ranges::sort puts the most searched first.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

const int K = 3;
(string Query, int Count)[] log =
[
    ("bluetooth speaker", 9400),
    ("black shoes", 8100),
    ("backpack", 7300),
    ("blue jeans", 6900),
    ("blue shirt", 4700),
    ("battery", 4400),
    ("bag", 3900),
    ("blue saree", 3300),
    ("cable", 8800),
    ("camera", 7700),
    ("candle", 2100),
];

var root = new Node();
foreach (var (query, count) in log)
    Insert(root, query, count);
Console.WriteLine($"{log.Length} queries, {Size(root) - 1} trie nodes, top {K} kept at each node");
foreach (string prefix in new[] { "b", "bl", "blu", "blue ", "c", "x" })
{
    Node? node = Find(root, prefix);
    if (node is null)
    {
        Console.WriteLine($"  \"{prefix}\" -> no suggestions");
        continue;
    }
    string shown = string.Join(", ", node.Top.Select(e => $"{e.Query} ({e.Count})"));
    Console.WriteLine($"  \"{prefix}\" -> {shown}; {Size(node)} nodes below");
}

static void Insert(Node root, string query, int count)
{
    // Offer the query to every node on its path, and keep each node's best K.
    Node node = root;
    foreach (char ch in query)
    {
        if (!node.Children.TryGetValue(ch, out Node? child))
            node.Children[ch] = child = new Node();
        node = child;
        node.Top.Add((query, count));
        node.Top.Sort(Better);
        if (node.Top.Count > K)
            node.Top.RemoveAt(K);
    }
}

static int Better((string Query, int Count) a, (string Query, int Count) b) =>
    a.Count != b.Count ? b.Count.CompareTo(a.Count) : string.CompareOrdinal(a.Query, b.Query);

static Node? Find(Node root, string prefix)
{
    Node node = root;
    foreach (char ch in prefix)
    {
        if (!node.Children.TryGetValue(ch, out Node? child))
            return null;
        node = child;
    }
    return node;
}

static int Size(Node node) => 1 + node.Children.Values.Sum(Size);

sealed class Node
{
    public Dictionary<char, Node> Children { get; } = [];
    public List<(string Query, int Count)> Top { get; } = [];
}

In C#: TryGetValue reports a missing child without an exception, and a static comparison function, Better, sorts each list with string.CompareOrdinal for ties.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

C is left out of this example: C's standard library has no map or growable list, so every node's children and top list would be hand-sized arrays and the program another design.

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const K = 3;
const LOG = [
    ['bluetooth speaker', 9400],
    ['black shoes', 8100],
    ['backpack', 7300],
    ['blue jeans', 6900],
    ['blue shirt', 4700],
    ['battery', 4400],
    ['bag', 3900],
    ['blue saree', 3300],
    ['cable', 8800],
    ['camera', 7700],
    ['candle', 2100],
];

final class Node
{
    /** @var array<string, Node> */
    public array $children = [];
    /** @var list<array{int, string}> */
    public array $top = [];
}

function insert(Node $root, string $query, int $count): void
{
    // Offer the query to every node on its path, and keep each node's best K.
    $node = $root;
    foreach (str_split($query) as $ch) {
        $node = $node->children[$ch] ??= new Node();
        $node->top[] = [$count, $query];
        usort($node->top, fn(array $a, array $b): int => [$b[0], $a[1]] <=> [$a[0], $b[1]]);
        $node->top = array_slice($node->top, 0, K);
    }
}

function find(Node $root, string $prefix): ?Node
{
    $node = $root;
    foreach (str_split($prefix) as $ch) {
        $node = $node->children[$ch] ?? null;
        if ($node === null) {
            return null;
        }
    }
    return $node;
}

function size(Node $node): int
{
    return 1 + array_sum(array_map(size(...), $node->children));
}

$root = new Node();
foreach (LOG as [$query, $count]) {
    insert($root, $query, $count);
}
printf("%d queries, %d trie nodes, top %d kept at each node\n", count(LOG), size($root) - 1, K);
foreach (['b', 'bl', 'blu', 'blue ', 'c', 'x'] as $prefix) {
    $node = find($root, $prefix);
    if ($node === null) {
        echo "  \"{$prefix}\" -> no suggestions\n";
        continue;
    }
    $shown = implode(', ', array_map(fn(array $e): string => "{$e[1]} ({$e[0]})", $node->top));
    echo "  \"{$prefix}\" -> {$shown}; " . size($node) . " nodes below\n";
}

In PHP: The ??= operator creates a child only when none exists, and comparing the arrays [$b[0], $a[1]] and [$a[0], $b[1]] sorts by count down, then by query up.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

use std::collections::BTreeMap;

const K: usize = 3;
const LOG: [(&str, u32); 11] = [
    ("bluetooth speaker", 9400),
    ("black shoes", 8100),
    ("backpack", 7300),
    ("blue jeans", 6900),
    ("blue shirt", 4700),
    ("battery", 4400),
    ("bag", 3900),
    ("blue saree", 3300),
    ("cable", 8800),
    ("camera", 7700),
    ("candle", 2100),
];

#[derive(Default)]
struct Node {
    children: BTreeMap<char, Node>,
    top: Vec<(u32, &'static str)>,
}

fn insert(root: &mut Node, query: &'static str, count: u32) {
    // Offer the query to every node on its path, and keep each node's best K.
    let mut node = root;
    for ch in query.chars() {
        node = node.children.entry(ch).or_default();
        node.top.push((count, query));
        node.top.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(b.1)));
        node.top.truncate(K);
    }
}

fn find<'a>(root: &'a Node, prefix: &str) -> Option<&'a Node> {
    prefix
        .chars()
        .try_fold(root, |node, ch| node.children.get(&ch))
}

fn size(node: &Node) -> usize {
    1 + node.children.values().map(size).sum::<usize>()
}

fn main() {
    let mut root = Node::default();
    for (query, count) in LOG {
        insert(&mut root, query, count);
    }
    let header = format!("{} queries, {} trie nodes", LOG.len(), size(&root) - 1);
    println!("{header}, top {K} kept at each node");
    for prefix in ["b", "bl", "blu", "blue ", "c", "x"] {
        let Some(node) = find(&root, prefix) else {
            println!("  \"{prefix}\" -> no suggestions");
            continue;
        };
        let shown: Vec<String> = node.top.iter().map(|(c, q)| format!("{q} ({c})")).collect();
        let (shown, below) = (shown.join(", "), size(node));
        println!("  \"{prefix}\" -> {shown}; {below} nodes below");
    }
}

In Rust: The entry API creates a child on first use, truncate keeps the best K, and find folds over the prefix's characters with try_fold, stopping at the first missing child.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

type Entry = [count: number, query: string];
type TrieNode = { children: Map<string, TrieNode>; top: Entry[] };

const K = 3;
const LOG: [string, number][] = [
  ["bluetooth speaker", 9400],
  ["black shoes", 8100],
  ["backpack", 7300],
  ["blue jeans", 6900],
  ["blue shirt", 4700],
  ["battery", 4400],
  ["bag", 3900],
  ["blue saree", 3300],
  ["cable", 8800],
  ["camera", 7700],
  ["candle", 2100],
];

const newNode = (): TrieNode => ({ children: new Map(), top: [] });
const better = (a: Entry, b: Entry): number => b[0] - a[0] || (a[1] < b[1] ? -1 : 1);

function insert(root: TrieNode, query: string, count: number): void {
  // Offer the query to every node on its path, and keep each node's best K.
  let node = root;
  for (const ch of query) {
    const child = node.children.get(ch) ?? newNode();
    node.children.set(ch, child);
    node = child;
    node.top.push([count, query]);
    node.top.sort(better);
    if (node.top.length > K) node.top.pop();
  }
}

function find(root: TrieNode, prefix: string): TrieNode | undefined {
  let node: TrieNode | undefined = root;
  for (const ch of prefix) node = node?.children.get(ch);
  return node;
}

const size = (node: TrieNode): number =>
  [...node.children.values()].reduce((n, child) => n + size(child), 1);

const root = newNode();
for (const [query, count] of LOG) insert(root, query, count);
console.log(`${LOG.length} queries, ${size(root) - 1} trie nodes, top ${K} kept at each node`);
for (const prefix of ["b", "bl", "blu", "blue ", "c", "x"]) {
  const node = find(root, prefix);
  if (!node) {
    console.log(`  "${prefix}" -> no suggestions`);
    continue;
  }
  const shown = node.top.map(([count, query]) => `${query} (${count})`).join(", ");
  console.log(`  "${prefix}" -> ${shown}; ${size(node)} nodes below`);
}

In TypeScript: find walks with optional chaining, node?.children.get(ch), so a missing child turns the rest of the walk into undefined without a branch.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"cmp"
	"fmt"
	"slices"
	"strings"
)

const k = 3

type entry struct {
	query string
	count int
}

type node struct {
	children map[rune]*node
	top      []entry
}

func insert(root *node, e entry) {
	// Offer the query to every node on its path, and keep each node's best K.
	n := root
	for _, ch := range e.query {
		if n.children[ch] == nil {
			n.children[ch] = &node{children: map[rune]*node{}}
		}
		n = n.children[ch]
		n.top = append(n.top, e)
		slices.SortFunc(n.top, func(a, b entry) int {
			return cmp.Or(cmp.Compare(b.count, a.count), cmp.Compare(a.query, b.query))
		})
		n.top = n.top[:min(len(n.top), k)]
	}
}

func find(root *node, prefix string) *node {
	n := root
	for _, ch := range prefix {
		if n = n.children[ch]; n == nil {
			return nil
		}
	}
	return n
}

func size(n *node) int {
	total := 1
	for _, child := range n.children {
		total += size(child)
	}
	return total
}

func main() {
	log := []entry{
		{"bluetooth speaker", 9400}, {"black shoes", 8100}, {"backpack", 7300},
		{"blue jeans", 6900}, {"blue shirt", 4700}, {"battery", 4400}, {"bag", 3900},
		{"blue saree", 3300}, {"cable", 8800}, {"camera", 7700}, {"candle", 2100},
	}
	root := &node{children: map[rune]*node{}}
	for _, e := range log {
		insert(root, e)
	}
	fmt.Printf("%d queries, %d trie nodes, top %d kept at each node\n", len(log), size(root)-1, k)
	for _, prefix := range []string{"b", "bl", "blu", "blue ", "c", "x"} {
		n := find(root, prefix)
		if n == nil {
			fmt.Printf("  %q -> no suggestions\n", prefix)
			continue
		}
		var shown []string
		for _, e := range n.top {
			shown = append(shown, fmt.Sprintf("%s (%d)", e.query, e.count))
		}
		fmt.Printf("  %q -> %s; %d nodes below\n", prefix, strings.Join(shown, ", "), size(n))
	}
}

In Go: Map iteration order is random, which size does not mind because it only adds; cmp.Or chains the two comparisons that sort each node's list.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

let k = 3
let log = [
  ("bluetooth speaker", 9400),
  ("black shoes", 8100),
  ("backpack", 7300),
  ("blue jeans", 6900),
  ("blue shirt", 4700),
  ("battery", 4400),
  ("bag", 3900),
  ("blue saree", 3300),
  ("cable", 8800),
  ("camera", 7700),
  ("candle", 2100),
]

final class Node {
  var children: [Character: Node] = [:]
  var top: [(count: Int, query: String)] = []
}

func insert(_ root: Node, _ query: String, _ count: Int) {
  // Offer the query to every node on its path, and keep each node's best K.
  var node = root
  for ch in query {
    let child = node.children[ch] ?? Node()
    node.children[ch] = child
    node = child
    node.top.append((count, query))
    node.top.sort { $0.count != $1.count ? $0.count > $1.count : $0.query < $1.query }
    node.top = Array(node.top.prefix(k))
  }
}

func find(_ root: Node, _ prefix: String) -> Node? {
  var node: Node? = root
  for ch in prefix {
    node = node?.children[ch]
  }
  return node
}

func size(_ node: Node) -> Int {
  node.children.values.reduce(1) { $0 + size($1) }
}

let root = Node()
for (query, count) in log {
  insert(root, query, count)
}
print("\(log.count) queries, \(size(root) - 1) trie nodes, top \(k) kept at each node")
for prefix in ["b", "bl", "blu", "blue ", "c", "x"] {
  guard let node = find(root, prefix) else {
    print("  \"\(prefix)\" -> no suggestions")
    continue
  }
  let shown = node.top.map { "\($0.query) (\($0.count))" }.joined(separator: ", ")
  print("  \"\(prefix)\" -> \(shown); \(size(node)) nodes below")
}

In Swift: Node is a class because the trie's nodes are shared references; the list of each node is an array of named tuples, sorted with a closure.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

K = 3
LOG = [
  ['bluetooth speaker', 9400], ['black shoes', 8100], ['backpack', 7300],
  ['blue jeans', 6900], ['blue shirt', 4700], ['battery', 4400], ['bag', 3900],
  ['blue saree', 3300], ['cable', 8800], ['camera', 7700], ['candle', 2100]
].freeze

Node = Struct.new(:children, :top)

def insert(root, query, count)
  # Offer the query to every node on its path, and keep each node's best K.
  node = root
  query.each_char do |ch|
    node = (node.children[ch] ||= Node.new({}, []))
    node.top = (node.top + [[count, query]]).sort_by { |c, q| [-c, q] }.first(K)
  end
end

def find(root, prefix)
  prefix.each_char.reduce(root) { |node, ch| node&.children&.fetch(ch, nil) }
end

def size(node) = 1 + node.children.values.sum { |child| size(child) }

root = Node.new({}, [])
LOG.each { |query, count| insert(root, query, count) }
puts "#{LOG.size} queries, #{size(root) - 1} trie nodes, top #{K} kept at each node"
['b', 'bl', 'blu', 'blue ', 'c', 'x'].each do |prefix|
  node = find(root, prefix)
  next puts "  #{prefix.inspect} -> no suggestions" if node.nil?

  shown = node.top.map { |count, query| "#{query} (#{count})" }.join(', ')
  puts "  #{prefix.inspect} -> #{shown}; #{size(node)} nodes below"
end

In Ruby: Struct gives the node its two fields, sort_by with [-count, query] orders each list, and the safe navigation operator &. lets find stop at a missing child.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

const val K = 3

val log =
    listOf(
        "bluetooth speaker" to 9400,
        "black shoes" to 8100,
        "backpack" to 7300,
        "blue jeans" to 6900,
        "blue shirt" to 4700,
        "battery" to 4400,
        "bag" to 3900,
        "blue saree" to 3300,
        "cable" to 8800,
        "camera" to 7700,
        "candle" to 2100,
    )

class Node {
    val children = mutableMapOf<Char, Node>()
    var top = listOf<Pair<Int, String>>()
}

fun insert(
    root: Node,
    query: String,
    count: Int,
) {
    // Offer the query to every node on its path, and keep each node's best K.
    var node = root
    for (ch in query) {
        node = node.children.getOrPut(ch) { Node() }
        val offered = node.top + (count to query)
        node.top = offered.sortedWith(compareBy({ -it.first }, { it.second })).take(K)
    }
}

fun find(
    root: Node,
    prefix: String,
): Node? = prefix.fold(root as Node?) { node, ch -> node?.children?.get(ch) }

fun size(node: Node): Int = 1 + node.children.values.sumOf { size(it) }

fun main() {
    val root = Node()
    for ((query, count) in log) insert(root, query, count)
    println("${log.size} queries, ${size(root) - 1} trie nodes, top $K kept at each node")
    for (prefix in listOf("b", "bl", "blu", "blue ", "c", "x")) {
        val node = find(root, prefix)
        if (node == null) {
            println("  \"$prefix\" -> no suggestions")
            continue
        }
        val shown = node.top.joinToString(", ") { (count, query) -> "$query ($count)" }
        println("  \"$prefix\" -> $shown; ${size(node)} nodes below")
    }
}

In Kotlin: getOrPut creates a child on first use, compareBy takes one selector for the count and one for the query, and find folds over the prefix's characters.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const k = 3;
const log = [
  ('bluetooth speaker', 9400),
  ('black shoes', 8100),
  ('backpack', 7300),
  ('blue jeans', 6900),
  ('blue shirt', 4700),
  ('battery', 4400),
  ('bag', 3900),
  ('blue saree', 3300),
  ('cable', 8800),
  ('camera', 7700),
  ('candle', 2100),
];

class Node {
  final children = <String, Node>{};
  var top = <(int, String)>[];
}

int better((int, String) a, (int, String) b) =>
    a.$1 != b.$1 ? b.$1 - a.$1 : a.$2.compareTo(b.$2);

void insert(Node root, String query, int count) {
  // Offer the query to every node on its path, and keep each node's best K.
  var node = root;
  for (final ch in query.split('')) {
    node = node.children.putIfAbsent(ch, Node.new);
    node.top = ([...node.top, (count, query)]..sort(better)).take(k).toList();
  }
}

Node? find(Node root, String prefix) {
  Node? node = root;
  for (final ch in prefix.split('')) {
    node = node?.children[ch];
  }
  return node;
}

int size(Node node) => node.children.values.fold(1, (n, c) => n + size(c));

void main() {
  final root = Node();
  for (final (query, count) in log) {
    insert(root, query, count);
  }
  print(
    '${log.length} queries, ${size(root) - 1} trie nodes, top $k kept at each node',
  );
  for (final prefix in ['b', 'bl', 'blu', 'blue ', 'c', 'x']) {
    final node = find(root, prefix);
    if (node == null) {
      print('  "$prefix" -> no suggestions');
      continue;
    }
    final shown = node.top.map((e) => '${e.$2} (${e.$1})').join(', ');
    print('  "$prefix" -> $shown; ${size(node)} nodes below');
  }
}

In Dart: The cascade ..sort(better) sorts the new list in place and returns it, so offering, sorting and keeping the best K fit in one expression.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart