DEV Community

loading...
Cover image for Can you answer this google interview question?

Can you answer this google interview question?

comscience profile image kapeel kokane ・1 min read

The Problem Statement 👨🏾‍💻

There is a continuous stream of numbers that you are supplied with, wherein you get to know the new number added to that stream one at a time. At any given moment, you will be asked the question: what is the median in the current stream of numbers that you have seen so far? and you have to solve the problem with the most efficient solution.

Key Points to consider 🔑

  • What data structure would you use to store the stream?
  • What would be the time complexity of adding a number to the stream data structure that you are using?
  • What would be the time complexity of fetching the real-time median at any given moment?

After giving it a try yourself, watch this video where I cover one of the most optimum solutions for the same problem:

Hope that helped, cheers!✌🏾

Discussion

pic
Editor guide