Time & Space Complexity
Before we dive into the list of problems, let’s review an important concept related to technical assessments.
The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.
Note that the time to run is a function of the length of the input and not the actual execution time of the machine on which the algorithm is running on.
The space complexity of an algorithm quantifies the amount of space taken by an algorithm to run as a function of the length of the input.
Asymptotic notations are mathematical tools to represent the time complexity of algorithms for asymptotic analysis.
Big O Notation
Big O is used to describe how quickly an algorithm's runtime grows relative to its input as the input becomes arbitrarily large.
If you solve an algorithm question during an interview, your interviewer might ask you about the runtime of your code.
Learn more in this article from freeCodeCamp.
If Big O is new to you and you'd like an in-depth look, watch this YouTube video:
In addition to Big O Notation, you might also want to learn a little bit about Big Omega and Big Theta. They don't come up as much in most interviews -- but you should still know what they are.
- Big Omega - Used to describe the best case running time for an algorithm.
- Big Theta - Used to describe the exact performance value of the algorithm or a useful, narrow range between upper and lower bounds.