Skip to question
asic.fyi

Hardware interview practice

Merge frozen per-core crash logs without allocation

HardData StructuresC

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.

Starting point

Question code

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
);
Reviewed example

Work through one case

Input
core0=[(t1,seq0,A),(t4,seq1,D)]; core1=[(t2,seq0,B),(t4,seq1,C)]
Expected output
merged=[A,B,D,C]

The fixed heap sorts by timestamp, then core ID, then sequence; core 0 therefore wins the equal-timestamp tie at t4.

What to cover

Requirements

  1. Validate every view, logical wrapped index, source core, total-entry bound, and full per-view order before publishing output.
  2. Load each change counter with acquire semantics before reading and again after merging; odd or changed counters return a race and zero count.
  3. 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.
  4. A short destination returns the exact chronological prefix and truncated status; bad or racing input sets output count to zero.