← Design Verification Interviews

Interview Question · Concept

Dynamic Array, Queue or Associative Array

L0 FresherL1 Juniorsystemverilogarraysdata structures
  • Asked at Google

The Question

The interviewer asks

When do you use a dynamic array, a queue and an associative array in a testbench? Give one real use of each.

Reveal the Model Answer

A dynamic array gets its size at run time and keeps it until you resize it. It fits a packet payload whose length is known when the packet is built. A queue grows and shrinks at both ends, so it fits an in-order scoreboard of expected items. An associative array stores only the keys you write. It fits a sparse memory model, or open requests looked up by transaction ID.

Outstanding Reads Looked up by IDAn associative array keyed by read ID holds only the IDs still open. Arrows from the checker to the map are calls; the tokens coming back are what they return. Other arrows show data.
Outstanding reads looked up by IDAn associative array keyed by read ID holds only the IDs still open. Arrows from the checker to the map are calls; the tokens coming back are what they return. Other arrows show data. source Requests IDs 3, 5 and 1000 map exp_data [int] one key peroutstanding read checker on_response() exists, compare,delete dut Responses IDs 5, 9, 3, then 5again final check End of test foreach listsleftover keys output Log one line per response storeexists, read, deleteresponseleftover keys
  1. Store three reads

    Three requests create three keys, and num() returns 3. The key type allows 4 billion IDs, but only these three entries exist.

    Follow the calls, values and waits
    1. data ID 3: a3: Requests → exp_data [int]
    2. data ID 5: b5: Requests → exp_data [int]
    3. data ID 1000: c0: Requests → exp_data [int]
  2. ID 5 answers

    exists(5) returns 1, so the checker reads b5, compares it with the response and prints a match. Then it deletes key 5.

    Follow the calls, values and waits
    1. data ID 5: b5: Responses → on_response()
    2. call exists(5): on_response() → exp_data [int]
    3. return 1: exp_data [int] → on_response()
    4. data b5: exp_data [int] → on_response()
    5. data ID 5: match: on_response() → Log
  3. ID 9 was never issued

    exists(9) returns 0. The checker reports an unexpected response before reading anything, so the default value 0 never reaches a comparison.

    Follow the calls, values and waits
    1. data ID 9: 0: Responses → on_response()
    2. call exists(9): on_response() → exp_data [int]
    3. return 0: exp_data [int] → on_response()
    4. data ID 9: unexpected response: on_response() → Log
  4. ID 3 has wrong data

    Key 3 exists, but its expected data, a3, differs from the response, a4. The checker reports both values and deletes the key.

    Follow the calls, values and waits
    1. data ID 3: a4: Responses → on_response()
    2. call exists(3): on_response() → exp_data [int]
    3. data a3: exp_data [int] → on_response()
    4. data ID 3: expected a3 got a4: on_response() → Log
  5. ID 5 again

    Key 5 was deleted after its first answer, so the second response for ID 5 is caught as unexpected.

    Follow the calls, values and waits
    1. data ID 5: b5: Responses → on_response()
    2. call exists(5): on_response() → exp_data [int]
    3. return 0: exp_data [int] → on_response()
    4. data ID 5: unexpected response: on_response() → Log
  6. End of test

    One key is left. foreach lists ID 1000, a read whose response never came.

    Follow the calls, values and waits
    1. data ID 1000: exp_data [int] → End of test
Read the diagram as text
  • Requests: IDs 3, 5 and 1000
  • exp_data [int]: one key per outstanding read
  • on_response(): exists, compare, delete
  • Responses: IDs 5, 9, 3, then 5 again
  • End of test: foreach lists leftover keys
  • Log: one line per response
  • Requests → exp_data [int]: store
  • on_response() → exp_data [int]: exists, read, delete
  • Responses → on_response(): response
  • on_response() → Log
  • exp_data [int] → End of test: leftover keys

Check presence with exists before every read, and delete each key once it has been answered.

Dynamic d[]Queue q[$]Associative a[key]
SizeSet by new[n]Grows with push, shrinks with popNumber of keys written
Index0 to n-10 to $ (last)Any integral, string or class key
Cheap operationsIndexPush and pop at either end, indexLookup, insert, delete by key
Typical TB usePayload bytesExpected items in orderSparse memory, ID table

Self-Check

Tick each key point you covered in your answer.

What Interviewers Listen For (Fresher)

A good fresher answer gives one real testbench use for each kind. It also says which kind grows and shrinks at both ends.

Cross-Questions

Where the interviewer goes next. Open a node to practise that follow-up.

WhyWhat IfProve ItBreak ItCompareScale It

  1. Dynamic Array, Queue or Associative Array
  2. WhyWhy a Missing Key Reads as a DefaultL1 Junior

    Why does reading a missing associative-array key return a default instead of stopping the simulation?

    Reveal the Model Answer

    The language treats it like an out-of-range read of any array. It returns the element type's default and may print a warning, so every expression still has a value. Stopping would make every speculative lookup fatal. The cost is that a check must call exists() when "absent" and "present with value 0" mean different things.

    Self-Check

    Tick each key point you covered in your answer.

    Misconception

    "Reading the key creates it with value 0, so num() grows."

    A read does not allocate; only a write does. The twin on the root prints one entry after reading a missing key.

    Source IEEE 1800-2017 §7.8.6

  3. CompareGrowing a Queue vs Resizing a Dynamic ArrayL1 JuniorL2 Mid-Level

    Compare appending one element at a time to a queue with growing a dynamic array by d = new[d.size() + 1](d).

    Reveal the Model Answer

    The resize form allocates a new array and copies every element on each call. Building n elements this way costs about n squared copies. push_back on a queue is designed for growth at the end. Use the dynamic array when the size is known once, and the queue when elements arrive one by one.

    Self-Check

    Tick each key point you covered in your answer.

    Misconception

    "new[n](old) resizes the array in place."

    It creates a new array of size n and copies the old contents into it; the old storage is released.

    Source IEEE 1800-2017 §7.5.1

  4. Prove ItSolve 2.1.1: Resize and PreserveSimulator-graded

    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

    Open Problem 2.1.1

  5. What IfWalking an ID Table with ForeachL1 JuniorL2 Mid-Level

    Asked if they iterate the ID table

    What if the end-of-test report walks the ID table with foreach and prints the outstanding IDs? In what order do they come out, and can you delete while walking?

    Reveal the Model Answer

    Keys come out in ascending key order, not insertion order; with signed int keys the standard puts negative keys first. Deleting entries inside the same foreach is undefined, so collect the keys first and delete afterwards.

    Self-Check

    Tick each key point you covered in your answer.

    Tool as Truth

    "Verilator listed 7, 10, -2, so negative keys come last."

    That is a Verilator 5.052 deviation the course measured. The standard orders signed keys numerically, so -2 comes first; unsigned key types avoid the difference.

    Source Lesson 2.3 simulator note (Verilator 5.052 key order); IEEE 1800-2017 §7.9.4

  6. Prove ItSolve 2.3.1: Outstanding Request LookupSimulator-graded

    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

    Open Problem 2.3.1

  7. Scale ItChoosing the Data Structure for an Out-of-Order ScoreboardL2 Mid-LevelL3 Senior

    Your bus allows out-of-order responses between IDs but keeps order within one ID. How do you structure the expected-data store, and what does it cost?

    Reveal the Model Answer

    Use an associative array keyed by ID, where each element is a queue. It matches the ordering rule exactly: look up the ID, compare with the front of its queue, and pop. Lookups stay cheap however many IDs are open, and a non-empty queue at the end is an outstanding request to report. Store handles in the queues rather than copies, and flush the whole table on reset.

    One FIFO per IDAn associative array of queues, one FIFO per ID. Arrows show data: expected values pushed by requests, values popped by the checker, and responses from the DUT.
    One FIFO per IDAn associative array of queues, one FIFO per ID. Arrows show data: expected values pushed by requests, values popped by the checker, and responses from the DUT. source Requests ID 1 expects a1, thenID 2 expects b2 queue exp_q[1] FIFO for ID 1 queue exp_q[2] FIFO for ID 2 checker Checker pops only the queueof the response's ID dut Responses ID 2, then ID 1, thenID 1 again push_backpush_backpop_frontpop_frontresponse
    1. Requests push

      The request for ID 1 pushes a1 onto exp_q[1], and the request for ID 2 pushes b2 onto exp_q[2]. Each ID has its own FIFO.

      Follow the calls, values and waits
      1. data a1: Requests → exp_q[1]
      2. data b2: Requests → exp_q[2]
    2. ID 2 answers first

      The response for ID 2 arrives first. The checker sees that exp_q[2] is not empty, pops its front, gets b2 and reports a match.

      Follow the calls, values and waits
      1. data ID 2: b2: Responses → Checker
      2. data b2: exp_q[2] → Checker
    3. ID 1 answers

      The response for ID 1 pops exp_q[1] and matches a1. Responses for different IDs overtook each other, and no false error appeared.

      Follow the calls, values and waits
      1. data ID 1: a1: Responses → Checker
      2. data a1: exp_q[1] → Checker
    4. One response too many

      A second ID 1 response arrives, but exp_q[1].size() is 0. The checker reports an unexpected response instead of popping a made-up 0.

      Follow the calls, values and waits
      1. data ID 1: a1: Responses → Checker
    Read the diagram as text
    • Requests: ID 1 expects a1, then ID 2 expects b2
    • exp_q[1]: FIFO for ID 1
    • exp_q[2]: FIFO for ID 2
    • Checker: pops only the queue of the response's ID
    • Responses: ID 2, then ID 1, then ID 1 again
    • Requests → exp_q[1]: push_back
    • Requests → exp_q[2]: push_back
    • exp_q[1] → Checker: pop_front
    • exp_q[2] → Checker: pop_front
    • Responses → Checker: response

    Within one ID the queue still enforces request order; across IDs, responses may arrive in any order.

    Self-Check

    Tick each key point you covered in your answer.

    What Interviewers Listen For (Senior)

    A good senior answer builds the structure from the protocol's ordering rule. Without being asked, it adds a flush on reset and an end-of-test check that every queue is empty.

    Wrong Altitude

    "One global queue and search it for the matching response."

    It works, but every response needs a linear search. It also cannot tell a wrong order within one ID from a legal reorder across IDs.

  8. Break ItThe Scoreboard That Remembered Before ResetL1 JuniorL2 Mid-Level

    A test applies reset in the middle of traffic. After reset, the first response for ID 3 fails although the waveform shows the DUT returned the right data for the new request. Here is the log. What is wrong?

    log
    @1200 req  id=3 data=a0
    @1250 RESET asserted (2 requests outstanding)
    @1400 RESET released
    @1450 req  id=3 data=b1
    @1520 resp id=3 data=b1
    @1520 SCOREBOARD ERROR: ID 3: expected a0 got b1
    Reveal the Model Answer

    The scoreboard still holds the expected data of the request that was in flight at reset. So it compares the new response with a0. The DUT legitimately dropped that request; the testbench did not. On reset, flush every expected-data structure, and decide whether a dropped request should be logged or counted.

    An Expectation That Survives Reset
    01234567rst_narvalidarid03rvalidrdata0020exp_q[3] (scoreboard)empty1010, 2020response 20 compared with stale 10
    1. Cycle 1

      Read ID 3 is issued, and the scoreboard pushes its expected data, 0x10, onto exp_q[3].

    2. Cycle 2

      Reset is asserted. The DUT drops the outstanding read, as the spec requires, but the scoreboard keeps 0x10.

    3. Cycle 5

      A new read reuses ID 3. Its expected data, 0x20, queues behind the stale 0x10.

    4. Cycle 7

      The DUT returns 0x20. The scoreboard pops the stale 0x10 and reports ID 3: expected 10 got 20.

    The same bug on a waveform, with data 10 and 20. The DUT forgot the first read at reset; the scoreboard did not.

    Self-Check

    Tick each key point you covered in your answer.

    What Interviewers Listen For (Junior)

    A good junior answer reads the log and sees that the expected value belongs to the request from before reset. It adds a flush of the scoreboard on reset.

    Misconception

    "Reset only matters to the DUT; the testbench just waits for it."

    Every stateful testbench component holds expectations about the DUT. The twin keeps one stale entry and fails a correct response.

    Run It

    An ID-keyed scoreboard across a reset that drops one outstanding request.

    RUNVerilator · simulator service
    Edit the code, then run it
    Expected: ID 3: expected a0 got b1 mismatches=1 FAIL: the scoreboard kept the pre-reset expectation and compared the new response against it
    See the Fix
    module tb;
      // Scoreboard: expected data queued per transaction ID.
      logic [7:0] exp [int][$];
      int mismatches = 0;
      task automatic expect_req(int id, logic [7:0] d); exp[id].push_back(d); endtask
      task automatic got_resp(int id, logic [7:0] d);
        logic [7:0] e = exp[id].pop_front();
        if (e !== d) begin mismatches++; $display("ID %0d: expected %h got %h", id, e, d); end
      endtask
      initial begin
        expect_req(3, 8'hA0);       // request in flight ...
        // ... reset: the DUT drops every outstanding request
        exp.delete();               // the fix: the scoreboard forgets them too
        expect_req(3, 8'hB1);       // ID 3 reused after reset
        got_resp(3, 8'hB1);         // the DUT answers the new request correctly
        $display("mismatches=%0d", mismatches);
        if (mismatches) $display("FAIL: the scoreboard kept the pre-reset expectation and compared the new response against it");
        else $display("PASS: the response matched the post-reset request");
      end
    endmodule
    

    Prints: mismatches=0 PASS: the response matched the post-reset request

    Delivery

    "The DUT must be wrong; the scoreboard says so."

    The log shows the response matching the post-reset request. Debug starts by asking which side holds old state, not by trusting the checker.

    Wrong Altitude

    "Avoid reusing IDs after reset in the test."

    That hides the bug instead of fixing it, and real software reuses IDs freely after a reset.

  9. WhyWhy a Reset Drops Outstanding RequestsL1 Junior

    Why is it legal for the DUT to forget requests at reset instead of finishing them?

    Reveal the Model Answer

    Reset returns the design's state to its defined initial values, and the queues holding outstanding requests are part of that state. Most protocols say transactions in progress at reset are abandoned and that nothing may be signalled until reset is released. The testbench must model the same loss.

    Self-Check

    Tick each key point you covered in your answer.

    Half-Truth

    "A good design should complete in-flight requests before resetting."

    That is a graceful-shutdown feature some designs add, not what reset means. Check the spec rather than assuming it.

  10. What IfA Response That Outlives ResetL1 JuniorL2 Mid-Level

    What if responses can outlive reset, and the next request reuses the same ID?

    Reveal the Model Answer

    Then a late response for the old request can match the new request with the same ID. The scoreboard may pass wrong data, or flag correct data. Give each expected entry extra identity, or wait a quiet period after reset before reusing IDs. Test it with a reused ID and a duplicate response.

    Self-Check

    Tick each key point you covered in your answer.

    Missed Corner

    "Clearing the queue at reset fixes stale IDs for good."

    It removes old expectations, but not responses still in flight. A late one can match a new request with the same ID.

    Source Lesson 2.7 key points

  11. CompareFlushing the Scoreboard vs Tagging EpochsL2 Mid-Level

    Compare flushing the scoreboard on reset with tagging each expectation with a reset epoch number.

    Reveal the Model Answer

    Flushing is simple and correct when the monitors also stop at reset. Tagging every entry with the epoch it was created in lets the checker recognise a late response from before the reset. It can then report that case as its own error instead of mismatching it. Use the epoch scheme when responses can still emerge from pipelines around the reset edge.

    A Stale Entry, Then the Clear on ResetThe scoreboard state for ID 3, first without and then with a clear on reset. Arrows show data, except exp_q.delete(), which is a call.
    A stale entry, then the clear on resetThe scoreboard state for ID 3, first without and then with a clear on reset. Arrows show data, except `exp_q.delete()`, which is a call. monitor Request monitor pushes expected dataper ID monitor Reset monitor waits for negedgerst_n queue exp_q[3] expected data for ID3 checker response() pops the front forthe ID dut DUT returns ID 3 withdata 20 push_backexp_q.delete()pop_frontresponse
    1. Before reset

      A read with ID 3 is issued before reset, and its expected data, 0x10, is pushed onto exp_q[3].

      Follow the calls, values and waits
      1. data 10: Request monitor → exp_q[3]
    2. Reset, no clear

      Reset is asserted and the DUT drops that read. Without a clear, 0x10 stays in the queue and describes a read that no longer exists.

    3. ID 3 is reused

      After reset a new read reuses ID 3. Its expected data, 0x20, lands behind the stale 0x10.

      Follow the calls, values and waits
      1. data 20: Request monitor → exp_q[3]
    4. A false failure

      The DUT returns 0x20, but pop_front hands the checker the stale 0x10. It reports expected 10 got 20, and 0x20 is left behind.

      Follow the calls, values and waits
      1. data 20: DUT → response()
      2. data 10: exp_q[3] → response()
    5. With the repair

      Run it again with the repair. When rst_n falls, exp_q.delete() removes every ID and every entry, so 0x10 is gone.

      Follow the calls, values and waits
      1. data 10: Request monitor → exp_q[3]
      2. call exp_q.delete(): Reset monitor → exp_q[3]
    6. Only new reads remain

      The new read pushes 0x20, and the response pops 0x20 and matches. exp_q.num() is 0 at the end.

      Follow the calls, values and waits
      1. data 20: Request monitor → exp_q[3]
      2. data 20: DUT → response()
      3. data 20: exp_q[3] → response()
    Read the diagram as text
    • Request monitor: pushes expected data per ID
    • Reset monitor: waits for negedge rst_n
    • exp_q[3]: expected data for ID 3
    • response(): pops the front for the ID
    • DUT: returns ID 3 with data 20
    • Request monitor → exp_q[3]: push_back
    • Reset monitor → exp_q[3]: exp_q.delete()
    • exp_q[3] → response(): pop_front
    • DUT → response(): response

    Each entry stands for a read the DUT still owes; reset cancels them all, so the scoreboard must drop them too.

    Self-Check

    Tick each key point you covered in your answer.

    Missed Corner

    "Flushing is always enough."

    A response already on the wires at the reset edge arrives after the flush. It has no matching entry, or it matches a reused ID by accident.

    Source Lesson 2.7 (debug case: stale IDs after reset)

  12. Prove ItSolve 2.7.1: Flush Pending RequestsSimulator-graded

    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

    Open Problem 2.7.1

  13. Scale ItReset in the Middle of a Test Across a Whole EnvironmentL3 Senior

    How do you make mid-test reset work across a whole environment with several agents, scoreboards and running sequences?

    Reveal the Model Answer

    Give reset one owner that broadcasts it, and make every stateful component handle it. Drivers drop their current item and idle the bus, monitors abandon partial transactions, scoreboards flush or bump an epoch, and sequences restart. Then cover reset at each interesting point, such as mid-burst or with a full FIFO. Each component's reset code runs only in those cases.

    Self-Check

    Tick each key point you covered in your answer.

    What Interviewers Listen For (Senior)

    A good senior answer puts mid-test reset in the test plan with its own coverage. It names the failure that happens when one component ignores reset.

    Wrong Altitude

    "End the test at reset and start a new one."

    It avoids the problem in the bench but never tests the DUT's own reset-in-traffic behaviour, which is where real bugs hide.

  14. Prove ItSolve 2.3.3: Out-of-Order Response MatcherSimulator-graded

    Show it, don't just say it: this Silicon Lab problem is graded by the simulator.

    Open Problem 2.3.3

What People Get Wrong

Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.

Misconception

"Reading a key that was never written is an error, so a stray ID is caught by the lookup."

The read quietly returns the element type's default. In the twin a zero-length response for an ID never requested matches that default and passes.

Run It

An ID table checked by reading exp_len[id] directly, then a response for an ID that was never requested.

RUNVerilator · simulator service
Edit the code, then run it
Expected: errors=0 entries=1 FAIL: reading a missing key returned 0, so the stray zero-length response matched
See the Fix
module tb;
  int exp_len [int];            // expected burst length per transaction ID
  int errors = 0;
  task check(int id, int len);
    // The fix: ask whether the ID is outstanding before reading it.
    if (!exp_len.exists(id)) begin errors++; $display("unexpected ID %0d", id); end
    else if (exp_len[id] != len) errors++;
  endtask
  initial begin
    exp_len[7] = 4;
    check(7, 4);                // a real response
    check(9, 0);                // ID 9 was never requested; a zero-length response
    $display("errors=%0d entries=%0d", errors, exp_len.num());
    if (errors == 0) $display("FAIL: reading a missing key returned 0, so the stray zero-length response matched");
    else $display("PASS: the stray ID was reported");
  end
endmodule

Prints: unexpected ID 9 errors=1 entries=1 PASS: the stray ID was reported

Half-Truth

"Use a queue for everything; it can do what the others do."

A queue can be indexed, but finding an ID in it means a linear search per response. With thousands outstanding, the lookup cost dominates the run.

Missed Corner

"A fixed-size array of 2^32 entries models the memory."

That allocates every location up front. An associative array keyed by address stores only the addresses the test touches.

Source IEEE 1800-2017 §7.8

Learn It, Then Prove It