Google L3 Interview

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:

uint64_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.