← Create New Paste

Gray Code in Coding Interviews: Patterns, Proof and Python

3 views
The "Gray Code" problem asks you to generate a sequence of 2^n integers, each written with n bits, so that consecutive numbers differ in exactly one bit, and the first and last also differ in one bit. For n = 2, a valid answer is [0, 1, 3, 2], which in binary is 00, 01, 11, 10. It sounds niche, but it's a good interview question because there are three distinct solutions, and the interviewer can watch how you move from pattern-spotting to a clean formula. Approach 1: backtracking Start at 0, flip one bit at a time, and add any number you haven't visited yet. It works, but you need a visited set and you have to argue that the search never gets stuck. It's fine as an opening idea, but don't stop there. Approach 2: reflect and prefix Look at how the sequence for n grows out of the sequence for n - 1: - n = 1: 0, 1 - n = 2: take [0, 1], then append its mirror [1, 0] with a leading 1 set: 00, 01, 11, 10 - n = 3: take those four, then append the mirrored list with the highest bit set: 000, 001, 011, 010, 110, 111, 101, 100 Why does it work? Inside each half, neighbors already differ by one bit (by induction). At the seam, the last element of the first half and the first element of the mirrored half are the same number except for the new top bit. The same holds at the wrap-around from the last element back to the first. def gray_code(n): result = [0] for i in range(n): top = 1 << i for x in reversed(result): result.append(x | top) return result Approach 3: the closed-form formula The i-th Gray code is i XOR (i >> 1). def gray_code_formula(n): return [i ^ (i >> 1) for i in range(1 << n)] Intuition: going from i to i + 1 flips a run of trailing bits. XORing each bit with its left neighbor cancels all of those flips except one, so exactly one bit of the Gray code changes. Mentioning this, even informally, shows depth. Complexity Both constructive approaches produce 2^n numbers in O(2^n) time, which is optimal because that's the size of the output. Extra space beyond the output is O(1). Follow-ups interviewers like - Convert a Gray code back to binary: XOR all the right shifts together (b = g; while g := g >> 1: b ^= g). - Start from a given number: XOR every element of the standard sequence with that start value. This is the "circular permutation in binary representation" variant. - Real-world uses: rotary encoders, Karnaugh maps, and error reduction in digital communication. A one-sentence mention makes the problem feel less like trivia. How to present it Write out n = 1, 2 and 3 by hand first and point out the mirror. Interviewers love it when the candidate discovers the structure instead of reciting the formula. Then offer the XOR one-liner as an optimization and verify it on n = 3. Under live interview pressure it's easy to lose the thread halfway through an explanation like this. Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, so you can stay organized while you think out loud.
Created Nov 16, 2026 15:58 Expires Nov 16, 2027 15:58