1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ425

Q425FWASIC interview problem

Find a calibration insertion position

TechniquesFWBinary searchLower boundBoundsFlash

DifficultyEasy

TopicFirmware Algorithms

LanguageSystemVerilog

Requirements4 checkpoints

Problem

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.

Type declarationSystemVerilog

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.

Example input and output

Use this case to check your interpretation

Input

table=[10,20,20,40]; key=20

Output

position=1

Explanation

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

Requirements (4)

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