PPractick

The problem

A lighting controller drives a row of n lamps. To avoid overheating, no two adjacent lamps may be on at the same time. The test team wants every allowed on/off pattern listed, written as binary strings of length n, in increasing (lexicographic) order, so they can run through them one by one. Generating all 2ⁿ strings and filtering wastes most of the work. Backtracking builds only valid strings: a 0 can always be appended, and a 1 only when the previous character isn't 1.

Example: n = 3 → 000 001 010 100 101.

Function signature

vector<string> generateBinaryStrings(int n);  // in lexicographic order

Test cases

Input n	Output	Explanation
3	000 001 010 100 101	011, 110 and 111 have adjacent 1s
2	00 01 10
1	0 1
4	0000 0001 0010 0100 0101 1000 1001 1010	8 strings
5	13 strings	The counts follow Fibonacci numbers

(Confirm: 1 ≤ n ≤ about 20; the output must be in lexicographic order.)

How interviewers phrase it

• "Generate all binary strings of length n without consecutive 1s" (GeeksforGeeks).
• Related: "count binary strings without consecutive 1s", which is a Fibonacci DP.

Clarifying questions to ask

1. Is a string with a single 1 allowed at the start or end? (Yes, only adjacent 1s are forbidden.)
2. Must the output be sorted?
3. How large can n be? (The output itself grows like Fibonacci numbers.)

Follow-ups to expect

1. "Why try 0 before 1?"
2. "How many strings are there?"
3. "What's the complexity?"
4. "How would you count without generating?"
5. "Bitmask check?"

Related questions

• Generate Parentheses Medium
• Power Set Medium
• Combination Sum Medium
• Combination Sum II Medium
• Subsets I Medium
• Subsets II Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in