Katkat
Back

Solve array modulo and parentheses tasks

SheinSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

Implement two tasks:

  1. Count subarrays by modulo remainder
  • Input: integer array nums (length n), integers K (1 ≤ K ≤ 10^
  1. 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).
  1. 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.