• farazbabar 4 hours ago

    This is similar to an approach I use but instead of a queue, I accomplish this using a ring buffer that wraps around and overwrites entries older than window size. We maintain a global window aggregate, subtract ring buffer slot aggregate for entries dropping out and accumulate new entries into new slot aggregate while adding it to the global aggregate. Everything is o(1) including reads, which just returns the global window aggregate.

    • agnishom 2 days ago

      This is a very interesting algorithm which is more or less known in the folklore, but is still relatively obscure. I have used it as a part of temporal logic monitoring procedure: https://github.com/Agnishom/lattice-mtl/blob/master/src/Moni...

      • Groxx 4 hours ago

        Not sure I'd call it obscure: https://leetcode.com/problems/maximum-subarray/

        I've seen it in tech interviews for years.

        • JohnKemeny 22 minutes ago

          The blog post discusses something else than just sum.

          Given an n length array of integers, and an integer k, output the max value for each k sized contiguous subarray.

          sum is much easier than max.