Solve array modulo and parentheses tasks
Company: Shein
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement two tasks:
1) Count subarrays by modulo remainder
- Input: integer array nums (length n), integers K (1 ≤ K ≤ 10^
4) and R (0 ≤ R < K).
- Output: the number of subarrays [i..j] such that (sum(nums[i..j]) mod K) == R.
- Requirements: O(n) time and O(K) space; describe the approach, justify correctness, and analyze complexity. Provide an implementation of countSubarraysByRemainder(nums, K, R).
2) Remove the minimum parentheses to balance a string
- Input: string s containing lowercase letters and parentheses '()'.
- Output: any string formed by deleting the minimum number of parentheses so that the result is a valid, balanced parentheses string (characters’ relative order must be preserved).
- Requirements: O(n) time and O(
1) extra space beyond the output; describe the algorithm and provide an implementation.
Quick Answer: This question evaluates proficiency in modular arithmetic and subarray-sum reasoning for remainder counting, together with string manipulation and parentheses-balancing competencies, testing algorithmic problem-solving, correctness justification, and implementation skills in the Coding & Algorithms domain.
Count Subarrays by Modulo Remainder
Given an integer array `nums` of length n and integers `K` (1 ≤ K ≤ 10^4) and `R` (0 ≤ R < K), return the number of contiguous subarrays `nums[i..j]` whose element sum is congruent to `R` modulo `K`, i.e. `(sum(nums[i..j]) mod K) == R`.
Approach: walk a running prefix sum reduced modulo K. For a subarray ending at index j with prefix remainder `p`, it has remainder R exactly when some earlier prefix had remainder `(p - R) mod K`. Keep a frequency table of prefix remainders seen so far (seeded with remainder 0 occurring once for the empty prefix) and accumulate matches. Use Python's floored modulo so negative numbers map into [0, K), keeping the math consistent. This runs in O(n) time and O(K) space.
Implement `countSubarraysByRemainder(nums, K, R)`.
Constraints
- 1 ≤ K ≤ 10^4
- 0 ≤ R < K
- nums may contain negative integers, zero, and positives
- n (length of nums) can be 0
- Use floored modulo so negatives map into [0, K)
Examples
Input: ([4, 5, 0, -2, -3, 1], 5, 0)
Expected Output: 7
Explanation: There are 7 subarrays whose sum is divisible by 5 (remainder 0).
Input: ([5], 9, 0)
Expected Output: 0
Explanation: The only subarray [5] has sum 5; 5 mod 9 = 5, not 0, so no subarray matches.
Hints
- If two prefix sums leave the same remainder mod K, the subarray between them is divisible by K. Generalize this to a target remainder of R.
- For a prefix remainder p, you want earlier prefixes with remainder (p - R) mod K. Count them with a hash map.
- Seed the map with remainder 0 having frequency 1 to account for the empty prefix (subarrays starting at index 0).
Remove Minimum Parentheses to Make Valid
Given a string `s` of lowercase letters and the characters `'('` and `')'`, delete the minimum number of parentheses so that the resulting string is a valid (balanced) parentheses string, preserving the relative order of the remaining characters. Letters are never removed. Return any one valid result of minimum length removed.
Approach: a single forward scan with a counter of currently-unmatched `'('`. On `'('` increment; on `')'` either match it (decrement the counter) or, if there is no open paren to match, mark this `')'` for deletion. After the scan, the counter equals the number of `'('` that were never closed — remove that many `'('` by scanning from the right. This deletes exactly the minimum number of parentheses, runs in O(n) time, and uses O(1) extra space beyond the output buffer.
Implement `removeMinParentheses(s)`.
Constraints
- s consists only of lowercase English letters and the characters '(' and ')'
- Letters must never be removed and relative order must be preserved
- s may be empty
- The result must remove the minimum possible number of parentheses
- Any valid minimum-removal result is accepted (the reference uses a deterministic left-to-right rule)
Examples
Input: ('lee(t(c)o)de)',)
Expected Output: 'lee(t(c)o)de'
Explanation: The trailing unmatched ')' is the only paren removed; the rest is already balanced.
Input: ('a)b(c)d',)
Expected Output: 'ab(c)d'
Explanation: The early ')' has no opener and is deleted; '(c)' stays balanced.
Hints
- Track the number of currently unmatched '('. A ')' that arrives when this count is 0 can never be matched, so delete it.
- After one pass, whatever value the open counter holds is the number of '(' that were never closed — those must be removed too.
- Remove the surplus '(' by scanning from the right so the deletions land on the last unmatched opens; total deletions are provably minimal.