How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Shein.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Shein during technical interviews.

Solve array modulo and parentheses tasks

Quick Overview

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.

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.

Input: ([1, 2, 3], 3, 0)

Expected Output: 3

Explanation: Subarrays [3], [1,2], and [1,2,3] all have sums divisible by 3.

Input: ([2, 7, 11, 15], 5, 2)

Expected Output: 2

Explanation: Two subarrays have a sum whose remainder mod 5 equals 2.

Input: ([], 3, 0)

Expected Output: 0

Explanation: Empty array: there are no subarrays, so the count is 0.

Input: ([-1, -1, -1], 2, 1)

Expected Output: 4

Explanation: Each single -1 (3 of them) and the full subarray sum -3 are odd (remainder 1 mod 2), giving 4.

Input: ([1, 1, 1, 1], 4, 0)

Expected Output: 1

Explanation: Only the full subarray sums to 4, which is divisible by 4.

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.

Input: ('))((',)

Expected Output: ''

Explanation: Every paren is unmatched: two ')' delete in the forward pass, two '(' in the backward pass.

Input: ('(a(b(c)d)',)

Expected Output: '(a(bc)d)'

Explanation: One surplus '(' remains after matching; it is removed from the right, leaving a balanced string of length 8.

Input: ('',)

Expected Output: ''

Explanation: Empty input yields empty output.

Input: ('abc',)

Expected Output: 'abc'

Explanation: No parentheses to remove; the string is returned unchanged.

Input: ('()',)

Expected Output: '()'

Explanation: Already valid; nothing is removed.

Input: ('(((',)

Expected Output: ''

Explanation: All three '(' are unmatched and removed in the backward pass.

Input: (')))',)

Expected Output: ''

Explanation: All three ')' are unmatched and removed in the forward pass.

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.

Quick Overview