CODEWITHSUNDEEP
javascriptalgorithmdata-structures
kellymandem
kellymandem

Reputation: 1769

Optimizing solution for space and time

I was recently given a seemingly small JavaScript programming challenge by a developer more senior than I am.

It goes something like:

Write code to continually track the max, min, and avg temperature as new numbers are inserted into a tracker class.

Write a class TempTracker with these methods:

  • A method to insert a new temperature.
  • A method to get the highest temperature we’ve seen so far
  • A method to get the lowest temperature we’ve seen so far
  • A method to get the average of all temps we've seen so far

Optimize for space and time.

Below is my solution (you can find the full source code including tests here).

class TempTracker {
    constructor() {
        this.temperatures = [];
    }

    all() {
        return [...this.temperatures];
    }

    clear() {
        this.temperatures.length = 0;
    }

    count() {
        return this.temperatures.length;
    }

    insert(temperature) {
        if (typeof temperature !== 'number' || Number.isNaN(temperature)) {
            throw new TypeError('must be a number');
        }

        this.temperatures.push(temperature);
    }

    add(temperature) {
        this.insert(temperature);
    }

    get length() {
        return this.count();
    }

    get lowest() {
        return this.check((temperatures) => Math.min(...temperatures));
    }

    get highest() {
        return this.check((temperatures) => Math.max(...temperatures));
    }

    get average() {
        return this.check((temperatures, length) => {
            const totalTemperature = temperatures.reduce(
                (acc, temperature) => acc + temperature,
                // eslint-disable-next-line
                0
            );

            return Number((totalTemperature / length).toFixed(2));
        });
    }

    // should be private method
    check(callback) {
        if (typeof callback !== 'function') {
            throw new TypeError('callback must be a function');
        }

        if (this.length === 0) {
            throw new Error('add at least one temperature value');
        }

        return callback(this.temperatures, this.length);
    }
}

While the code certainly works as intended, I was told that my code is not optimized for space and time, because as the input grows to millions or billions of temperatures, the memory for processing will run out and something else was mentioned along the lines of, it takes linear time O(𝑛).

My knowledge of data structures and algorithms is very hazy at best and I am really trying to improve in that area.

When I asked what I could do to improve the code, I was told to use something else than an array to store the list of temperatures and left to ponder over which makes the most sense for this use case.

Of the available data structures (at least that I am aware of) in JavaScript, the only ones I could think of were Sets and Float32Arrays.

Could I get guidance on which is one is better and why, plus on how to improve my solution to "optimize for space and time"?

Upvotes: 1

Views: 124

Answers (2)

trincot
trincot

Reputation: 350760

For the given requirements you don't really need to store all individual temperatures... there is no requirement for having an all method.

You actually only need to maintain the minimum, maximum, sum and count. With those 4 numbers you can do all that is needed:

class TempTracker {
    constructor() {
        this._low = Infinity;
        this._high = -Infinity;
        this._count = 0;
        this._sum = 0;
    }

    insert(temperature) {
        if (typeof temperature !== 'number' || Number.isNaN(temperature)) {
            throw new TypeError('must be a number');
        }
        this._low = Math.min(temperature, this._low);
        this._high = Math.max(temperature, this._high);
        this._count++;
        this._sum += temperature;
    }

    get lowest() {
        if (!this._count) throw new Error("no data");
        return this._low;
    }

    get highest() {
        if (!this._count) throw new Error("no data");
        return this._high;
    }

    get average() {
        if (!this._count) throw new Error("no data");
        return Math.round(this._sum * 100 / this._count) / 100;
    }
}

Upvotes: 2

Paul Hankin
Paul Hankin

Reputation: 58319

You don't need any complex datastructures for this task, you just need to keep a track of:

  • the largest temperature seen so far
  • the smallest temperature seen so far
  • the sum of the temperatures seen so far
  • the number of temperatures seen so far

This requires O(1) space and each of the stated operations takes O(1) time (to get the average, divide the sum of the temperatures by the number of temperatures).

Upvotes: 4

Related Questions