Design high-throughput hashing for kernels

Q: Design high-throughput hashing for kernels

This question evaluates understanding of cache-efficient, high-throughput hash lookup design and related competencies such as hashing strategies, probe behavior, memory layout, vectorization, bitwise optimizations, prefetching, alignment, and microarchitectural performance trade-offs.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Question

Design a high-throughput hash-based lookup to be called inside a tight kernel. Choose between open addressing and chaining, specify the load factor, probe sequence, and table layout to favor vectorization and contiguous accesses. Show how to use bitwise operations, prefetching, and alignment to reduce collisions and cache misses. Explain trade-offs and how you would profile and validate the design.

PracHub · Accepted Answer

def solution(pairs, queries):
    n = len(pairs)

# ceil(10 * n / 7) without floating point
    required = (10 * n + 6) // 7

capacity = 1
    target = max(1, required)
    while capacity < target:
        capacity <<= 1

mask = capacity - 1
    occupied = [False] * capacity
    keys = [0] * capacity
    values = [0] * capacity

insert_probes = 0

for key, value in pairs:
        idx = ((key * 2654435761) & 0xFFFFFFFF) & mask
        while True:
            insert_probes += 1
            if not occupied[idx]:
                occupied[idx] = True
                keys[idx] = key
                values[idx] = value
                break
            if keys[idx] == key:
                values[idx] = value
                break
            idx = (idx + 1) & mask

answers = []
    lookup_probes = 0

for key in queries:
        idx = ((key * 2654435761) & 0xFFFFFFFF) & mask
        while True:
            lookup_probes += 1
            if not occupied[idx]:
                answers.append(-1)
                break
            if keys[idx] == key:
                answers.append(values[idx])
                break
            idx = (idx + 1) & mask

return (capacity, answers, insert_probes, lookup_probes)

Quick Overview

Solution

Hints

Quick Overview