VLSI DV Interview Puzzles · All levels

Associative Array Iteration Order

Predict outputs of `first`, `next`, `num`, and `exists`.

Puzzle

Difficulty: Medium · Puzzle 5 of 6 · Topic: Queue and Array Puzzles

Predict outputs of `first`, `next`, `num`, and `exists`.

Code

systemverilog

module p5;
  int aa[string];
  string k;
  bit ok;
  initial begin
    aa["b"] = 2;
    aa["a"] = 1;
    ok = aa.first(k);
    $display("first_ok=%0d k=%s", ok, k);
    ok = aa.next(k);
    $display("next_ok=%0d k=%s", ok, k);
    $display("num=%0d ex_c=%0d", aa.num(), aa.exists("c"));
  end
endmodule

Hint

Associative arrays iterate in index order, not insertion order.

Step-by-step solution

diagram

1) Keys are `"a"` and `"b"`; lexical order gives `"a"` first.
2) `first(k)` returns 1 and sets k to `a`.
3) `next(k)` from `a` returns 1 and sets k to `b`.
4) `num()` is 2 and `exists("c")` is 0.

Answer

Answer: first_ok=1 k=a, next_ok=1 k=b, num=2 ex_c=0

Why candidates get it wrong

People often expect associative iteration to follow insertion order like many software maps.

Interviewer follow-up

What does `aa.next(k)` return if called once more after `k=b`?

Navigate