← ByteDance Interview InsightsSoftware Engineer

ByteDance·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Python coding round for a Data Engineer role at Bytedance, about 30 minutes. One problem the whole time, which felt manageable but had a subtle edge case I didn't see coming.

Questions Asked (1)

Q1

Given a binary array of 0s and 1s, count the number of contiguous substrings that consist of exactly two equal-length groups (for example, '0011' or '1100' would each count as valid).

Algorithms & Data Structures
Author's notes

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.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

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.

1. Clarify the problem

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).

2. Identify the key observation

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.

3. Design an O(n) algorithm

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.

4. Handle edge cases and complexity

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).

5. Test with examples

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'.

Key Points to Mention

  • The problem reduces to counting adjacent runs of equal length.
  • For two adjacent runs of lengths L1 and L2, the number of valid substrings spanning them is min(L1, L2).
  • A single pass O(n) algorithm with O(1) extra space is possible.
  • Use a 64-bit integer for the count to avoid overflow.
  • Edge cases: empty array, all same bits, and very long runs.
  • Clarify that the two groups must be contiguous and of equal length, but the bits can be in any order (0s then 1s or 1s then 0s).

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