Solve two-pointer, sliding-window, and string tasks
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Solve the following three coding tasks:
1) Two-pointer in-place de-duplication: Given a non-decreasing integer array nums and an integer k >= 1, modify nums in-place so that each distinct value appears at most k times. Return the new length L and ensure nums[0..L-1] holds the resulting sequence. Requirements: O(n) time, O(1) extra space. Prove correctness (loop invariants) and discuss off-by-one pitfalls. Test cases: [], k=1 -> L=0; [2,2,2], k=1 -> [2]; [1,1,1,2,2,3], k=2 -> prefix [1,1,2,2,3]; k >= n; array with many distinct values.
2) Sliding-window minimum cover: Given strings s and t, return the shortest substring of s that contains every character of t with multiplicity. If multiple, return the leftmost. Achieve O(|s| + |t|) time and O(Σ alphabet) space. Be Unicode-aware by code points; explain how you’d adapt if the alphabet is very large or if you must treat grapheme clusters. Example: s = "ADOBECODEBANC", t = "ABC" -> "BANC". Provide adversarial tests (e.g., repeated chars in t, no solution).
3) Non-LC style string processing: Implement sanitize(s) that (a) trims leading/trailing whitespace, (b) collapses any run of whitespace (spaces/tabs/newlines) into a single space, and (c) replaces every maximal run of ASCII digits [0-9]+ with a single token "#" while leaving all other characters unchanged. Do it in one pass O(n) and O(1) extra space (in-place if the language allows). Discuss pitfalls with multi-byte Unicode, combining marks, and surrogate pairs. Include unit tests that cover edge cases (empty string, only digits, mixed emoji, long whitespace runs).
Quick Answer: This multi-part question evaluates algorithmic problem-solving skills across two-pointer in-place array manipulation, sliding-window substring optimization, and single-pass string sanitization with attention to Unicode, grapheme clusters, and space-efficient in-place transformations.
Part 1: Two-Pointer In-Place De-duplication
You are given a non-decreasing integer array nums and an integer k >= 1. Rewrite the array in-place so that each distinct value appears at most k times. Keep the relative order of the remaining elements the same. For easier automated testing, return a tuple (L, nums[:L]) after performing the in-place rewrite, where L is the new logical length.
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order
- 1 <= k <= 200000
Examples
Input: ([], 1)
Expected Output: (0, [])
Explanation: Edge case: empty input stays empty.
Input: ([2, 2, 2], 1)
Expected Output: (1, [2])
Explanation: Only one copy of 2 may remain.
Hints
- Use one pointer to read the original array and another pointer to write the kept values.
- Once you have already written k elements, compare the current value with the element k positions behind the write pointer.
Part 2: Sliding-Window Minimum Cover Substring
Given strings s and t, return the shortest substring of s that contains every character of t with multiplicity. If multiple substrings have the same minimum length, return the leftmost one. If no such substring exists, return an empty string. Assume Python string iteration is by Unicode code point.
Constraints
- 0 <= len(s), len(t) <= 200000
- Characters may repeat in t and must be matched with multiplicity
- Expected solution should run in O(len(s) + len(t)) time
Examples
Input: ("ADOBECODEBANC", "ABC")
Expected Output: "BANC"
Explanation: Classic example: BANC is the shortest substring containing A, B, and C.
Input: ("AAABBC", "AABC")
Expected Output: "AABBC"
Explanation: t requires two As, one B, and one C.
Hints
- Maintain character requirements from t and expand a right pointer until the window becomes valid.
- Once the window is valid, move the left pointer rightward while the window still covers t.
Part 3: String Sanitization with Whitespace Collapsing and Digit-Run Replacement
Implement sanitize(s) in one pass. It must: (1) trim leading and trailing whitespace, (2) collapse every maximal run of whitespace into a single space, and (3) replace every maximal run of ASCII digits [0-9]+ with a single '#'. All other characters must remain unchanged. For this problem, whitespace means any character c such that c.isspace() is True in Python.
Constraints
- 0 <= len(s) <= 200000
- Digits to replace are ASCII only: '0' through '9'
- The algorithm should process the string in one left-to-right pass
Examples
Input: ("",)
Expected Output: ""
Explanation: Edge case: empty string stays empty.
Input: ("12345",)
Expected Output: "#"
Explanation: A full digit run becomes a single #.
Hints
- Do not emit a space immediately when you see whitespace; delay it until you know another non-whitespace character is coming.
- Track whether you are currently inside a digit run so you only append one '#'.