Hardware interview practice
Verify a balanced-sequence enumerator
Verify a single-request device that streams every balanced sequence of n open and n close tokens in open-first dictionary order.
Starting point
Question code
interface balance_if(input logic clk);
logic rst_n, req_valid, req_ready;
logic [2:0] n;
logic out_valid, out_ready, out_last, out_error;
logic [11:0] token_bits;
logic [3:0] token_count;
endinterfaceReviewed example
Work through one case
Input
n=3; encode open=0 and close=1Expected output
[000111,001011,001101,010011,010101]These five Catalan sequences keep every prefix balanced and appear in open-first dictionary order.
What to cover
Requirements
- For n=0 through 6, generate the complete ordered list and encode token zero as open and token one as close.
- Validate every prefix, exact open/close totals, uniqueness, order, and Catalan result count.
- Emit one empty success for n=0 and one zero-payload final error for n=7.
- Allow only one active request, hold stalls stable, enforce first/completion bounds, and cancel cleanly on reset.