Bytedance·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Bytedance Data Engineer screen, one Python coding question, about 30 minutes total. Pretty focused session, no fluff.

Questions Asked (1)

Given a binary array of 0s and 1s, count how many contiguous substrings consist of exactly two equal-length groups (for example '0011' or '1100' would each count). The example input was [0,1,0,0,0,0,0,1,1,1,1] with an expected output of 6.

Algorithms & Data Structures

Author's notes

Took me a bit to even understand what 'two groups of equal length' meant from the problem statement.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the problem asks for contiguous substrings where the first half is all 0s and the second half all 1s, or vice versa, with equal lengths. Then propose an O(n) solution by scanning for maximal runs of identical bits and summing min(left_run, right_run) for each adjacent run pair. Walk through the example to verify the count of 6.

Pro tip: Explicitly state the two valid patterns ('0...01...1' and '1...10...0') and note that substrings must be contiguous and exactly two groups, which rules out overlapping or mixed patterns. This shows you understand the problem's constraints and avoids common misinterpretations.

1. Clarify the problem

Restate that we need contiguous substrings of even length where the first half is all one bit and the second half is all the other bit. Confirm with the interviewer that only these two patterns count.

2. Identify runs

Scan the array and compute the lengths of consecutive runs of identical bits. For example, [0,1,0,0,0,0,0,1,1,1,1] becomes runs of lengths [1,1,5,4] with bits 0,1,0,1.

3. Count valid substrings per adjacent run pair

For each pair of adjacent runs (e.g., a run of 0s followed by a run of 1s), the number of valid substrings is min(length of first run, length of second run). Sum these values across all adjacent pairs.

4. Verify with the example

Apply the method to the given input: runs [1,1,5,4] give min(1,1)=1, min(1,5)=1, min(5,4)=4, total 6, matching the expected output.

5. Analyze complexity and edge cases

State that the algorithm runs in O(n) time and O(1) extra space (or O(n) if storing runs). Mention edge cases: all same bits, alternating bits, and empty array.

Key Points to Mention

The two valid patterns: 0...01...1 and 1...10...0, each with equal-length halves.
Contiguity requirement: substrings must be contiguous and cannot skip elements.
Run-length encoding approach: compress the array into runs of identical bits.
Sum of min(adjacent run lengths) gives the total count.
Time complexity O(n) and space complexity O(1) if runs are processed on the fly.
Edge cases: arrays with fewer than 2 elements, all zeros, all ones, and alternating bits.

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