DATA STRUCTURES & ALGORITHMS CHEAT SHEET

(Quick Guide)
What are Data Structures?
Data structure is a storage that is used to store and organize data. It is a way of arranging data on a
computer so that it can be accessed and updated efficiently. Each data structure is good and is
specialized for its own thing. Think of it like a filing system where you put information in different folders or
boxes so you can easily find and use it later.

Operations On Data Structures

• Insertion: This means adding new data to a collection, like putting a new file (apple) into a folder on
your computer.

• Deletion: This is removing data, like taking an item (mango) off your shopping list.

• Traversal: This means going through each item one by one, like flipping through pages of a book to
look at each word.

• Searching: This is trying to find something in the data, like looking for a specific contact in your
phone.

• Sorting: This means arranging data in order, like organizing books on a shelf alphabetically.

• Access: This is how we retrieve the data we’ve stored, like opening a document on your computer to
read it.

some common types of data structures

• Array: A collection of items stored at contiguous memory locations, like a row of boxes where each
box holds a value, and you access them using their index (position).

• Linked List: A sequence of elements where each element points to the next one, like a chain where
each link is connected to the next.

• Stack: A collection that follows the Last In, First Out (LIFO) principle, like a stack of plates where
the last plate placed on top is the first one removed.

• Queue: A collection that follows the First In, First Out (FIFO) principle, like a line of people waiting
to buy tickets—first in line, first to leave.

• Tree: A hierarchical structure with a root and branches, like a family tree where each person can
have children, and those children can have their own children.
• Graph: A set of nodes (or vertices) connected by edges, like cities connected by roads on a map,
where you can move from one node to another based on their connections.

• Hash Table (or Hash Map): A collection that stores data in key-value pairs, like a dictionary where
each word (key) has a corresponding definition (value).

Arrays
An array is a data structure that holds a fixed number of elements, all of the same type,
in contiguous memory locations. Each element in the array can be accessed using its
index, starting from 0 for the first element.

Insertion:
Adding an element to the array at a specific index.

• Example: If we have {10, 20, 30, 40}, inserting 25 at index 2 will make it {10, 20, 25, 30,
40}.
• Time Complexity: O(n) if you need to shift elements.

Deletion:
Removing an element from a specific index and shifting other elements.

• Example: Removing 30 from {10, 20, 30, 40} will result in {10, 20, 40}.
• Time Complexity: O(n) due to shifting.

Traversal:
Visiting each element of the array one by one.

• Time Complexity: O(n).

Searching:
Finding an element by its value or index.

• Linear Search (O(n)): Goes through each element until it finds the one you're
looking for.
• Binary Search (O(log n)): If the array is sorted, it can divide and conquer to find
an element faster.
Sorting:
Arranging the elements in increasing or decreasing order.

• Algorithms like QuickSort (O(n log n)) and BubbleSort (O(n²)) can be applied

Advantages of Arrays:
Direct Access:
Arrays provide fast and direct access to any element using its index, which makes it efficient for read
operations.

• Time Complexity: O(1) for accessing elements.

Memory Efficiency:
Arrays use contiguous memory, so they are efficient in terms of memory usage compared to some
other data structures that require extra memory for pointers or links.

Ease of Use:
They are simple to understand and use. Most programming languages have built-in support for
arrays.

Best for Fixed-Size Data:

If you know the number of elements in advance and the collection size won’t change, arrays work
well.

Disadvantages of Arrays:
Fixed Size:
Once an array is created, you cannot resize it. If you need to store more elements than you originally
planned for, you'll need to create a new, larger array and copy the data over.

• Example: You can't add a 6th element to a {10, 20, 30, 40, 50} array if its size is fixed to 5.

Inefficient Insertions and Deletions:

To insert an element in the middle of the array, you have to shift all the elements after
it to make space. Similarly, when you delete an element, all subsequent elements must
be shifted to fill the gap.

• Time Complexity: O(n) for both insertion and deletion.

Wasted Memory:
If you allocate an array larger than necessary (to avoid resizing), you might end up with
unused space, which can waste memory.

Linear Search Can Be Slow:

Unless the array is sorted and you can use binary search, finding an element requires
checking each item one by one.

When to Use an Array:

-> When you know the number of elements you need to store in advance.
-> When fast access to elements by index is required.
-> For storing collections of similar data, like scores, temperatures, or a list of names
where size doesn’t change frequently.

When Not to Use an Array:

-> When the number of elements is dynamic and can change frequently.
-> When you need efficient insertions or deletions, especially in the middle of the data.

Hash Table
A hash table (or hash map) is a data structure that stores data in key-value pairs. It
uses a hash function to compute an index (or hash code), where the value
corresponding to a particular key is stored. This allows for fast access to the values
based on their keys.
what does hash function means?
A hash function is like a special formula that takes a key (like a word, number, or name) and converts
it into a unique number, which is called a hash value or hash code. This number tells us where to
store or find the data in a hash table.
In simple terms, a hash function helps convert a piece of data (key) into a number that tells us where
to store or find it quickly in a hash table, without searching through all the lockers (or data).

Operations on Hash Tables:

Insertion:
Adding a new key-value pair to the hash table.

• Example: Storing "Alice" -> 12345 in a phone book.

• Time Complexity: O(1) on average.

Deletion:
Removing a key-value pair from the hash table.

• Example: Removing "Bob" -> 67890.

• Time Complexity: O(1) on average.

Search:
Finding the value associated with a given key.

• Example: Finding the phone number for "Alice".

• Time Complexity: O(1) on average.

Traversal:
Visiting every key-value pair in the hash table.
 • Time Complexity: O(n) where n is the number of elements in the hash table.

Advantages of Hash Tables:

Fast Lookups:
Hash tables provide O(1) average time complexity for search, insertion, and deletion. This makes
them one of the fastest data structures for these operations.

Efficient for Large Data Sets:

Hash tables perform well with large collections of data because the time to access any element is
constant, assuming a good hash function and few collisions.

Flexible Key Types:

Keys can be of various types—strings, numbers, or even objects—provided that the hash function can
handle them.

Disadvantages of Hash Tables:

Collisions:
If two keys hash to the same index, it’s called a collision. Hash tables need a way to handle collisions,
typically through chaining (storing multiple values at the same index) or open addressing (finding
another index). Collisions can degrade performance.

Memory Overhead:
Hash tables often use more memory than other data structures because they require extra space for
the hash function and to handle collisions.

Unordered:
Hash tables do not maintain the order of elements. If you need to store elements in a specific order, a
hash table is not a good choice.

Poor Worst-Case Performance:

In the worst case (with many collisions), the time complexity for search, insert, or delete can degrade
to O(n). This happens when the hash function is poor or when the table is too full.
When to Use a Hash Table:
->When you need fast lookups and are dealing with large sets of data.
-> When you need to map keys to values, like in a dictionary where each word (key) has a definition
(value).
-> When you don’t care about the order of elements.

When Not to Use a Hash Table:

-> When the order of elements matters.
-> When the data set is small (simpler structures like arrays or linked lists might suffice).
-> When you have limited memory (hash tables can use more space).

Collision Handling Techniques:

Chaining:
In chaining, each index of the hash table points to a linked list of entries. If two keys hash to the same
index, both are stored in the list.

• Pro: Easy to implement.

• Con: Extra memory for pointers and slower performance if the list grows long.

Open Addressing:
In open addressing, when a collision occurs, the hash table looks for the next available slot based on a
probing sequence (e.g., linear probing or quadratic probing).

• Pro: No need for extra memory for lists.

• Con: More complex and can suffer from clustering, where a group of adjacent cells is filled,
making future insertions slower.

Linked List
A linked list is a linear data structure where elements, called nodes, are stored in a sequence. Each
node contains two parts:

1. Data: The actual value of the node.

2. Pointer (Link): A reference (or link) to the next node in the sequence

Unlike arrays, linked lists don't store elements in contiguous memory locations. Instead, each
element points to the next, forming a chain

A linked list is a way of storing a collection of items, where each item (called a node) points to the
next item. Think of it like a train where each car is connected to the next one.

what is pointer in linked list

a pointer is like a signpost that tells you where something is located rather than holding the item
itself.

Imagine you have a box of toys. Instead of putting the toy directly on a shelf, you have a piece of
paper that says, "The toy is in Box A." This paper doesn't have the toy; it just tells you where to find it.
In computer programming, a pointer works similarly—it holds the address (or location) of a piece of
data in memory instead of the data itself.

Types of linked lists

Singly Linked List

->Each node contains data and a pointer to the next node. The last node points to null, indicating the
end of the list.
->Used for simple implementations where traversal is only required in one direction (forward).
->Simple to implement and uses less memory than other types.
->Cannot traverse backwards and requires a full traversal to find elements.
Doubly Linked List
->Each node contains data, a pointer to the next node, and a pointer to the previous node. The first
node's previous pointer and the last node's next pointer point to null.
->Useful when you need to traverse the list in both directions (forward and backward).
->Allows for easy insertion and deletion from both ends and bidirectional traversal.
->Requires more memory for the additional pointer.

Circular Linked List

->Similar to a singly linked list, but the last node points back to the first node instead of null, forming
a circular structure.
->Often used in applications where you want to cycle through the list repeatedly, such as in round-robin
scheduling
->Can traverse the entire list from any point and useful for applications that require a continuous loop
->More complex to implement and can lead to infinite loops if not managed properly.

Circular Doubly Linked List

->Combines the features of both circular and doubly linked lists. Each node has pointers to both the -
next and previous nodes, and the list is circular.
->Useful for applications that require bidirectional traversal and continuous looping.
->Allows easy traversal in both directions and supports circular movement.
->Requires even more memory for the additional pointers and is more complex to implement.

Stack
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle, meaning the last
element added is the first one to be removed.
Think of a stack as a pile of plates: you always add a new plate on top, and when you need one, you
take it from the top.

Key Operations

1. Push: Add an item to the top of the stack.

2. Pop: Remove the item from the top of the stack.
3. Peek (or Top): Look at the top item without removing it.
4. isEmpty: Check if the stack is empty.

Imagine a stack of books:

 • Push: You keep adding books to the top of the pile.
• Pop: When you want to read a book, you always take the one on top.
• Peek: If you're curious about what book is on top, you just look at it but don't remove it.
• isEmpty: If there are no books left in the pile, it's empty.

Advantages of Stack

Simple to Implement: Easy to understand and use for basic applications like reversing strings or
checking for balanced parentheses.

Efficient Operations: Push and pop operations are fast, with a time complexity of O(1).

Useful in Recursion: Stacks are often used in algorithms that rely on recursion (such as depth-first
search).

Disadvantages of Stack
Limited Access: You can only access or remove the top element; if you need something in the middle,
you’ll have to pop everything above it.

Fixed Size (for Static Stacks): In some implementations, like array-based stacks, the size might be
fixed, which limits how much data you can store.

Not Ideal for Random Access: Stacks are not suitable for situations where you need to access
elements randomly or search for specific items in the middle.

Real-World Use Cases

Undo Functionality: In text editors, stacks are used to track changes. Each time you make a change,
it’s pushed onto the stack. When you hit “undo,” the last change is popped off.

Browser Back Button: Browsers use a stack to keep track of the pages you visit. When you press the
back button, it pops the last visited page off the stack.
Expression Evaluation: Stacks are often used to evaluate expressions, especially in compilers and
interpreters.

Queue
A queue is a linear data structure that follows the FIFO (First In, First Out) principle, meaning the first
element added to the queue is the first one to be removed.

Think of a queue like waiting in line at a grocery store checkout. The first person to get in line is the
first one to be served, and the last person to join the line has to wait their turn.
Enqueue (Add to the queue): When someone joins the back of the line, it's like adding an item to the
end of the queue.

Dequeue (Remove from the queue): When the person at the front of the line is served and leaves,
it's like removing an item from the front of the queue.

Peek: If you want to see who’s first in line without serving them, that’s like looking at the front item
in the queue without removing it.

Use Cases:
->Ticket counter: The first person in line buys the ticket first, and new people join at the back.
->Customer service: Calls are answered in the order they are received, so the first caller gets served
first.

Advantages:

Order Preservation: Items are processed in the exact order they were added
Multiple Implementations: Can be implemented using arrays, linked lists, or circular arrays.
Disadvantages:

Limited Access: Only the front and rear elements can be accessed directly.
Fixed Size: If implemented with arrays, resizing is required for dynamic operations.

Use Cases:
-> Task Scheduling: Queues are used in scheduling tasks like CPU processes.
-> Printing Jobs: Jobs in a printer queue are processed in the order they are received.
-> Breadth-First Search: Used in algorithms to explore nodes layer by layer.

Types of Queues:
Simple Queue: The basic FIFO structure. Just like standing in a straight line. The first person to enter the
line is the first one served (FIFO - First In, First Out). You can only add elements at the rear (end) and remove
them from the front.

Limitations: If implemented with a fixed array, once the rear reaches the end, even if space is available at the
front (after dequeuing), it cannot be reused without shifting elements.

Circular Queue: The last element points back to the first, making the queue circular. Imagine a queue
that wraps around in a circle. After the last position, it loops back to the first, making efficient use of
space.

Useful in systems where memory is limited, like buffering in network routers or managing tasks in a
round-robin fashion.

Makes better use of space compared to a simple queue. When the rear reaches the end, it can still
reuse the free space at the front.
Priority Queue: Elements are dequeued based on priority rather than order. Here, each item has a
priority level, and the highest priority item is served first, regardless of when it joined the queue. It's
like VIP customers always getting to cut in line.

Task management where some tasks are more urgent than others, such as emergency services or
operating systems scheduling processes.

Requires additional computation to sort items by priority when adding them, which can slow down
the enqueue operation.

When elements are added (enqueued), they are placed in the queue according to their priority. This
can be done by sorting the elements, or by using a specialized data structure (like a binary heap) that
efficiently maintains the priority order.
Unlike a regular queue where the front and rear are based on the order in which elements were
added (FIFO), a priority queue doesn't follow this rule.

Instead, it places elements based on their priority. The highest-priority element gets to the front of
the queue, regardless of when it was added.

Double-Ended Queue (Deque): Like a line where you can enter or leave from both ends. You can add
or remove elements from either the front or the rear. Useful in scenarios where you need to quickly
add or remove items from both ends, such as undo/redo operations in software or implementing
sliding windows in algorithms.Very flexible, allowing operations at both ends.

Operations:

• Enqueue Front: Add to the front of the queue.

• Enqueue Rear: Add to the rear (like in a normal queue).
• Dequeue Front: Remove from the front (like a normal queue).
• Dequeue Rear: Remove from the rear.

Imagine you're at a small park bench where you can sit on either side. You can choose to sit on one
end, and if someone else joins, they can sit on the opposite end. Similarly, when leaving, you can get
up from either side, and the same goes for others.

Tree
A Tree is a type of data structure used to organize data in a hierarchical way, like a family tree or an
organization chart. Each element in a tree is called a node, and nodes are connected by edges (links)
that show relationships between them.
Imagine you're organizing your computer's folders. You start with a main folder, and inside it, there
are subfolders, which might contain more subfolders or files. This structure forms a tree, with each
folder or file being a node in the tree.

Key Terms:
->Root: This is the starting node of the tree, like the main folder on your computer. It's the topmost element
that doesn't have a parent.
->Node: Each item in the tree, like a folder or file, is called a node. Nodes can store data (e.g., the name of a
file).
->Edge: The connection between two nodes. For example, when a folder contains a subfolder, there's an edge
between them
->Parent and Child: If a node is connected to another node below it, the top one is called the parent, and the
bottom one is the child. For example, if a folder contains a subfolder, the main folder is the parent, and the
subfolder is the child.
->Leaf: A node that doesn't have any children (like a file in a folder with no subfolders).
->Subtree: A part of the tree itself, like a smaller section of the hierarchy
->Depth/Height: Depth measures how far a node is from the root. Height is how many levels a tree has.
Types of Trees:

Binary Tree: A tree where each node has up to two children (like two arms). It’s one of the simplest
types of trees. Imagine a family tree where each parent can have at most two children. Simple to
understand. Useful for representing simple hierarchical relationships

Binary Search Tree (BST): A special type of binary tree where the left child is always smaller than
the parent, and the right child is always bigger. This makes it faster for searching.

Imagine a Bookshelf:

1. You’re organizing books by their title.

2. You start with a book titled "M" and place it on the shelf. This is your first book and becomes the root
of your bookshelf.
3. Now, whenever you add a new book:
o If the title is alphabetically smaller than "M" (like "B"), you place it on the left side of "M".
o If the title is alphabetically larger than "M" (like "S"), you place it on the right side of "M".

So the basic rule of a BST is:

• Left side of the bookshelf is for books with titles smaller than the current book.
• Right side is for books with titles larger than the current book.
Balanced Tree (like AVL Tree or Red-Black Tree): A binary search tree that keeps itself
balanced, meaning both sides of the tree are nearly equal in size.

Imagine a Bookshelf Again:

• You want to add books but make sure that no part of the shelf gets too heavy. If you pile too many
books on one side, the shelf might get difficult to manage.
• So, after adding a book, you check if both the left side and the right side have a similar number of
books. If one side has more books, you adjust things to keep it balanced.

A balanced tree ensures that both sides are almost equal in terms of height (number of levels of
books).

An unbalanced tree could have one side very deep (lots of books on one side), making it hard to
search through the books efficiently.

A balanced tree ensures:

• Faster searching because both sides are of similar height.

• Better performance for inserting and deleting items since things are always organized in an
efficient way.

Trie (Prefix Tree): A tree used to store strings (sequences of characters). Each path down the tree
represents a word or part of a word. Think of your phone’s predictive text feature. As you type “ca,” it
suggests “cat,” “car,” and “camera” because those words all share the same starting letters. That’s
how a Trie works.

Fast for finding and storing lots of words, especially in auto-complete or dictionary systems.

It can take up a lot of memory because each letter in each word needs to be stored separately.

Efficient Searching:

• If you want to search for a word that starts with C, you don’t need to check every word. You
just follow the path from C and narrow it down.
• This is great for autocomplete. For example, if you type "ca", it can quickly suggest "cat" and
"car".

Shared Prefixes:

• Words with the same beginning letters (like "cat" and "car") share the same path until they
diverge. This saves space and makes the structure more efficient.

Fast Insertion:

• When you want to add a new word, you only need to add the parts that are different. So,
adding "cab" would simply mean adding a new path after A in the C branch.

Pros of a Trie:

• Quick Prefix Searches: Great for finding all words starting with a certain prefix.
• Efficient for Auto-Complete: Can suggest words based on what you've typed so far.
• Memory Efficient for Similar Words: Words with shared prefixes save space.

Cons of a Trie:
 • More Memory for Short Words: For very short words or unrelated words, it can end up using
more memory than a basic list of words.
• Overhead: It takes more time to build and manage a Trie compared to a basic array or list.

N-ary Tree: An N-ary tree is like a family tree where each person can have more than two children.
In simpler terms, it's a tree structure where each node (point in the tree) can have any number of
branches or children, not just two like in a binary tree.

Think of a family tree where each parent can have many children. Each parent is a node, and their
children branch out from them. There’s no limit on how many children a parent can have, so this
family tree can branch out as much as needed.

Imagine you're organizing files in a computer folder:

1. The main folder is the root node.

2. Inside that folder, you have multiple subfolders (each subfolder is a child of the root node).
3. Each subfolder can have more subfolders or files inside them.

Where N-Ary Trees Are Used:

• File systems: Where directories can have multiple subdirectories.

• Hierarchies: In organizations or companies where managers can have many subordinates.
• Game development: Where each node can represent a point in the game and have multiple paths or
choices.

Imagine a classroom where the teacher (the root) asks 4 students (the branches) to form groups of
their own. Each of those 4 students can then form more subgroups under them. There is no limit to
how many students can be part of each subgroup, making it an N-ary tree, where each student can
have multiple group members branching out under them.

Benefits:
 • Flexible structure: Unlike binary trees, where each node can only have two children, N-ary trees allow
you to expand as needed.
• Useful for real-world scenarios: They work well for organizing data in systems that need more
branches, like file systems or company hierarchies.

Drawbacks:

• More complex: Managing an N-ary tree can be harder than a binary tree because there are more
possible paths to navigate or balance.

B-Tree:

A tree used in databases and file systems. It’s a type of self-balancing tree where each node can have
multiple children. It's very efficient for handling large amounts of data.

When you search for a file on your computer, the system uses a B-tree to quickly find where that file
is stored.

How a B-Tree Works:

1. Multiple Branches: Unlike a binary tree (which only has two branches per node), a B-Tree can
have many branches per node. Think of each node like a library shelf that contains a
collection of books (or data points).
2. Balanced Structure: In a B-Tree, all the leaf nodes (the lowest level) are at the same height.
This keeps everything balanced so that you don’t have one long branch that’s hard to search
through. It’s like making sure all your library shelves are equally filled, so you don’t have to
look too far for anything.
3. Nodes Store Multiple Items: Each node (or shelf) can store multiple pieces of data. So instead
of just holding one book (like a regular tree), a B-Tree node can hold multiple books. This
helps organize things better and reduces the number of steps needed to find something.
4. Efficient Searching: The B-Tree divides the data into sections and uses a system to guide you
directly to the right section, much like how a library index points you to the exact shelf and
section where a book is located.

Graph
A graph is a way to represent a collection of items and the connections between them. You can think
of it like a map of cities where the cities are points (called nodes or vertices) and the roads
connecting them are the lines (called edges).

Basic Components of Graphs

1. Vertices (Nodes): These are the points or locations in the graph. For example, in a city map,
each city can be a vertex.
 2. Edges: These are the lines that connect the vertices. In our city map, the roads connecting the
cities are edges.

Types of Graphs

1. Undirected Graph: In this type of graph, the edges have no direction. If there’s a connection
between two vertices, you can travel both ways. For example, if City A is connected to City B,
you can travel from A to B and from B to A.
2. Directed Graph (Digraph): In a directed graph, the edges have a direction. This means that
you can only travel one way. For example, if there’s an edge from City A to City B, you can
travel from A to B, but not from B to A unless there’s a separate edge going back.
3. Weighted Graph: In a weighted graph, each edge has a value or weight associated with it. This
is often used to represent things like distances or costs. For example, if you have a map where
the roads between cities have distances marked, that’s a weighted graph.
4. Unweighted Graph: In an unweighted graph, all edges are treated equally, meaning there is
no cost or distance associated with them.

Common Operations on Graphs

1. Traversal: This means visiting all the vertices in a graph. There are two popular ways to
traverse:
o Depth-First Search (DFS): Go as deep as possible down one path before backing up.
o Breadth-First Search (BFS): Visit all the neighbors at the present depth level before moving on
to nodes at the next depth level.
2. Searching: Finding a specific vertex in the graph.
3. Shortest Path: Finding the shortest route from one vertex to another, which is crucial in maps
or networking.

What is an Algorithm?
An algorithm is like a recipe or a set of instructions that you follow to solve a problem or complete a
task. It’s a clear, step-by-step method for getting something done.

Imagine you want to bake a cake. You follow a recipe that tells you:

1. Gather ingredients.
2. Mix the flour, sugar, and eggs.
3. Bake it at 350°F for 30 minutes.

This recipe is an algorithm for making a cake. It tells you what to do, in what order, to get the desired
result (a cake).

Key Features of Algorithms

1. Step-by-Step: Each instruction must be followed in the correct order.

2. Clear: Each step should be easy to understand and perform.
3. Finite: An algorithm should have a clear end. It shouldn’t go on forever.
4. Solves a Problem: The goal of an algorithm is to solve a problem or complete a task.

Algorithms in Computers

In computers, an algorithm is a sequence of steps the computer follows to solve problems or perform
tasks. For example:

• Sorting Numbers: If you give the computer a list of numbers, it can follow an algorithm to sort
them from smallest to largest.
• Searching for Information: When you search for something on Google, the search engine uses
an algorithm to find the most relevant results for you.

What is Recursion?
Recursion is like a situation where something repeats itself in a smaller or simpler form. Imagine
you’re looking at two mirrors facing each other. If you stand between them, you'll see a reflection of
yourself inside another reflection, which goes on forever. This repeating process is similar to how
recursion works in programming.

In programming, recursion works in a similar way. A function calls itself repeatedly, solving a smaller
part of the problem each time, until it reaches a base case, which is a condition that tells the function
to stop.

Example: Factorial Calculation

The factorial of a number is the product of all positive integers less than or equal to that number. For
example:

• 5! (factorial of 5) = 5 × 4 × 3 × 2 × 1 = 120

A recursive way to calculate factorial is:

1. Base Case: If the number is 1, return 1 (because 1! = 1).

2. Recursive Step: Multiply the current number by the factorial of the previous number.

How This Works for Factorial of 5:

1. factorial(5) calls factorial(4).

2. factorial(4) calls factorial(3).
3. factorial(3) calls factorial(2).
4. factorial(2) calls factorial(1).
5. factorial(1) hits the base case and returns 1.

Now, the recursion unwinds:

• factorial(2) = 2 × 1 = 2
• factorial(3) = 3 × 2 = 6
• factorial(4) = 4 × 6 = 24
• factorial(5) = 5 × 24 = 120

Key Points About Recursion

1. Base Case: The condition where recursion stops. Without a base case, recursion would go on
forever, causing a problem called infinite recursion.
2. Recursive Case: The part where the function calls itself, reducing the problem size.
3. Breaking the Problem Down: Each recursive call should bring the problem closer to the base
case.

Advantages of Recursion
 • Simplicity: Recursion can make complex problems easier to understand and solve.
• Breaks Down Problems: It’s useful when the problem can be divided into similar
subproblems, like tree structures or searching algorithms.

Disadvantages of Recursion

• Memory Usage: Each recursive call uses memory, so deep recursions can cause stack
overflow errors.
• Slower: Recursion can be slower than other methods like iteration (loops) because it involves
multiple function calls.

What is Sorting?
Sorting means arranging things in a specific order, like alphabetically, by size, or by age. Imagine you
have a list of numbers, and you want to arrange them from the smallest to the largest. Sorting
algorithms are methods used to organize data like this.

There are many types of sorting algorithms, each with different ways of arranging data. Some are
faster, some use less memory, and some are simple to understand.

Types of sorting algorithms

1. Bubble Sort
Bubble Sort works by repeatedly "bubbling up" the largest unsorted number to the end. Think of it
like comparing pairs of numbers and swapping them if they are in the wrong order. You keep doing
this until the whole list is sorted.

Imagine you're arranging a row of kids from shortest to tallest. You look at two kids at a time, and if
the shorter kid is standing behind the taller one, you swap them. You keep going over the line again
and again until everything is in order.
Pros:

• Simple to understand and implement.

• Works well with small lists.

Cons:

• Very slow for large lists (inefficient)

Selection Sort
Selection Sort works by repeatedly selecting the smallest number from the unsorted part of the list
and swapping it with the first unsorted number.

Imagine you’re sorting a pile of books from shortest to tallest. You don’t want to compare all the
books at once, so you decide to sort them step by step:

1. Look at the pile: Find the shortest book in the pile.

2. Pick the shortest book: Take that shortest book and place it at the front of the row.
3. Repeat for the rest: Now look at the remaining unsorted books, find the next shortest one,
and place it next to the first book.
4. Keep going: Continue this process until all the books are lined up from shortest to tallest.
Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It
works similarly to how you sort playing cards in your hands: you take one card (element) at a time
and insert it into its correct position in the sorted portion of the deck (array).

Key Steps:

1. Start from the second element: Compare it to the elements before it (one by one) and insert
it in its correct position.
2. Shift elements if needed: If the current element is smaller than the ones before it, shift the
larger elements to the right to make space for it.
3. Repeat: Continue this process for each subsequent element until the entire array is sorted.

Another example
Imagine you are organizing a group of books by their size.

• You take one book at a time and place it in the correct position among the books you’ve
already organized.
• You don’t start over from scratch; you just insert each new book into its correct spot among
the already sorted ones.

This is how Insertion Sort works:

1. Start with the first book: The first book is already sorted because it’s alone.
2. Pick the second book: Compare it to the first one. If it’s smaller, place it before. If it’s larger,
leave it as it is.
3. Pick the third book: Compare it to the first two books, find the correct place for it, and insert
it.
4. Repeat: Continue picking books one by one and inserting them into their correct positions.

Merge Sort
Merge Sort is an efficient, stable, and comparison-based sorting algorithm that follows the divide and
conquer approach. The main idea behind Merge Sort is to divide the array into smaller parts, sort
those parts, and then merge them back together in a sorted manner

Imagine you have a big pile of socks of different colors, and you want to sort them into pairs of the
same color. Instead of trying to sort the entire pile at once, you use a divide and conquer strategy,
like this:

Divide the pile in half:

• You split your pile of socks into two smaller piles.

Keep dividing:

• You split each of those smaller piles into even smaller ones, and you keep going until each pile
has just one sock.

Start merging:

• Now, you look at two socks at a time from different piles and compare them.
• If they are of the same color, you make a pair.
• If they are not, you place them in the correct order based on color and keep sorting.

Merge bigger piles:

 • After sorting and merging two socks, you move on to the next two piles and keep merging
them until you’ve gone through all your socks.

Final sorted pile:

• By the end, you’ll have all your socks sorted into pairs, and your pile will be perfectly ordered.

Merge Sort Process:

1. Divide: Split the array into two halves recursively until each sub-array contains only one
element.
2. Conquer: Sort and merge the sub-arrays back together by comparing elements.
3. Merge: During the merging process, combine the smaller sub-arrays in a way that ensures the
resulting array is sorted.
Advantages:

• Efficient for large datasets.

• Guaranteed O(n log n) time complexity in all cases.
• Stable sorting: Does not change the relative order of equal elements.

Disadvantages:

• Not in-place: Requires additional memory to store temporary arrays during the merging
process.
• Slower for small datasets compared to simpler algorithms like Insertion Sort.

Quick Sort
Quick Sort is another popular sorting algorithm that uses the divide and conquer approach. It is
faster than many other algorithms, such as Bubble Sort or Selection Sort, especially when handling
large datasets.

Imagine you have a group of students of varying heights, and you want to line them up from shortest
to tallest. Instead of comparing everyone to everyone else, you can use this clever approach:

1. Pick a "pivot": Choose one student at random to be the "pivot" — the person you compare
everyone else to.
2. Separate the group:
o Make two groups:
▪ Group 1: Students shorter than the pivot.
▪ Group 2: Students taller than the pivot.
o The pivot now stands in the middle.
 3. Repeat the process: Now, treat each smaller group (Group 1 and Group 2) just like the original
group. Pick a pivot from each group, and divide those groups into even smaller groups.
4. Keep sorting: You keep dividing and comparing, always putting students shorter than the
pivot on one side and students taller on the other.
5. Line everyone up: Eventually, each group will be sorted, and when you combine all the small
groups, everyone will be standing in the correct order.

Quick Sort Process:

1. Pick a Pivot: Choose an element from the array as the pivot. This can be the first element, the
last element, or any element in between.
2. Partition: Rearrange the array so that:
o All elements smaller than the pivot come before it.
o All elements greater than the pivot come after it.
3. Recursion: Recursively apply the same process to the sub-arrays (those smaller and larger
than the pivot).
4. Combine: As each part is sorted individually, combining them results in a fully sorted array.

Advantages of Quick Sort:

• Fast for large datasets: On average, it performs faster than Merge Sort or Insertion Sort.
• In-place: It doesn’t require much extra space, as it sorts the array in-place.

Disadvantages of Quick Sort:

 • Worst case performance: If the pivot selection is poor (like choosing the smallest or largest
element repeatedly), the performance degrades to O(n²).
• Unstable: Unlike Merge Sort, Quick Sort may not preserve the relative order of equal
elements.

Searching Algorithms
Searching algorithms are techniques used to find a particular item or group of items from a collection
of data. The goal is to locate the desired item quickly and efficiently.

Searching algorithms can be broadly divided into two categories:

1. Linear Search: The most basic form of searching.

2. Binary Search: A more efficient way to search through sorted data

Linear Search (Sequential Search)

In Linear Search, you simply go through each element one by one and check if it is the item you're
looking for.

Imagine you're searching for a specific book on a messy shelf where books are arranged randomly.
You would look at each book from left to right, one by one, until you find the book you're searching
for.

How It Works:

• Start from the first element and compare it to the target.

• If the target is found, stop.
• If not, move to the next element and repeat.
• Keep going until you either find the target or reach the end of the list.

Time Complexity:

• Best Case: O(1) – The item is found at the first position.

• Worst Case: O(n) – The item is either not present or is at the last position
Pros:

• Simple to implement.
• Works on both sorted and unsorted data.

Cons:

• Inefficient for large datasets because it requires checking each item one by one.

Binary Search
Binary Search is a faster searching algorithm, but it only works on sorted data. It repeatedly divides
the search interval in half to quickly zero in on the target item.

Imagine looking for a word in a dictionary. You don't start from the first page. Instead, you open the
dictionary somewhere in the middle. If the word you're looking for comes alphabetically before the
middle word, you focus on the earlier part of the dictionary. Otherwise, you check the later part. This
process continues until you find the word.

How It Works:

• Start with two pointers: one at the beginning and one at the end of the array.
• Find the middle element.
• If the middle element is the target, you're done.
• If the target is smaller than the middle element, repeat the search on the left half.
• If the target is larger than the middle element, repeat the search on the right half.
• Continue this process until the target is found or the search interval becomes empty.

Time Complexity:

• Best Case: O(1) – The target is found in the middle.

• Worst Case: O(log n) – The search space is halved at every step, leading to logarithmic time
complexity.
Pros:

• Much faster than Linear Search for large datasets.

• Ideal for searching through sorted data.

Cons:

• Requires sorted data, which adds overhead if your data is unsorted.

Dijkstra's Algorithm
Dijkstra's Algorithm is a popular method used to find the shortest path between two points in a
graph. It ensures that you get the least expensive or quickest path from one point to another,
whether you're traveling between cities, navigating through a computer network, or analyzing road
maps.

Imagine you are planning a road trip, and you want to drive from City A to City B. There are multiple
routes and roads that connect several cities in between. You want to find the shortest or quickest
route to reach your destination.

• Some roads between the cities may be longer or shorter.

• Some routes may have traffic and cause delays.
• Some roads may be faster, but take you through more cities.

You could either guess or follow your instincts, but Dijkstra's Algorithm helps you do it methodically
and accurately. It calculates the best route step by step, ensuring you travel the least distance or time
between two points.

Bellman-Ford Algorithm
Bellman-Ford Algorithm is a method used to find the shortest path from one starting point (node) to
all other points in a network (graph). It's like Dijkstra's algorithm but with one major difference—it
can handle negative weights. In simpler terms, if there's a road or a connection that rewards you or
costs less as you travel, Bellman-Ford can still calculate the best path.

Imagine you’re planning a road trip again, but now you can encounter discounts or penalties on
certain roads. Some roads may even give you back money (negative cost) or take longer but are
cheaper. Your task is still to find the least expensive route from City A to other cities.

• Some roads might have a positive distance (like normal travel distance or time).
 • Some roads might have a negative distance (imagine getting a cash bonus for taking a certain
road).
• Bellman-Ford will ensure you avoid routes that may reduce your distance but lead you into
infinite loops (to prevent constantly cycling through roads for extra bonuses).

Backtracking
Definition: Backtracking is a problem-solving algorithm that incrementally builds candidates for
solutions and abandons a candidate as soon as it determines that this candidate cannot be extended
to a valid solution. Essentially, it explores all potential solutions to find the correct one by making
choices and then retracing (or "backtracking") when a choice leads to a dead end.

Backtracking is like solving a puzzle step by step, where you make a choice, and if that choice doesn’t
lead to a solution, you take a step back (or "backtrack") and try a different option. It’s a way to find
answers to problems by exploring all possible paths and eliminating those that don't work.

How Does It Work?

-> Making Choices:

• Imagine you’re trying to find your way through a maze. You start at the entrance and choose a
direction to go.

-> Exploring:

• As you go along, you check if you’re still on the right path. If you hit a dead end, you stop and
look for another way to go back.

-> Backtracking:

• If a path doesn’t lead to the exit (solution), you return to where you made a decision
(backtrack) and try another direction.

-> Finding the Solution:

• You keep making choices and backtracking until you either find the exit or realize there’s no
way out.

Caching vs. Memoization

Both caching and memoization are techniques used to store and retrieve data efficiently, but they
serve slightly different purposes and are used in different contexts. Here’s a simple explanation of
each
Caching

Definition: Caching is like a temporary storage space where you keep frequently accessed data so
that you can retrieve it quickly without having to go back to the original source each time.

Imagine you often visit a coffee shop that has a long line. To make things faster, the shop keeps your
favorite order on hand. So, when you arrive, they quickly grab it for you instead of making it from
scratch each time. This way, you save time, and the shop can serve more customers

Key Points:

• Purpose: To speed up data retrieval.

• Scope: Generally applied to larger datasets, such as web pages, images, or results from
database queries.
• Storage: Usually managed at a higher level (like in a web server or database).
• Expiration: Cached data may have a set time to live (TTL), meaning it might get removed or
updated after a while.

Memoization
Memoization is a specific type of caching used in programming, particularly in recursive functions. It
involves storing the results of expensive function calls and returning the cached result when the same
inputs occur again.

Think of a student studying for an exam. When they solve a math problem, they write down the
answer in their notebook. If they encounter the same problem again, they check their notebook
instead of solving it from scratch. This saves them time and effort.

Key Points:

• Purpose: To optimize performance of recursive algorithms by avoiding repeated calculations.

• Scope: Typically used in functions or algorithms that have overlapping subproblems, like
Fibonacci sequence calculations or certain dynamic programming problems.
• Storage: Usually involves using data structures like arrays or dictionaries to remember the
results of function calls.
• Function-Specific: Works specifically for functions and relies on function inputs as the keys to
retrieve results.

=================================================