SHEIN·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Shein software engineer interview with two algorithm problems back to back. Both were fairly meaty for a single session and the complexity constraints made it clear they actually wanted you to think, not just brute force your way through.

Questions Asked (2)

Given an integer array, two integers K and R, count the number of subarrays whose sum modulo K equals R. Your solution must run in O(n) time and use O(K) space. Walk through your approach, justify why it's correct, and implement it.

Algorithms & Data Structures

Author's notes

Prefix sum with a remainder frequency map.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a prefix sum modulo K and a hash map to count remainders. For each prefix sum, compute its remainder and add the count of previous prefixes with remainder (current_remainder - R + K) % K to the answer. This yields O(n) time and O(K) space.

Pro tip: Handle negative numbers by normalizing the modulo operation to always yield a non-negative remainder, and initialize the map with remainder 0 having count 1 to account for subarrays starting at index 0.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: count subarrays where sum mod K equals R. Confirm that K > 0 and R is in [0, K-1]. Mention that the solution must be O(n) time and O(K) space.

2. Explain the prefix sum modulo approach

Describe how the sum of a subarray from i to j is prefix[j] - prefix[i-1]. Taking modulo K, we need (prefix[j] - prefix[i-1]) mod K = R, which implies prefix[i-1] mod K = (prefix[j] mod K - R + K) mod K. Thus, for each j, we look for previous prefixes with that remainder.

3. Walk through the algorithm with an example

Use a small array to illustrate: initialize a hash map with {0:1} to handle subarrays starting at index 0. Iterate through the array, maintain running sum modulo K, compute target remainder, add map[target] to count, then increment map[current_remainder].

4. Justify correctness and complexity

Argue that every subarray ending at j with sum mod K = R is counted exactly once because we consider all valid starting points via the prefix remainders. Time is O(n) since each element is processed once; space is O(K) due to at most K distinct remainders.

5. Implement the solution in code

Write clean code in a language of choice (e.g., Python or Java), ensuring negative remainders are normalized. Include comments and handle edge cases like empty array or K=1.

Key Points to Mention

Prefix sum modulo K and its relation to subarray sums
Using a hash map to store counts of remainders for O(1) lookups
Normalizing negative remainders to be in [0, K-1]
Initializing the map with remainder 0 count 1 to account for subarrays starting at index 0
Time complexity O(n) and space complexity O(K)
Handling edge cases: empty array, K=1, R out of range

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Given a string with lowercase letters and parentheses, remove the minimum number of parentheses to make it valid and balanced. The relative order of remaining characters must be preserved. Implement this in O(n) time with O(1) extra space beyond the output.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The O(1) space constraint is what makes this annoying.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pass approach: first, scan left-to-right to count unmatched closing parentheses and mark them for removal; then scan right-to-left to count unmatched opening parentheses and mark them. Finally, build the result string by including only characters that were not marked for removal, preserving order.

Pro tip: Clarify that the O(1) extra space constraint applies beyond the output, so using a boolean array of size n is acceptable. Also, mention that the two-pass method is optimal and simpler than a stack-based approach, which would require O(n) space.

1. Clarify requirements and constraints

Confirm that the input string contains only lowercase letters and parentheses, and that the output must preserve the relative order of remaining characters. Ensure the O(1) extra space is beyond the output.

2. First pass: identify unmatched closing parentheses

Iterate left-to-right, maintaining a balance counter. Increment on '(', decrement on ')'. If balance would go negative, mark that ')' for removal and reset balance to 0.

3. Second pass: identify unmatched opening parentheses

Iterate right-to-left, maintaining a balance counter. Increment on ')', decrement on '('. If balance would go negative, mark that '(' for removal and reset balance to 0.

4. Build the result string

Iterate through the string once more, appending characters that were not marked for removal. This preserves the original order.

5. Analyze complexity and edge cases

State that the algorithm runs in O(n) time with three passes, and uses O(n) space for the boolean array (or O(1) if using a mutable string). Discuss edge cases like empty string, all parentheses, and already balanced strings.

Key Points to Mention

Two-pass marking technique to identify unmatched parentheses without a stack.
Use of a balance counter to track unmatched parentheses in each direction.
Preservation of relative order by only removing marked characters.
Time complexity O(n) and space complexity O(n) for the boolean array (or O(1) if modifying in place).
Comparison with stack-based approach: stack uses O(n) space and may be less efficient.
Edge cases: empty string, no parentheses, all opening or all closing parentheses, already balanced.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.