← ByteDance Interview InsightsSoftware Engineer
The example they gave was something like [0,1,0,0,0,0,0,1,1,1,1] with an expected output of 6, which I stared at for a solid 20 seconds trying to manually verify.
Clarify that a valid substring consists of two adjacent equal-length blocks of identical bits (e.g., '0011' or '1100'). Then propose an O(n) solution by scanning the array and, for each position, counting the length of the current run of identical bits and the length of the previous run; the number of valid substrings ending at the current position is min(current_run_length, previous_run_length). Sum these contributions over all positions to get the total count.
Pro tip: Mention that this problem is essentially counting adjacent equal-length runs and that the O(n) solution can be derived by observing that each valid substring is determined by a boundary between two runs. Also, note that the answer can be large, so use a 64-bit integer for the count.
Confirm that a valid substring must consist of exactly two contiguous blocks of equal length, one of all 0s and one of all 1s, in either order. For example, '0011' and '1100' are valid, but '000111' is not because the blocks are length 3 and 3? Wait, '000111' has two blocks of length 3, so it is valid. Actually, any two adjacent runs of equal length form a valid substring. So the problem reduces to counting all pairs of adjacent runs (of 0s and 1s) that have the same length, and for each such pair, the number of valid substrings is exactly that length (since you can take any suffix of the first run and the corresponding prefix of the second run of the same length).
Realize that every valid substring is contained within the concatenation of two adjacent runs of different bits, and its length is twice the length of the shorter run. More precisely, if you have a run of 0s of length L1 followed by a run of 1s of length L2, then the number of valid substrings that span the boundary between these runs is min(L1, L2). This is because you can choose any k from 1 to min(L1, L2) and take the last k zeros and the first k ones.
Traverse the array once, keeping track of the length of the current run and the length of the previous run. When the current run ends (i.e., when the bit changes), add min(previous_run_length, current_run_length) to the total count. Then set previous_run_length = current_run_length and reset current_run_length to 1 for the new bit. At the end of the array, also add min(previous_run_length, current_run_length) for the final pair of runs.
Consider edge cases: empty array (return 0), array with all same bits (no valid substrings), and very large arrays (use 64-bit integer for the count). The time complexity is O(n) and space complexity is O(1).
Walk through a small example, such as '0011', to verify the algorithm: runs are '00' (length 2) and '11' (length 2), so min(2,2)=2 valid substrings: '01' and '0011'. Another example: '1100' gives 2. For '000111', runs are length 3 and 3, so min(3,3)=3 valid substrings: '01', '0011', '000111'.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.