FINAL INTERVIEW PREP

What to prepare for?

So the path to study is like so:

1. Big "O" notation - Done
2. Data structures
   1. Arrays - Done
   2. Linked Lists - Done
   3. Stacks - Done
   4. Queues - Done
   5. Trees - Done
3. Time complexity - Done
4. Space Complexity - Done
5. Pseudocode Implementations - Partially Done

Important Concepts

• In terms of how time complexity expands with the number of inputs an algorithm gets, we can consider an expanding array or hashset or some data structure that is created during the process of an algorithm as to having a space complexity of O(n).
• What I'm trying to say is that if we have a data structures that is created within an algorithm itself, we are creating an algorithm with a space complexity of O(n). This could even be from an expanding array, whenever we add in a new element the array expands and is a size bigger than before, hence the space complexity of O(n).
• A constant space complexity is something like this:

arr = [1,2,3] 
"""
The array size is 3 giving a space complexity of O(3)
But in the grand scheme of things this may be considered as to having
A constant space complexity of O(1)
"""

• So, just to summarize space complexity, it will take up more space when the algorithm causes the data structure in it to expand alongside whatever input comes into it. A space complexity may be constant when there is an unchanging data structure in terms of its size (it does not expand or shrink it maintains its same structure).
• Time complexity on the other hand is different, it records the number of operations undertaken in an algorithm. Time complexity measures how the number of basic operations grows as your input data size ($n$) grows. Refer to the following:

1. Constant Time: $O(1)$

The algorithm takes the exact same amount of time regardless of how much data you have.

• The School Analogy: You have the student's exact ID number, which corresponds directly to a specific locker number. You walk straight to that locker.

• Code Example: Accessing an array index or checking a map key.

def get_first_student(students):
    return students[0]  # Takes 1 step whether there are 10 or 10,000 students

2. Logarithmic Time: $O(\log n)$

The algorithm cuts the search space in half with every single step. It is incredibly fast and scales beautifully with massive amounts of data.

• The School Analogy: The student directory is alphabetized. You open it exactly to the middle. The name you want comes earlier, so you throw away the second half of the book. You repeat this until you find the name.

• Code Example: Binary Search.

def binary_search(sorted_students, target):
    low = 0
    high = len(sorted_students) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_students[mid] == target:
            return mid
        elif sorted_students[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

3. Linear Time: $O(n)$

The time grows in a direct, straight line 1-to-1 with the size of your data. If your data doubles, the time doubles.

• The School Analogy: The student records are in an unsorted pile. You have to look through them one by one from top to bottom.

• Code Example: A single standard loop.

def find_student(students, target_name):
    for student in students:
        if student == target_name:
            return True
    return False

4. Quasilinear Time: $O(n\log n)$

This happens when you perform a logarithmic operation ($O(\log n)$) a linear ($n$) number of times. This is the gold standard speed for efficient sorting.

• The School Analogy: You want to sort a messy pile of student papers alphabetically. You split the pile in half, sort each half, and merge them back together cleanly.

• Code Example: Efficient sorting algorithms like Merge Sort or Quick Sort, or Python’s built-in .sort().

def sort_students(students):
    return sorted(students)  # Built-in Timsort/Merge Sort runs in O(n log n)

5. Quadratic Time: $O(n^2)$

The execution time is proportional to the square of the input size. If your data doubles, your execution time quadruples ($2^2=4$). If data triples, time multiplies by 9. This usually indicates nested loops.

• The School Analogy: You want to check if any two students in the entire school share the exact same birthday. You take the first student and compare them to every other student, then take the second student and compare them to everyone, and so on.

• Code Example: Nested loops (like Bubble Sort).

def print_all_pairs(students):
    for i in range(len(students)):          # Runs n times
        for j in range(len(students)):      # Runs n times inside the outer loop
            print(students[i], students[j])

6. Exponential Time: $O(2^n)$

The time doubles with every single addition to the input size. If $n=10$, it takes around 1,000 steps. If $n=20$, it takes around 1,000,000 steps. This becomes practically impossible to run very quickly.

• The School Analogy: You want to find every possible combination of student groups that could fit inside a specific classroom.

• Code Example: Naive, unoptimized recursive algorithms (like calculating Fibonacci numbers without memoization).

def recursive_fibonacci(n):
    if n <= 1:
        return n
    # Spawns two new function calls for every single call!
    return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)

7. Factorial Time: $O(n!)$

The absolute slowest common time complexity. It grows so blindingly fast that even an input size of $n=20$ could take a modern computer thousands of years to finish.

• The School Analogy: A school bus driver wants to find the absolute shortest driving route to drop off $n$ students at their individual homes, calculating every single mathematical arrangement of stops.

• Code Example: The Traveling Salesperson Problem via brute force, or generating every single permutation of a string.

import itertools

def get_all_permutations(students):
    # Generates n! permutations. 
    # If you have just 13 students, this generates over 6 billion combinations!
    return list(itertools.permutations(students))