K-th Symbol in Grammar
Asked at DE Shaw
Problem
K-th Symbol in Grammar builds rows of 0s and 1s: row 1 is 0, and each next row replaces every 0 with 01 and every 1 with 10. It asks for the k-th symbol of row n. Rows double in length, so generating them is hopeless for n = 30 — you need to trace the symbol back to its ancestors.
Asked At
| Company | Difficulty | |
|---|---|---|
| DE Shaw | Medium | View all DE Shaw questions → |
How to Think About It
Row n has 2^(n-1) symbols; generating it is exponential.
Key insight: symbol k in row n comes from symbol ceil(k / 2) in row n - 1. If k is odd, it is the first child and equals its parent; if k is even, it is the second child and is the flip of its parent.
That gives a recursion of depth n: kth(n, k) = kth(n-1, (k+1)/2) if k is odd, else 1 - kth(n-1, k/2).
Bit trick: going from row 1 down, the symbol flips once for every step that takes the second child. Those steps correspond exactly to the 1 bits of k - 1. So the answer is popcount(k - 1) % 2.
Walkthrough: n = 2, k = 2: k - 1 = 1 has one set bit -> answer 1 (row 2 is 01).
Optimal Approach
Step 1: Observe that each position's binary path from the root is given by the bits of k - 1.
Step 2: Every 1 bit means "take the second child", which flips the symbol.
Step 3: Return popcount(k - 1) % 2.
n does not even affect the answer, as long as k is within row n.
Time: O(log k). Space: O(1).
What Trips People Up in Real Interviews
Building the rows as strings. Row 30 has over 500 million symbols.
Mixing up which child keeps the parent's value. With 1-indexed k, odd positions keep it and even positions flip it.
Presenting the bit trick without justification. Show the recursive parent relation first, then explain why it reduces to counting 1 bits.
Off-by-one using k instead of k - 1.
Solution Code
def kthGrammar(n, k):
return bin(k - 1).count('1') % 2Frequently Asked Questions
What is the K-th Symbol in Grammar problem?
K-th Symbol in Grammar builds rows of 0s and 1s: row 1 is `0`, and each next row replaces every `0` with `01` and every `1` with `10`. It asks for the `k`-th symbol of row `n`. Rows double in length, so generating them is hopeless for `n = 30` — you need to trace the symbol back to its ancestors.
How do you solve K-th Symbol in Grammar?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask K-th Symbol in Grammar?
K-th Symbol in Grammar is asked at DE Shaw. It is a medium difficulty problem.
What are common mistakes on K-th Symbol in Grammar?
- Building the rows as strings. Row 30 has over 500 million symbols.
- Mixing up which child keeps the parent's value. With 1-indexed `k`, odd positions keep it and even positions flip it.
- Presenting the bit trick without justification. Show the recursive parent relation first, then explain why it reduces to counting 1 bits.
- Off-by-one using `k` instead of `k - 1`.