← Bloomberg Interview Insights
Knew sliding window was the move pretty quickly, but getting the pointer logic exactly right took me a minute.
Use a sliding window with two pointers and a hash map to track the last seen index of each character. Expand the right pointer and when a duplicate is found, move the left pointer to the maximum of its current position and the duplicate's last index plus one. Keep track of the maximum window length seen.
Pro tip: Clarify the character set upfront (e.g., ASCII vs Unicode) to choose the right data structure, and always walk through a few examples to catch off-by-one errors.
Ask about the character set, empty string, and whether the substring must be contiguous. Confirm expected output for edge cases like all unique characters or all same characters.
Use a hash map (or array for fixed ASCII) to store the last seen index of each character. This allows O(1) lookups and updates.
Initialize left and right pointers at 0. Expand right, and if the current character is in the map and its last index >= left, move left to last index + 1. Update the map with the current index.
After each step, compute the current window length (right - left + 1) and update the maximum length if it's larger.
State that time complexity is O(n) and space is O(min(n, m)) where m is the character set size. Walk through a test case to verify correctness.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.