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 Take-home Project rounds at SIG (Susquehanna).

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at SIG (Susquehanna) during technical interviews.

Count subarrays with odd zero count | SIG (Susquehanna) Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count subarrays with odd zero count states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Count subarrays with odd zero count

Company: SIG (Susquehanna)

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an integer array nums, return how many contiguous subarrays contain an odd number of zeros. Provide an O(n) solution (e.g., using prefix parity counts of zero occurrences) and state its time and space complexity. Example: nums = [0, 0, 1, 0, 1] -> 4.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count subarrays with odd zero count states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Count Subarrays With an Odd Number of Zeros

Given an integer array `nums`, return how many contiguous subarrays contain an **odd** number of zeros. Provide an O(n) solution. The key idea is to track the running *parity* (even/odd) of the count of zeros seen so far. A subarray `(i, j]` has an odd number of zeros if and only if the prefix parity at index `i` differs from the prefix parity at index `j`. So while scanning, keep counts of how many prefixes have had even parity vs odd parity (starting with one "empty" prefix of even parity), and for each new element add the number of earlier prefixes of the opposite parity. **Example:** `nums = [0, 0, 1, 0, 1]` -> `9`. (Note: there are 15 subarrays total for a length-5 array; 9 of them contain an odd number of zeros.)

Constraints

0 <= nums.length <= 10^5
Array elements are arbitrary integers; only whether each element equals 0 matters.
The answer can exceed 32-bit range for large inputs (up to ~n^2/2 subarrays), so use a 64-bit accumulator.

Examples

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

Expected Output: 9

Explanation: Of the 15 contiguous subarrays, 9 contain an odd number of zeros. (The original prompt's claim of 4 was a miscount.)

Input: ([],)

Expected Output: 0

Explanation: Empty array has no subarrays.

Input: ([0],)

Expected Output: 1

Explanation: The single subarray [0] has one zero (odd).

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

Expected Output: 0

Explanation: No zeros anywhere, so no subarray has an odd zero count.

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

Expected Output: 4

Explanation: Subarrays with odd zero counts: [0]x3 (each 1 zero) and the full [0,0,0] (3 zeros) = 4.

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

Expected Output: 8

Explanation: 8 of the 15 subarrays contain an odd number of zeros.

Hints

Brute force over all O(n^2) subarrays works but is too slow for large n; you need O(n).
Only the parity (even/odd) of the zero count matters. Track a running parity bit as you scan.
A subarray has an odd number of zeros iff the prefix parities at its two endpoints differ. Keep counts of how many prefixes had even vs odd parity (start with one even prefix), and add the opposite-parity count at each step.

Minute Difference Between Two HH:MM Times

Given two times formatted as strings `t1` and `t2` in `"HH:MM"` 24-hour form, return the difference in **minutes** between them. Assume both times are on the same day and that `t2` is always at or after `t1`. Convert each time to total minutes from midnight (`hours * 60 + minutes`) and subtract. **Example:** `t1 = "12:23", t2 = "13:24"` -> `61` (804 - 743).

Constraints

Each time is a valid 'HH:MM' string with HH in [00, 23] and MM in [00, 59].
t1 and t2 are on the same day, and t2 >= t1, so the result is non-negative (0 to 1439).
Leading zeros are present (e.g. '09:05').

Examples

Input: ("12:23", "13:24")

Expected Output: 61

Explanation: 12:23 = 743 min, 13:24 = 804 min; 804 - 743 = 61.

Input: ("00:00", "00:00")

Expected Output: 0

Explanation: Identical times differ by 0 minutes.

Input: ("00:00", "23:59")

Expected Output: 1439

Explanation: Midnight to one minute before the next midnight = 1439 minutes.

Input: ("09:05", "09:50")

Expected Output: 45

Explanation: Same hour: 50 - 5 = 45 minutes.

Input: ("08:30", "10:00")

Expected Output: 90

Explanation: 08:30 = 510 min, 10:00 = 600 min; 600 - 510 = 90.

Hints

Split each string on the ':' character to get the hour and minute parts.
Convert each time to a single integer: total minutes from midnight = hours * 60 + minutes.
Subtract the two totals. Because t2 >= t1, no wrap-around handling is needed.

Rotate a Matrix 90 Degrees Clockwise

Given an `n x n` matrix, return a new matrix that is the original rotated **90 degrees clockwise**. A clean way to compute this: element at position `(i, j)` in the input moves to position `(j, n-1-i)` in the output. Equivalently, rotating clockwise is the same as transposing the matrix and then reversing each row. **Example:** ``` [[1, 2, 3], [[7, 4, 1], [4, 5, 6], -> [8, 5, 2], [7, 8, 9]] [9, 6, 3]] ```

Constraints

The matrix is square: n x n, with 0 <= n <= 100.
Matrix entries are integers (may be negative).
Return a new matrix; an in-place solution is also acceptable but the reference returns a fresh grid.

Examples

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)

Expected Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Explanation: The first column (7,4,1) becomes the top row, etc.

Input: ([[1]],)

Expected Output: [[1]]

Explanation: A 1x1 matrix is unchanged by rotation.

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

Expected Output: [[3, 1], [4, 2]]

Explanation: Clockwise: bottom-left 3 moves to top-left, etc.

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

Expected Output: [[-3, -1], [-4, -2]]

Explanation: Negative values rotate identically.

Input: ([],)

Expected Output: []

Explanation: An empty matrix rotates to an empty matrix.

Hints

Think about where a single element ends up: the element at (i, j) lands at (j, n-1-i) after a clockwise turn.
Equivalently, rotating clockwise = transpose the matrix, then reverse each row.
Allocate an n x n result grid and copy each element to its rotated position; handle the empty matrix (n = 0) as a base case.

Quick Overview