Removing Every Match from a Queue

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

What IfProve ItBreak ItCompare

1. Removing Every Match from a Queue
2. CompareLocator Methods vs a Hand-Written LoopL1 Junior

   Compare q.find(x) with (x != 5) with a loop that pushes the survivors into a new queue.

   Reveal the Model Answer

   Both build a new queue and both are linear. The locator method states the intent in one line and cannot get an index wrong. The loop can do more in one pass, such as count and log the removed items. In reviews, prefer the method unless the loop does more than filter.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Both build a new queue and both are linear. Key point 2 The locator method states the intent in one line and cannot get an index wrong. Key point 3 The loop can do more in one pass, such as count and log the removed items. Key point 4 In reviews, prefer the method unless the loop does more than filter.

   Half-Truth

   "Locator methods are faster because they are built in."

   The standard sets no complexity for them. Choose them for clarity, and measure if speed matters.

   Source IEEE 1800-2017 §7.12

   • Lesson 2.4Array Methods and with Expressions
3. Break ItDeleting from a Queue Inside a LoopL1 Junior

   Break it: a loop deletes matches in place with q.delete(i) while i counts up. What goes wrong?

   Reveal the Model Answer

   After q.delete(i), every later element moves down one index. The loop then adds 1 to i and skips the element that moved into slot i. So two matches in a row leave the second one behind. Loop down from the end, or build a new queue.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 After q.delete(i), every later element moves down one index. Key point 2 The loop then adds 1 to i and skips the element that moved into slot i. Key point 3 So two matches in a row leave the second one behind. Key point 4 Loop down from the end, or build a new queue.

   Misconception

   "Use foreach and delete inside it; the loop follows the size."

   The standard leaves the result undefined if the array size changes during a foreach. Tools may skip or repeat elements.

   Source IEEE 1800-2017 §12.7.3

   • Lesson 2.4Array Methods and with Expressions
4. What IfCounting with Sum on a Bit ArrayL1 JuniorL2 Mid-Level

   Asked if they count matches with sum()

   What if they count set flags with flags.sum() on a bit flags[8], or total byte lengths with lens.sum()? Predict the output.

   module tb;
     bit  flags [8] = '{default: 1};   // eight set flags
     byte lens  []  = '{100, 100};     // two lengths of 100
     initial begin
       $display("flags.sum()=%0d  with int=%0d", flags.sum(), flags.sum() with (int'(item)));
       $display("lens.sum()=%0d  with int=%0d", lens.sum(), lens.sum() with (int'(item)));
     end
   endmodule
   

   Reveal the Model Answer

   It prints flags.sum()=0 with int=8 and lens.sum()=-56 with int=200. A reduction method returns the element type, so eight 1-bit flags add up modulo 2 and two signed bytes overflow. Cast each item in a with clause, such as flags.sum() with (int'(item)), to make the sum wide enough.

   1. Search for stuck reads

      item stands for each value in turn, and two values exceed 1,000. On an associative array find_index returns their keys, IDs 7 and 12, as a queue.

      Follow the calls, values and waits

      1. data 1500 and 2048 match: age [int] → find_index
      2. data {7, 12}: find_index → ids
   2. Count them

      The cast inside the with clause turns each comparison into a 32-bit 0 or 1, so the sum is 2. Without the cast, the sum is 1 bit wide and 1 + 1 wraps to 0.

      Follow the calls, values and waits

      1. data 0, 1, 0, 1: age [int] → sum
      2. data 2: sum → n
   3. An empty answer

      No value exceeds 5,000, so find returns an empty queue. Check size() before reading element 0 of any result.

      Follow the calls, values and waits

      1. data no match: age [int] → find
      2. data {}: find → ages
   4. The array is unchanged

      None of these calls changed age. Locator and reduction methods only read the collection; sort and the other reordering methods change it.

   Read the diagram as text

   • age [int]: ID 3: 12, ID 7: 1500, ID 9: 40, ID 12: 2048
   • find_index: with (item > 1000)
   • sum: with (int'(item > 1000))
   • find: with (item > 5000)
   • ids: queue {7, 12}
   • n: int: 2
   • ages: queue {}, size() is 0

   • age [int] → find_index
   • age [int] → sum
   • age [int] → find
   • find_index → ids: keys
   • sum → n: one value
   • find → ages: values

   Every locator method returns a queue, even when the answer has one element or none.

   RUNVerilator · simulator service

   Edit the code, then run it

   OutputWaves

   RunReset codeExpected: flags.sum()=0 with int=8 lens.sum()=-56 with int=200

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 It prints flags.sum()=0 with int=8 and lens.sum()=-56 with int=200. Key point 2 A reduction method returns the element type, so eight 1-bit flags add up modulo 2 and two signed bytes overflow. Key point 3 Cast each item in a with clause, such as flags.sum() with (int'(item)), to make the sum wide enough.

   Misconception

   "sum() returns an int, like most functions."

   Its result has the type of the array elements, unless a with expression gives another type. So a bit array sums in one bit.

   Source IEEE 1800-2017 §7.12.3

   • Lesson 2.4Array Methods and with Expressions
   • Problem 2.4.2Wide Population Reduction
5. Prove ItSolve 2.4.2: Wide Population ReductionSimulator-graded

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

   Open Problem 2.4.2

6. Prove ItSolve 2.2.2: Bounded Queue OperationsSimulator-graded

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

   Open Problem 2.2.2

7. Break ItPopping an Empty QueueL1 Junior

   A scoreboard calls exp_q.pop_front() when a response arrives. How does this break when the DUT sends a response nobody asked for?

   Reveal the Model Answer

   Popping an empty queue returns the element type's default, perhaps with a warning, and the scoreboard compares the response against that default. A spurious response of value 0 then passes. Check exp_q.size() first and report an unexpected response.

   Self-Check

   Tick each key point you covered in your answer.

   Key point 1 Popping an empty queue returns the element type's default, perhaps with a warning, and the scoreboard compares the response against that default. Key point 2 A spurious response of value 0 then passes. Key point 3 Check exp_q.size() first and report an unexpected response.

   Misconception

   "An empty pop stops the simulation with an error."

   The standard returns the default value and at most warns, so the test keeps running with a made-up expectation.

   Source IEEE 1800-2017 §7.10.2.4

   • Lesson 2.2Queues and Ordering
   • Problem 2.2.1First FIFO Mismatch