Core Concepts - DSA Interview Guide

Level 1: Foundation - Core Concepts

Big O Notation Basics

Big O notation describes how the runtime of an algorithm grows as the input size increases. It helps us compare algorithms and predict performance.

🏠 Real-Life Analogy:

Think of finding a book in different scenarios:

O(1) - Constant Time: You know exactly where the book is (like having the GPS coordinates)
O(n) - Linear Time: You search shelf by shelf until you find it
O(n²) - Quadratic Time: You compare every book with every other book to organize them

TypeScript

// O(1) - Constant Time: Direct array access
function getFirstElement(arr: number[]): number {
    return arr[0]; // Always takes the same time regardless of array size
}

// O(n) - Linear Time: Search through array
function findElement(arr: number[], target: number): boolean {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return true;
    }
    return false;
}

// O(n²) - Quadratic Time: Nested loops
function findDuplicates(arr: number[]): boolean {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] === arr[j]) return true;
        }
    }
    return false;
}

Python

# O(1) - Constant Time: Direct array access
def get_first_element(arr):
    return arr[0]  # Always takes the same time regardless of array size

# O(n) - Linear Time: Search through array
def find_element(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

# O(n²) - Quadratic Time: Nested loops
def find_duplicates(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

OCaml

(* O(1) - Constant Time: Direct array access *)
let get_first_element arr = arr.(0)

(* O(n) - Linear Time: Search through array *)
let rec find_element arr target =
  match arr with
  | [] -> false
  | head :: tail -> 
      if head = target then true 
      else find_element tail target

(* O(n²) - Quadratic Time: Check all pairs *)
let rec find_duplicates = function
  | [] -> false
  | head :: tail ->
      if List.mem head tail then true
      else find_duplicates tail

Complexity	Name	Example	Performance for 1000 items
O(1)	Constant	Array access	1 operation
O(n)	Linear	Linear search	1000 operations
O(n²)	Quadratic	Nested loops	1,000,000 operations

Algorithm vs Data Structure

An algorithm is a step-by-step procedure to solve a problem, while a data structure is a way to organize and store data efficiently.

🏗️ Real-Life Analogy:

Data Structure: Like a filing cabinet - it's how you organize your documents
Algorithm: Like the process of finding a specific document - the steps you follow

TypeScript

// Data Structure: Array to store student grades
class GradeBook {
    private grades: number[] = [];
    
    // Algorithm: Add a grade
    addGrade(grade: number): void {
        this.grades.push(grade);
    }
    
    // Algorithm: Calculate average
    calculateAverage(): number {
        if (this.grades.length === 0) return 0;
        const sum = this.grades.reduce((acc, grade) => acc + grade, 0);
        return sum / this.grades.length;
    }
}

Python

# Data Structure: List to store student grades
class GradeBook:
    def __init__(self):
        self.grades = []
    
    # Algorithm: Add a grade
    def add_grade(self, grade):
        self.grades.append(grade)
    
    # Algorithm: Calculate average
    def calculate_average(self):
        if not self.grades:
            return 0
        return sum(self.grades) / len(self.grades)

OCaml

(* Data Structure: List to store student grades *)
type grade_book = float list

(* Algorithm: Add a grade *)
let add_grade grade grades = grade :: grades

(* Algorithm: Calculate average *)
let calculate_average grades =
  match grades with
  | [] -> 0.0
  | _ -> 
      let sum = List.fold_left (+.) 0.0 grades in
      sum /. (float_of_int (List.length grades))

Key Takeaways:

Data structures organize data; algorithms manipulate data
Choose the right data structure for your algorithm's needs
Good data structure choice can make algorithms more efficient

Ready for the next step?

Now that you understand the core concepts, let's explore fundamental data structures!

Continue to Data Structures →