3
\$\begingroup\$

A Brief Context

I recently gave an interview in a company where I was asked this particular question. After the interview was over, the HR gave the feedback that my solution (is correct programmatically) but is monolithic and not scalable. The interview was for frontend developer 2.


Question

Suppose there is a company which does some analytics work and returns data. The company (let's say X) gets a stream of numbers and it calculates average at that instant for all numbers received and returns the average. There could be other companies (let's say Y) which can ask for the average.

Data:   1  3  5  7  9
Avg:    1  2  3  4  5

So, in the above example, the average are calculated by company X.

  • After first no, average is 1,
  • After second no (i.e. 3), average is 2 ((3+1)/2) and so on

At any point in time, companies are only concerned about average at that time (basically, if average is asked after data value 5, you only need to return 3)

The geeksforgeeks link for problem is https://www.geeksforgeeks.org/average-of-a-stream-of-numbers/

Complexity

The solution needs to be O(1) time and O(1) space


My solution:

I wrote a closure in Javascript to save the current average and total number of values encountered so far. Then wrote another function to call it by passing some parameters. The parameters decide whether I should be updating the average or returning it.

function analytics() {
  const data = {
    avg: 0, //the average at that instant
    totalPoints: 0 //total number of values encountered till that point
  }
  return function(value) {
    //if value is not present, return the avg
    if (!value) {
      return data.avg
    }
    const newTotal = data.avg * data.totalPoints + value
    const newTotalP = data.totalPoints + 1
    //update the value for next usage
    data.avg = newTotal / newTotalP
    data.totalPoints = newTotalP
    return data.avg
  }
}

fn = analytics()

/*
 param = {
 	type: //Company Names
 	value: //Value to update
 }
*/

function y({
  type,
  value
}) {
  if (["Y"].indexOf(type) >= 0) {
    return fn()
  } else if (["X"].indexOf(type) >= 0) {
    return fn(value)
  }
}

console.log("get avg", y({
  type: "Y"
}))
console.log("update avg", y({
  type: "X",
  value: 1
}))
console.log("update avg", y({
  type: "X",
  value: 3
}))
console.log("update avg", y({
  type: "X",
  value: 5
}))
console.log("get avg", y({
  type: "Y"
}))
console.log("update avg", y({
  type: "X",
  value: 7
}))
console.log("update avg", y({
  type: "X",
  value: 9
}))
console.log("get avg", y({
  type: "Y"
}))

My concerns/doubts:

  • What did I miss here so that solution is not scalable
  • Any use cases when it might cause issues
  • How can it be re-written to make it scalable

Things the can be assumed won't cause any issues

  • Need not worry about precision issues while calculating the average
  • Need not worry about issues due to Number datatype not able to accomodate very large values
  • Data validation issues
  • Variable names etc (I re-wrote the solution again for codereview, so some names are not correct)

Hope, I am able to explain the situation properly and would like to get more insights here. Also, let me know if anyone needs any further explanation or something is missing

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I've got 2 concerns about your current solution: 1. It doesn't handle 0 at all, the spec says "all numbers" not "all positive integers", you should try to accommodate any valid number. 2. There's nothing saying the average is always a whole number, which could given sufficient inputs cause you serious problems. It's still constant time to store the total and return total/numEntries. \$\endgroup\$
    – scragar
    Mar 5 '20 at 15:56
2
\$\begingroup\$

This is a good first-cut solution to the functional requirement of stated question. However, when you look at it as production code related to two companies (X and Y) these points arise:

  1. Monolithic: The code should be well demarcated across X and Y company logic. A single analytics function is processing all of the logic with an (admittedly, nice) value control. This has merged the implementation into one piece of code. Say, Y no longer needs the average or, maybe needs something else. Change in code for Y will need to engage with the primary logic of X's code.

  2. Scaling: Imagine a new company Z wants to get not just the average but also the number of data points seen by X (the totalPoints). Changing this monolithic analytics code would engage with all of the existing logic.

These are probably not the only points (and they are also both associated with monolithic and scaling issues). I am just trying to imagine some scaling paths and outline the monolithic-nature of this solution.

To get a fair view of this, consider some changes in the requirements and attempt to modify the code to incorporate them. The complexity required in the edit should be reasonably comparable to the requirement (not higher). Contact of the edit with other parts of the implementation should be minimal.

From a different standpoint, this code would be called a prototype of the logic. The production version would need to handle aspects beyond functionality (like: maintainability, scaling, business-logic separation, readability too).

I wonder if you were asked further questions by the interviewer after reading this program. Were they alluding towards these points.

\$\endgroup\$
1
  • \$\begingroup\$ A lot of this makes sense and now I am able to understand the interviewer's view point. There was not a lot of time remaining during interview, so we didn't have much discussion. I recently got the detailed feedback where interviewer was expecting class based approach exposing 2 different methods (one to update and one to return value) which clearly aligns with your explanation also. Thanks for help!! \$\endgroup\$ Mar 15 '20 at 9:04
1
\$\begingroup\$

After getting detailed feedback from the company, below given is the solution which company expected. This also matched with all the points which nik has explained (the accepted answer above).

  • Create a class with 2 different methods. One to update the average (setAverage here) used by company X and other to get the average (getAverage here) which can be used by companies such as Y.

  • By this approach, separations of concerns is there. Similarly if another company Z wants no of values, a new method can be added without modifying the existing functionalities

class Analytics {
  constructor() {
    this.average = 0
    this.noOfValues = 0
  }
  setAverage(value){
    const total = value + this.average*this.noOfValues
    const average = total/(this.noOfValues + 1)
    this.average = average
    this.noOfValues = this.noOfValues + 1
    return average
  }
  getAverage(){
    return this.average
  }
}

const analytics = new Analytics()

console.log("setAverage, no 1: ", analytics.setAverage(1))
console.log("average is", analytics.getAverage())
console.log("setAverage, no 3: ", analytics.setAverage(3))
console.log("average is", analytics.getAverage())
console.log("setAverage, no 5: ", analytics.setAverage(5))
console.log("setAverage, no 7: ", analytics.setAverage(7))
console.log("average is", analytics.getAverage())
console.log("average is", analytics.getAverage())
console.log("setAverage, no 10: ", analytics.setAverage(10))
console.log("average is", analytics.getAverage())

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.