Runway·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Interviewed for an ML Engineer role at Runway and got hit with a pretty deep n-gram language model question that covered implementation, design decisions, and complexity analysis all in one shot. More of a systems-meets-theory hybrid than a pure coding screen.

Questions Asked (1)

Design and implement an n-gram language model class with fit and generate methods. The fit method should read a text file, tokenize it, build n-gram and (n-1)-gram frequency counts, and compute conditional probabilities with smoothing. The generate method should sample next tokens using the learned probabilities. Also discuss how to choose the optimal n, validation procedures, metrics like perplexity, backoff or interpolation strategies, and the time/space complexity tradeoffs for different values of n.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This was a lot to unpack in one question.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by outlining the class design and core methods, then dive into implementation details like tokenization, counting, smoothing, and sampling. Finally, discuss model selection (n, smoothing), evaluation metrics (perplexity), and trade-offs (time/space complexity, backoff/interpolation).

Pro tip: Emphasize practical considerations: use efficient data structures (e.g., nested dictionaries or tries) for sparse counts, and mention that in production you'd likely use a library like KenLM or SRILM, but implementing from scratch demonstrates understanding.

1. Class Design and Fit Method

Define the class with fit and generate methods. In fit, read the file, tokenize (e.g., split on whitespace, handle punctuation), pad with start/end tokens, and build n-gram and (n-1)-gram frequency counts using dictionaries.

2. Probability Estimation with Smoothing

Compute conditional probabilities P(w_n | w_1...w_{n-1}) = count(w_1...w_n) / count(w_1...w_{n-1}). Apply smoothing (e.g., add-k, Kneser-Ney) to handle unseen n-grams and avoid zero probabilities.

3. Generate Method

Implement generate by starting with a seed context (or start token), then iteratively sample the next token from the conditional distribution until an end token or max length. Use the learned probabilities and smoothing.

4. Model Selection and Evaluation

Discuss choosing n via validation: split data into train/validation/test, train models with different n, evaluate perplexity on validation, and pick n with lowest perplexity. Mention backoff/interpolation to combine multiple n-gram orders.

5. Complexity and Trade-offs

Analyze time/space: counting O(N) time, O(V^n) space in worst case (but sparse in practice). Generation O(n) per token. Larger n captures more context but increases sparsity and memory; smoothing/backoff mitigate.

Key Points to Mention

Tokenization choices (e.g., lowercasing, punctuation handling) affect model quality.
Smoothing techniques: Laplace, Good-Turing, Kneser-Ney, and their impact on perplexity.
Perplexity as evaluation metric: lower is better, computed as exp(-1/N * sum log P(w_i | context)).
Backoff vs. interpolation: backoff uses lower-order n-grams when higher-order unseen; interpolation mixes probabilities from different orders.
Time/space complexity: O(N) time for counting, O(V^n) space worst-case but sparse; generation O(n) per token.
Practical implementation: use efficient data structures (e.g., nested dicts, tries) and consider pruning rare n-grams.

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