Skip to question
asic.fyi

Hardware interview practice

Find a calibration insertion position

EasyFirmware AlgorithmsSystemVerilog

Return the first position in a nondecreasing calibration table whose value is at least a requested key, or the table length when no such entry exists.

Starting point

Question code

typedef enum { SEARCH_OK, SEARCH_EINVAL } search_rc_t;
search_rc_t find_insert_pos(const uint16_t *table,
                            size_t count,
                            uint16_t key,
                            size_t *position);
// count <= 64; table is nondecreasing.
Reviewed example

Work through one case

Input
table=[10,20,20,40]; key=20
Expected output
position=1

The half-open lower-bound search returns the first duplicate whose value is not less than the key.

What to cover

Requirements

  1. Use a half-open [lo, hi) search and a midpoint that cannot overflow.
  2. Resolve a duplicate run to its first index and never read table[count].
  3. Allow an empty table with a null table pointer and return position zero.
  4. Reject an invalid output, count above 64, or null nonempty table without changing the saved output.
Continue practicing
ArraysFind lower and upper bounds