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.