# Interview Questions - Algorithm, Data Structure

— algorithm, interview — 1 min read

### Disclaimer

These are my revision notes for my job interviews. As a contractor, I have job interviews more often than a permanent employee. Writing down the revision notes does not imply that I am incapable of answering these questions naturally. During interviews, I naturally get nervous, and due to my introversion, I often struggle to clearly articulate what I already know and understand. I simply want to avoid those situations and prepare myself to present myself in the best possible way.

### What is big O?

- Mathematical notation
- Describe the time complexity or space complexity of an algorithm.
- Time complexity of O(n) will have its execution time grow linearly as the input size increases.
- Time complexity is O(1), the algorithm executes in constant time, regardless of input size.
- O(n²) means the time taken will be proportional to the square of the size of input, and so on.

### What is recurrence?

In the context of computer science and algorithm analysis, recurrence is a way of defining a problem in terms of one or more smaller instances of the same problem.

A good example of this is the Fibonacci sequence, where each number is the sum of the two preceding ones. In terms of a recurrence relation, it could be defined as:

`F(n) = F(n-1) + F(n-2)`

with base cases:

`F(0) = 0, F(1) = 1`