Sliding Window or Two Pointers | Dataford Interview Questions

Your question is Sliding Window or Two Pointers. 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

The Compass search experience records the neighborhood associated with each listing a user views. Given this ordered sequence, find the longest contiguous browsing session containing at most k distinct neighborhoods.

Return the session as [start, end], using zero-based inclusive indices. If multiple sessions have the same maximum length, return the one with the smallest starting index. If k is zero, return [0, -1].

Formal Specification

Implement longest_session(neighborhoods, k).

neighborhoods is a list of strings representing viewed listing neighborhoods.
k is a nonnegative integer.
Return a two-element list [start, end].
The selected subarray must contain at most k distinct strings.

Constraints

1 <= len(neighborhoods) <= 10^5
0 <= k <= len(neighborhoods)
Each neighborhood is a non-empty string of at most 50 characters

Function Signature

def longest_session(neighborhoods, k):