DescriptionQ438
Q438FWArchASIC interview problem
Merge frozen per-core crash logs without allocation
TechniquesFirmwareMin-heapAtomic snapshot
DifficultyHard
TopicData Structures
LanguageC
Requirements4 checkpoints
01
Problem
Merge timestamp-sorted crash-log rings from up to eight cores into one deterministic prefix using supplied fixed scratch space, while detecting malformed metadata and concurrent source changes.
Type declarationC
typedef struct{uint64_t ts;uint32_t seq;uint16_t core,code;} trace_t;
typedef struct{const trace_t *p;uint16_t depth,head,count;
const atomic_uint *generation;} view_t;
typedef enum{MERGE_OK,MERGE_TRUNCATED,MERGE_BAD,MERGE_RACE}
merge_status_t;
typedef struct{uint8_t core;uint16_t pos;} heap_node_t;
merge_status_t merge_crash_logs(
const view_t view[], uint8_t core_count,
trace_t out[], uint16_t capacity,
heap_node_t scratch[8], uint16_t *out_count
);Example input and output
Use this case to check your interpretationInput
core0=[(t1,seq0,A),(t4,seq1,D)]; core1=[(t2,seq0,B),(t4,seq1,C)]Output
merged=[A,B,D,C]Explanation
The fixed heap sorts by timestamp, then core ID, then sequence; core 0 therefore wins the equal-timestamp tie at t4.
02
Requirements (4)
- Validate every view, logical wrapped index, source core, total-entry bound, and full per-view order before publishing output.
- Load each change counter with acquire semantics before reading and again after merging; odd or changed counters return a race and zero count.
- Use only the supplied eight-node minimum heap and order by timestamp, then core, then sequence in O(total entries times log active cores) time.
- A short destination returns the exact chronological prefix and truncated status; bad or racing input sets output count to zero.