Microsoft SWE II OA, HackerRank, two coding problems. I passed and moved on to the VO.
[Questions]
Q1: Given a string, look at the substrings whose length is in [minLength, maxLength] and whose number of distinct characters is <= maxUnique, and return the highest frequency among them. Similar to LC 1297. n goes up to 1e5, maxLength <= 26.
Example: abcde, length 2 to 4, maxUnique unlimited, the answer is 1 (every substring appears only once).
Q2: Pick exactly k out of n servers, the chosen ones cannot be adjacent, and minimize the maximum value among the chosen servers. Similar to LC 2560 in a different wrapper.
Example: [2,3,5,9], k=2, the answer is 5 (pick the 1st and the 3rd server, the max is 5).
[Approach]
Q1: The outer loop goes over every valid length L (from minLength to maxLength). The inner loop scans the string with a sliding window of size L, using a hash map to count how often each substring appears, while also tracking the number of distinct characters in the window (a Counter works for that), and skipping the window if it exceeds maxUnique. Take the max frequency over all lengths. Gotchas: initialize n inside the function, and clear the freq map when you switch to a new length.
Q2: Binary search on an upper bound x, then scan left to right greedily: take a server if its value is <= x and the previous one was not taken, and see whether you can get k servers. If you can, x is feasible, so search lower; if you can't, search higher.
Discussion
Loading comments…