Perplexity·Software Engineer·Online Assessment (OA)·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Perplexity coding assessment, one problem the whole way through. The task was deceptively practical, less about clever algorithms and more about knowing when to stop and extrapolate.

Questions Asked (1)

On a ByteTokenizer class with a working tokenize method, implement estimate_token_count(text, sample_size, rng) that estimates the full token count without tokenizing the entire input. You can call tokenize as many times as you want, but the total bytes passed across all calls must stay within sample_size. If sample_size is at least as large as the input, return the exact count. Any randomness must use the provided rng object.

Algorithms & Data StructuresTechnical Trade-offsAPI & Integrations

Author's notes

The edge case tripped me up first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, handle the trivial case: if sample_size >= len(text), tokenize the entire text and return the exact count. Otherwise, use the provided rng to randomly sample chunks of text whose total length is at most sample_size, tokenize each chunk, and compute the average tokens per byte. Multiply that ratio by the total length of the input to estimate the full token count.

Pro tip: Mention that the estimate's accuracy depends on how representative the sampled chunks are; if the text has varying token density (e.g., code vs. prose), you might stratify the sample or use multiple random samples to reduce variance. Also, be explicit about how you handle the last partial chunk to avoid bias.

1. Check for exact case

If sample_size is greater than or equal to the length of the input text, simply call tokenize on the entire text and return the exact token count. This avoids unnecessary sampling.

2. Design the sampling strategy

Decide how to partition the input into chunks and select a random subset whose total byte length does not exceed sample_size. Use the provided rng to make random choices, ensuring reproducibility and fairness.

3. Tokenize sampled chunks

For each selected chunk, call tokenize and record the number of tokens produced. Keep a running total of bytes sampled and tokens counted.

4. Compute the estimate

Calculate the average tokens per byte from the sampled chunks, then multiply by the total length of the input text to estimate the full token count. Optionally, round to the nearest integer.

5. Discuss trade-offs and edge cases

Explain how sample_size affects accuracy, the impact of non-uniform token density, and how you ensure randomness uses only the provided rng. Mention potential improvements like stratified sampling.

Key Points to Mention

Handling the exact case when sample_size >= len(text) by tokenizing the whole input.
Using the provided rng object for all randomness to ensure reproducibility and testability.
Sampling strategy: random contiguous chunks vs. random individual characters; contiguous chunks preserve context and tokenization behavior.
Estimator: tokens per byte ratio multiplied by total bytes; this is a simple unbiased estimator if sampling is uniform.
Trade-offs: larger sample_size increases accuracy but costs more computation; non-uniform text may require stratification.
Edge cases: empty text, sample_size = 0, and ensuring the total bytes passed to tokenize never exceeds sample_size.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.