The Power Consumption Problem

Posted on Mar 18, 2025
tl;dr: A practical firmware design scenario.

Introduction

Suppose your task is to design a firmware for a smart energy monitor that logs power consumption at a 1-second interval. The device should always be able to retrieve the maximum power usage over the last T seconds efficiently. The system should support the following operations:

  • Add a new reading (real-time power measurement in watts).
  • Query the maximum power draw within the last T readings.
  • Your solution should be optimized for minimal memory usage and fast query times

Understanding the Problem

Terms and Terminologies

Firmware: Firmware is software, but software written for electronic devices. We use the word firmware to specify that we’re talking about electronic devices and not web development or any other type of software.

Power:

\[ P = V \times I \]

Power is an electrical value that represents the rate of transfer of energy within an electric circuit. At a foundational level, any electrical device needs both voltage and current to function. Truly, all a device needs is current, but current without voltage is lazy. Voltage is the force that causes current to flow, and when you put voltage and current on the same team, this is power - your phone can’t help but to start charging.

“Logs power consumption”: Logging simply refers to the process of adding a new value to a data structure.

“At a 1-second interval”: We read a new power value every 1 second. If we set out to log power values at a 1-second interval for 5 seconds, we would have exactly 5 values.

“To retrieve”: After logging power values for a certain time period, we want our smart system to tell us the maximum value for the last T seconds quickly. “To Retrieve something” means to request the system to provide it to us efficiently. The term “Query” also means the same thing.

Back to the Problem

Suppose your task is to design firmware for a smart energy monitor that logs power consumption at a 1-second interval. The device should always be able to retrieve the maximum power usage over the last T seconds efficiently. The system should support the following operations:

  • Add a new reading (real-time power measurement in watts).
  • Query the maximum power draw within the last T readings.
  • Your solution should be optimized for minimal memory usage and fast query times.

Function Signatures & Pseudocodes

Function Signatures

// Objects
typedef struct {
    int power[MAX_WINDOW_SIZE];     // Circular buffer for power readings
    int deque[MAX_WINDOW_SIZE];     // Monotonic deque to store indices of max values
    int front, rear;                // Pointers for the deque
    int currentSize, windowSize;    // Current size and max window size
    int index;                      // Tracks the index of the next insertion
} EnergyMonitor;

// Main Functions
void initMonitor(EnergyMonitor *monitor, int windowSize);
void addReading(EnergyMonitor *monitor, int value);
int getMaxPower(EnergyMonitor *monitor);

// Helper Functions
void removeSmallerValuesFromDeque(EnergyMonitor *monitor, int value);
void removeOldElements(EnergyMonitor *monitor);

EnergyMonitor is the object that holds all the internal data and logic necessary to manage the readings. It uses a circular buffer for efficient space usage—once the buffer is full, new values overwrite the oldest ones. We use a monotonic deque, which is a queue that always maintains its values in decreasing order. This allows us to always access the maximum in constant time.

Pseudocodes

I love pseudocode because it allows us to tell the story more effectively without being bogged down by the technicalities.

// Pseudocode for Main Functions

function initMonitor(monitor, windowSize):
    monitor.windowSize = windowSize
    monitor.currentSize = 0
    monitor.front = 0
    monitor.rear = -1
    monitor.index = 0

function addReading(monitor, value):
    idx = monitor.index % monitor.windowSize
    monitor.power[idx] = value
    removeOldElements(monitor)
    maintainDeque(monitor, value)
    monitor.deque[++monitor.rear] = monitor.index
    monitor.index += 1
    if monitor.currentSize < monitor.windowSize:
        monitor.currentSize += 1

function getMaxPower(monitor):
    if monitor.currentSize == 0:
        return "No readings available"
    return monitor.power[monitor.deque[monitor.front] % monitor.windowSize]


// Pseudocode for Helper Functions

function removeSmallerValuesFromDeque(monitor, value):
    while monitor.front <= monitor.rear and
          monitor.power[monitor.deque[monitor.rear] % monitor.windowSize] <= value:
        monitor.rear -= 1

function removeOldElements(monitor):
    if monitor.front <= monitor.rear and
       monitor.deque[monitor.front] <= monitor.index - monitor.windowSize:
        monitor.front += 1

// Pseudocode for main()

function main():
    Create monitor
    Set windowSize = 5
    Initialize monitor with windowSize
    readings = [10, 5, 3, 12, 15, 6, 8, 9, 2]
    For each value in readings:
        Call addReading(monitor, value)
        Print max power using getMaxPower(monitor)

Algorithm Walkthrough

  1. Object: EnergyMonitor
  • Stores recent readings using a circular buffer.
  • Uses a double-ended queue to maintain max values in decreasing order.
  • Tracks size, windowSize, and current index.
  1. initMonitor(monitor, windowSize)
  • Initializes variables.
  • Prepares internal state to begin tracking readings.
  1. addReading(monitor, value)
  • Adds a new power reading every second.
  • Inserts into circular buffer.
  • Calls removeOldElements() to clean up stale data.
  • Calls removeSmallerValuesFromDeque() to preserve descending order.
  • Appends current index.
  • Updates size and index counters.
  1. removeOldElements(monitor)
  • Removes any values outside the current window.
  1. removeSmallerValuesFromDeque(monitor, value)
  • Maintains the property of the deque: largest value always at the front.
  • Removes values from the back that are smaller than the new value.
  1. getMaxPower(monitor)
  • Returns the current maximum power from the last windowSize seconds.
  • Accesses the index at the front of the deque.

Recap

  • Circular buffer ensures \(O(1)\) memory use.
  • Monotonic deque allows fast retrieval of max.
  • Overall time complexity is O(n), since each element is added and removed at most once.

Algorithm Analysis

FunctionTime ComplexitySpace Complexity
initMonitorO(1)O(windowSize)
addReadingO(1)O(windowSize)
getMaxPowerO(1)O(windowSize)

Full Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX_WINDOW_SIZE 1000  // Max window size

typedef struct {
    int power[MAX_WINDOW_SIZE];     // Circular buffer for power readings
    int deque[MAX_WINDOW_SIZE];     // Monotonic deque storing indices of potential max values
    int front, rear;                // Deque pointers
    int currentSize, windowSize;   // Number of readings stored and the window size
    int index;                      // Total number of readings added
} EnergyMonitor;

// Initialize the energy monitor
void initMonitor(EnergyMonitor *monitor, int windowSize) {
    monitor->windowSize = windowSize;
    monitor->currentSize = 0;
    monitor->front = 0;
    monitor->rear = -1;
    monitor->index = 0;
}

// Remove indices from the front of the deque that are outside the current window
void removeOldElements(EnergyMonitor *monitor) {
    if (monitor->front <= monitor->rear &&
        monitor->deque[monitor->front] <= monitor->index - monitor->windowSize) {
        monitor->front++;
    }
}

// Remove indices from the back of the deque if their power values are less than or equal to the new reading
void removeSmallerValuesFromDeque(EnergyMonitor *monitor, int value) {
    while (monitor->front <= monitor->rear &&
           monitor->power[monitor->deque[monitor->rear] % monitor->windowSize] <= value) {
        monitor->rear--;
    }
}

// Add a new power reading
void addReading(EnergyMonitor *monitor, int value) {
    int idx = monitor->index % monitor->windowSize;
    monitor->power[idx] = value;

    removeOldElements(monitor);
    removeSmallerValuesFromDeque(monitor, value);

    // Add new index to rear of deque
    monitor->deque[++monitor->rear] = monitor->index;

    monitor->index++;
    if (monitor->currentSize < monitor->windowSize) {
        monitor->currentSize++;
    }
}

// Get the maximum power reading in the last windowSize seconds
int getMaxPower(EnergyMonitor *monitor) {
    if (monitor->currentSize == 0) {
        printf("No readings available!\n");
        return -1;
    }
    return monitor->power[monitor->deque[monitor->front] % monitor->windowSize];
}

// The system in action
int main() {
    EnergyMonitor monitor;
    int windowSize = 5;

    initMonitor(&monitor, windowSize);

    int readings[] = {10, 5, 3, 12, 15, 6, 8, 9, 2};
    int n = sizeof(readings) / sizeof(readings[0]);

    for (int i = 0; i < n; i++) {
        addReading(&monitor, readings[i]);
        printf("Added %d, Max in last %d readings: %d\n",
               readings[i], windowSize, getMaxPower(&monitor));
    }

    return 0;
}

Conclusion

I find Leetcode problems to be interesting but abstract in nature. The problem in this post is simply the Sliding Window applied to firmware design. In my opinion, practicing problems with practical use cases makes them more retainable and engaging. I hope you learned a thing or two—you can always email me if you’d like to share your feedback.