The Big-Tech Silicon Interview Master Vault

A 2:1 MUX computes Y = S ? B : A. Tie A = 0 and it becomes Y = S & B - an AND gate. So each AND costs one MUX with its low input grounded.

For four inputs build a tree: two MUXes produce a&b and c&d, and a third ANDs those. Three MUXes, two levels deep.

Volunteer the follow-up: "A chain also works with three MUXes but is three levels deep. The tree is the same area and one level faster." → Volume 2.1

Four NANDs.

Expanding, n2 = (a·b')' and n3 = (a'·b)', so the final NAND gives a·b' + a'·b - XOR.

Follow-up: "Why does anyone care about NAND-only?" NAND is functionally complete and, in static CMOS, cheaper than AND or OR - an AND is physically a NAND followed by an inverter. Standard cell libraries are NAND/NOR heavy for that reason. → Volume 2.1

Start from Y = (A·~S) + (B·S) and apply De Morgan:

With ~S = NAND(S, S) that is four NAND gates: one inverter, two product terms, one combiner. → Volume 2.1

A priority encoder. casez expresses it literally:

always @(*) begin
  valid = |din;
  casez (din)
    8'b1???????: pos = 3'd7;
    8'b01??????: pos = 3'd6;
    8'b001?????: pos = 3'd5;
    8'b0001????: pos = 3'd4;
    8'b00001???: pos = 3'd3;
    8'b000001??: pos = 3'd2;
    8'b0000001?: pos = 3'd1;
    8'b00000001: pos = 3'd0;
    default:     pos = 3'd0;
  endcase
end

Say the trade-off: "Priority is real logic - it costs depth, because each bit must know no higher bit was set. For a wide input I would build it as a tree of 'any bit set in this half' terms rather than a linear chain." Also mention valid: without it, position 0 is ambiguous with "no bits set". → Volume 2.1

A balanced adder tree, not serial accumulation. Pair the 32 bits into 16 two-bit sums, then 8 three-bit, 4 four-bit, 2 five-bit, 1 six-bit - 5 levels, not 32. Widths grow only as needed, so early levels are nearly free.

Pre-empt the follow-up: "At 2 GHz I would pipeline it - five levels makes a natural two- or three-stage pipeline." → Volume 2.5

Subtracting one from a power of two clears the single set bit and sets everything below it, so the AND is zero. The n != 0 term is required - zero would otherwise pass.

The same expression checks that a one-hot FSM state has not been corrupted. → Volume 4.5

Equivalently: adding two numbers of the same sign must produce that sign. If it does not, the result wrapped. Opposite-signed operands can never overflow.

The distinction being tested: "C_out alone signals unsigned overflow. The adder hardware is identical for signed and unsigned - signedness exists only in how you interpret the result, which is why an ALU produces both flags and lets the instruction choose." → Volume 2.3

wire [W-1:0] b_in = b ^ {W{sub}};        // XOR row: inverts when sub = 1
assign {cout, result} = a + b_in + sub;  // the spare carry-in supplies the +1

Cost: W XOR gates. Volunteer this: "For subtraction cout is a not-borrow flag - it is 1 when A ≥ B unsigned, which is how unsigned less-than comes out for free." → Volume 2.2

A ripple carry adder's carry is a serial dependency - bit i waits for bit i-1, so delay is O(N). CLA computes G = A·B and P = A ⊕ B for every bit simultaneously (they depend only on the inputs), then derives each carry as a flat sum-of-products. Delay becomes O(log N).

The cost, raised unprompted: "A flat 64-bit CLA would need a 64-input AND gate and p[0] driving 64 loads - both physically impossible. Real adders build it in 4-bit blocks with group generate and propagate, then a second level of lookahead across the groups." → Volume 2.2

Decompose the shift amount into its binary digits and build one stage per digit: stage i shifts by 2ⁱ or passes through, controlled by shamt[i].

log₂(N) stages of N 2:1 MUXes, and the delay does not depend on how far you shift. Replace the fill bits with the bits falling off the bottom and the same structure becomes a rotator. → Volume 2.3

Register the signal once and compare it with itself:

reg sig_d;
always @(posedge clk or negedge rst_n)
  if (!rst_n) sig_d <= 1'b0;
  else        sig_d <= sig_in;

assign rise = sig_in & ~sig_d;   //  0 -> 1
assign fall = ~sig_in & sig_d;   //  1 -> 0
assign both = sig_in ^ sig_d;    //  any change

Two follow-ups to pre-empt: "If sig_in is asynchronous it must pass through a 2-FF synchronizer first, or the flop can go metastable. And these outputs are combinational, so they glitch - if the consumer is in another domain, register them." → Volume 5.2

Divide by 4 - an even divisor, so two cascaded toggle flip-flops give an exact 50% duty cycle by construction. No counter decode needed.

Open with this instead and you will stand out: "Before dividing I would ask whether a real 25 MHz clock is needed or just slower logic. A derived clock creates a second domain with its own skew and constraints. If the logic just needs to run four times slower, a clock enable on the original 100 MHz clock is strictly better - one domain, no CDC, trivial timing." → Volume 3.5

Odd division needs the output high for 1.5 input periods, and you cannot get half a period from rising edges alone - so use the falling edge too.

Run two modulo-3 counters, one on posedge and one on negedge, decode each to a wave high for 2 of 3 states, and AND them. The negedge copy is offset by half a period, so the AND is high for 2T - 0.5T = 1.5T out of 3T - exactly 50%.

Say this unprompted and you have shown you have built one: "That final AND is a combinational gate on a clock, so it can glitch. In an ASIC flow it must be a proper clock-gating cell from the library, not an ordinary AND2." → Volume 3.5

reg [1:0] sync;
always @(posedge clk or negedge arst_n)
  if (!arst_n) sync <= 2'b00;              // ASSERT: async, immediate
  else         sync <= {sync[0], 1'b1};    // DE-ASSERT: shifts in on clock

assign rst_n = sync[1];

Recovery is the minimum time reset must be de-asserted before the next clock edge - the setup-time equivalent for the reset pin. Violate it and the flop can go metastable on reset release.

The systemic reason it matters: "Reset reaches tens of thousands of flops through different wire delays. If it releases near a clock edge, some flops leave reset a cycle before others - half the design starts on cycle N and half on N+1. Asserting asynchronously is safe; the release is the dangerous half. And you need one synchronizer per clock domain." → Volume 3.2

Maximal length comes from tap positions corresponding to a primitive polynomial over GF(2) for that width. The sequence then visits 2ⁿ - 1 states before repeating.

All zeros is a dead state. The XOR of any number of zeros is zero, so the register shifts in a zero forever. That is precisely why the period is 2ⁿ - 1 and not 2ⁿ.

The variant they probe with: "With XNOR feedback the dead state is all ones instead, for the same reason. FPGAs often prefer XNOR because registers power up to zero, so the LFSR self-starts without an explicit non-zero seed." → Volume 3.4

Three stages, in this order:

1. Synchronize - the switch is asynchronous, so two flops first.
2. Filter - require the synchronized level to be stable for N counts (typically 10-20 ms worth) before accepting it.
3. Edge-detect - produce a one-cycle pulse from the accepted level.

The point of the question is whether you remember step 1. A debouncer that filters an unsynchronized input still has a metastable flop at its front door. → Volume 5.2

A binary counter can change several bits at once - 0111 → 1000 flips four. Another clock domain sampling mid-transition can read a value that never existed. A Gray counter changes exactly one bit per step, so a mistimed sample returns either the old value or the new one.

Two caveats worth volunteering: "Keep the binary counter alongside - you need binary for arithmetic and Gray only for crossing. And single-bit stepping only holds when the count wraps at a power of two." → Volume 3.3

An XOR prefix chain - each binary bit is the XOR of all Gray bits from the MSB down:

The asymmetry is the interesting part: "Binary→Gray is one XOR per bit in parallel. Gray→binary is a serial XOR chain, O(N) deep unless built as a prefix tree. That is why an async FIFO Gray-codes on the way out and never converts back on the far side." → Volume 6.3

A fixed-priority arbiter always grants the lowest-numbered requester, so a busy low channel starves the others. Round-robin rotates the priority base: after granting channel k, priority starts at k+1 next time.

The standard implementation is two priority encoders - one masked to requests above the pointer, one unmasked - taking the masked result if any, otherwise the unmasked one (which wraps around).

Volunteer the property being tested: "The guarantee is bounded wait - no requester waits more than N-1 grants. That is what makes it fair, and why round-robin appears in every shared-bus and NoC design." → Volume 4.4

The method matters more than the answer. Name each state after the longest prefix of 1011 the stream currently ends with: - , 1, 10, 101, 1011. Then for each state and input bit, append it and ask what the longest prefix is now. Transitions fall out mechanically and overlap handling is automatic.

From 1011 on a 0 you go to state 10, because the stream now ends …10110 whose longest useful suffix is 10.

Moore needs 5 states and asserts a cycle later; Mealy needs 4 and asserts in the same cycle, at the cost of a combinational input-to-output path. → Volume 4.1

Worked: T = 5 ns, skew = 0.10, t_su = 0.15, t_unc = 0.05, t_cq = 0.25, t_comb = 3.80 → setup slack = +0.85 ns, T_min = 4.15 ns → f_max ≈ 241 MHz.

Point at what is missing: "T does not appear in the hold equation. A hold violation therefore fails at every frequency including DC, and positive skew helps setup while hurting hold." → Volume 7.2

Yes. Two separate problems, and candidates usually name only the first.

1. Metastability - solved by a two-flop synchronizer, which gives the first flop a full destination period to resolve.
2. Missed data - not solved by a synchronizer. The destination samples half as often, so a one-cycle pulse in the fast domain (5 ns) can vanish entirely between two 10 ns destination edges. A level must be stable for at least 1.5 destination clock periods to be caught reliably.

The fix depends on the traffic: toggle synchronizer for single pulses, handshake for occasional multi-bit transfers, asynchronous FIFO for sustained throughput. → Volume 5.2

Because each bit resolves its metastability independently. Bits that left the source on the same edge can arrive on different edges, so the destination latches a mixture of old and new - a value that was never on the bus.

Concretely: a counter crossing 0111 → 1000 where bit 3 resolves a cycle early is sampled as 1111. Every individual synchronizer worked perfectly; the system is still broken.

The unifying answer: "Gray code, a held-stable bus with a synchronized flag, a handshake, or an async FIFO - they all work by reducing the crossing to a single bit." → Volume 5.3

Both full and empty put the pointers at the same address, so the address bits alone cannot distinguish them. Make each pointer one bit wider than the address - that bit counts laps.

count works because two's complement subtraction wraps correctly. Also qualify the enables - do_wr = wr_en && !full - so a write when full is a harmless no-op rather than silent corruption. → Volume 6.2

Burst duration = 120 / 80 MHz = 1.5 µs. Items read in that time = 50 MHz × 1.5 µs = 75. Depth = 120 - 75 = 45 → round up to 64 for a Gray-pointer FIFO.

Use effective rates: if the writer only writes on one clock in two, its effective rate is 40 MHz, not 80. Round the read count down - assuming the reader kept up better than it did would under-size the FIFO.

The trap version: "What if the writer never stops?" Then no finite depth works - occupancy grows without bound. FIFO depth only solves bursts. Sustained overload needs back-pressure, or a defined drop policy if the source cannot be stalled. → Volume 6.4