← Microsoft Interview Insights
Two-pointer setup is the right instinct but I kept second-guessing my write index.
Use a two-pointer technique: one pointer (write) tracks the position to place the next valid element, and another (read) scans the array. Since the array is sorted, you can allow up to k duplicates by comparing the current element with the element at write - k. This achieves O(n) time and O(1) space.
Pro tip: Emphasize that the array is sorted, which allows in-place deduplication without extra space. Also, mention that the solution is optimal and discuss edge cases like k=0 or k >= array length.
Confirm that the array is sorted, k is a non-negative integer, and modifications must be in-place. Discuss edge cases: empty array, k=0, k >= length, and all elements identical.
Set write = 0 to track the position where the next valid element will be placed. Iterate through the array with a read pointer.
For each element at read, if write < k or the current element is different from the element at write - k, then assign array[write] = array[read] and increment write.
After the loop, write represents the new length of the modified array. Return write.
Explain that the algorithm runs in O(n) time with O(1) extra space. Discuss why this is optimal and mention potential variations (e.g., if array were not sorted).
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.
Use a sliding window with two pointers to expand and contract the window while maintaining character counts of t. Track the minimum window length and leftmost start index, ensuring O(|s| + |t|) time by processing each character at most twice. Handle Unicode by iterating over code points (e.g., using runes in Go or code points in Python) rather than bytes.
Pro tip: Explicitly state that you will treat the string as a sequence of Unicode code points, not bytes, and mention that in languages like Python 3, iterating over a string already yields code points, but in others you may need to decode first. This shows attention to detail and avoids a common pitfall.
Confirm that the substring must contain all characters of t with correct frequencies, and if multiple shortest substrings exist, return the leftmost. Discuss edge cases: empty t, t longer than s, or characters not in s.
Use a hash map (or fixed-size array if the character set is small) to store the frequency of each character in t. Maintain a count of how many characters from t are currently satisfied in the window.
Initialize left and right pointers at 0. Expand right to include characters, updating the window frequency and satisfied count. When all characters are satisfied, shrink left to find the smallest valid window, updating the minimum length and start index.
Ensure that iteration and frequency counting operate on Unicode code points (e.g., using runes in Go, code points in Python, or codePointAt in Java) to correctly handle characters outside the Basic Multilingual Plane.
Explain that each character is added and removed at most once, giving O(|s| + |t|) time and O(|t|) space. Walk through a small example and test edge cases.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.
This one felt less like a classic LC problem and more like something you'd actually write at work, which I liked.
Start by clarifying the requirements and edge cases, then outline a two-pointer in-place algorithm that processes the string character by character, handling whitespace and digit runs. Emphasize the O(n) time and O(1) space constraints, and discuss Unicode pitfalls such as multi-byte characters and surrogate pairs.
Pro tip: Mention that the function should operate on a mutable character array (e.g., in C++ or Java) to achieve O(1) space, and that for immutable strings (like in Python), you may need to convert to a list first, which uses O(n) space—so clarify the language context.
Ask about input type (string vs. char array), whether the function should modify in-place, and how to handle Unicode. Confirm that '#' replaces digit runs and that whitespace includes spaces, tabs, newlines.
Use a read pointer to scan the input and a write pointer to build the output. Maintain a state flag for whether the previous character was whitespace or a digit to collapse runs.
When encountering whitespace, write a single space only if the last written character wasn't a space. When encountering a digit, write '#' only if the previous character wasn't a digit.
Explain that ASCII digits are safe, but for Unicode, code points may be multi-byte. Surrogate pairs in UTF-16 must be treated as a single character; naive byte-wise processing can split them.
Confirm O(n) time and O(1) extra space (if mutable array). Test edge cases: empty string, all whitespace, all digits, leading/trailing whitespace, and mixed Unicode.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.