Solve a Data Structures Problem | Dataford Interview Questions

Your question is Solve a Data Structures Problem. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Slack analytics groups each channel's normalized message tokens into contiguous runs. Given an array of tokens and an integer k, find the length of the longest contiguous subarray containing at most k distinct token values.

Use a sliding window so the algorithm scales linearly with the number of tokens. Token order must be preserved, and repeated occurrences count toward the window length but not toward its distinct-token count.

Formal Specification

Implement longest_topic_run(tokens, k):

Input: tokens, a list of strings, and k, a nonnegative integer.
Output: An integer representing the maximum length of a contiguous subarray with at most k distinct strings.
Return 0 when no non-empty valid window exists.

Constraints

0 <= len(tokens) <= 10^5
0 <= k <= len(tokens)
Each token is a non-empty string of at most 50 characters
Token comparisons are case-sensitive

Function Signature

def longest_topic_run(tokens, k):