Skip to question

Q101FreeSystemVerilog

Find the longest unique token run

Difficulty
Medium
Topic
Streaming Algorithms
Language
SV
Interview prompt

Question

For each bounded protocol-token frame, report the longest contiguous run containing no repeated token ID, including its inclusive start and end indices. Supply 1 through 64 accepted tokens and assert in_last only on the final accepted token.

Candidate starting point

Implementation scaffold

module longest_unique_token_run (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       in_valid,
  input  logic       in_last,
  input  logic [3:0] token,
  input  logic       result_ready,
  output logic       in_ready,
  output logic       result_valid,
  output logic [6:0] best_length,
  output logic [5:0] best_start,
  output logic [5:0] best_end
);
  typedef enum logic [1:0] {S_CLEAR, S_INPUT, S_RESULT} state_t;
  state_t state_q;

  logic last_valid_q [0:15];
  logic [5:0] last_index_q [0:15];
  logic [3:0] clear_q;
  logic [5:0] index_q, window_start_q;
  logic [6:0] best_length_q, result_length_q;
  logic [5:0] best_start_q, best_end_q;
  logic [5:0] result_start_q, result_end_q;

  logic [5:0] next_window_start;
  logic [6:0] current_length;
  logic current_is_better;

  always_comb begin : advance_unique_window
    // TODO: Implement advance_unique_window using the supplied state and interface.
  end

  assign in_ready      = (state_q == S_INPUT);
  assign result_valid  = (state_q == S_RESULT);
  assign best_length   = result_length_q;
  assign best_start    = result_start_q;
  assign best_end      = result_end_q;

  always_ff @(posedge clk) begin : clear_capture_and_publish
    // TODO: Implement clear_capture_and_publish using the supplied state and interface.
  end
endmodule
Reviewed example

Trace one case

Input
accepted token frame = [1, 2, 1, 3, 4, 3]
Expected output
best_start=1; best_end=4; best_length=4; run=[2, 1, 3, 4]

The repeated 1 advances the window start to index 1, and the later repeated 3 closes the longest unique run.

What to cover

Requirements

  1. Support token IDs 0 to 15 and frame lengths from 1 to 64.
  2. Track only accepted tokens; bubbles and downstream backpressure must not change indices.
  3. Never move the current window start backward when a repeated token lies before the active window.
  4. On equal maximum lengths, keep the run with the earliest start index.
  5. Clear or invalidate last-seen state between frames and hold the final result stable.
Continue practicing
Q1153 · Reference ModelsModel a recent-ID replay streamHardPQ973 · Reference ModelsDebug a signed sliding-window peakMediumP