“””
We have an embedded environment with a very simple operating system. Part of the facilities provided to us is a single hardware timer.
The goal is to implement multiple timers, each with their own callback, based on this single timer.
The hardware timer can be set with the following function:
void set_hw_timer(int relative_timeout_ms);
After relative_timeout_ms milliseconds have elapsed, the timer triggers a hardware interrupt, which will call the function: void handle_hw_timer();
Only one hardware timer may be pending. Calling set_hw_timer again before the timer has expired will reset the expiration to the new value without triggering the interrupt.
There is also a utility function:
int64_t get_current_time();
which returns the time in milliseconds that have elapsed since boot.
We would like to allow an arbitrary number of timers to be pending. Define the timer structure and implement this function:
void set_timer(struct timer *t, int relative_timeout_ms, void (*callback)());
Each call to set_timer with a different t parameter should yield a different timer.
The timer structure will be allocated by the caller and passed in, but the caller will not touch the contents of it and you may add any fields you want to it.
The callback function should be called after relative_timeout_ms milliseconds have elapsed. It will be called in interrupt context.
You will also need to implement the body of the handle_hw_timer function.
“””
This Google interview problem comes from an embedded setting where you only have one hardware timer, but you need to support many logical timers, each with its own callback. You are given low-level primitives set_hw_timer and get_current_time, plus an interrupt handler handle_hw_timer. You must design a timer struct, implement set_timer so that multiple independent timers can be scheduled, and write handle_hw_timer to manage a data structure (often a min-heap or sorted list) that always arms the hardware timer for the next earliest expiration and invokes the right callbacks in interrupt context.
