Data Structures: The Building Blocks of Coding Mastery(day-4)

Specific algorithm for particular Data Structure!!(day-4)

Manralai

For all new updates: Subscribe

A new person must learn in this order only

Algorithms are divided into two parts

1. Specific to Data Structure
2. General Techniques

For all new updates: Subscribe

Specific to Data Structure

1. Arrays

Sorting:

• Quick Sort: Efficient average-case time complexity (O(n log n))
• Merge Sort: Stable sort, useful when order matters (O(n log n))

Searching:

• Binary Search: Fast search in sorted arrays (O(log n))

Two Pointers:

• In-place manipulation, often for sorted arrays (e.g., removing duplicates)

Sliding Window:

• Sub-array problems, finding maximum/minimum within a window

For all new updates: Subscribe

2. Linked Lists

Traversal:

• Iterate through the list, understand the node structure

Insertion/Deletion:

• At beginning, end, or at a specific position

Reversal:

• In-place reversal, recursive and iterative approaches

Cycle Detection:

• Floyd’s Tortoise and Hare algorithm

For all new updates: Subscribe

3. Stacks

Implementation not needed.

Understand:

• Push/Pop/Peek Operations

4. Queues

Implementation not needed.

Understand:

• Enqueue/Dequeue Operations

5. Trees (Binary Trees, Binary Search Trees, etc.)

Traversal:

• In-order, Pre-order, Post-order (recursive and iterative)

Searching:

• Find a node with a given value (especially in BSTs)

6. Hash Tables (Hash Maps/Sets)

Implementation not needed.

Understand:

• Understand how hash functions work
• Insertion/Deletion/Lookup
• Collision Handling

7. Heaps (Priority Queues)

Implementation not needed.

Understand:

• Insertion/Deletion (extract-min/max)
• Building a Heap

Top K Elements:

• Using a heap to find k largest/smallest elements

For all new updates: Subscribe

8. Graphs

Traversal:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Shortest Path:

• Dijkstra’s Algorithm

Cycle Detection:

• DFS

9. Tries

Implement Trie from scratch

Insertion/Searching:

• For words/prefixes

Auto-completion:

• Using a trie for word suggestions

10. Union-Find (Disjoint Set)

• Implement Union-Find from scratch
• Find/Union Operations
• Cycle Detection in undirected graphs

For all new updates: Subscribe

General Techniques

These techniques are not specific to any data structures

1. Recursion
2. Dynamic Programming
3. Backtracking
4. Greedy Algorithms

1. Recursion

• Defining a problem in terms of itself, often leading to elegant and concise solutions.
• Solve: Factorial calculation, tree traversals, depth-first search.

2. Dynamic Programming

• Breaking down a problem into overlapping sub-problems and storing solutions to avoid re-computation.
• Solve: Fibonacci sequence, Knapsack problem, Longest Common Sub-sequence.

3. Greedy Algorithms

• Making locally optimal choices at each step with the hope of finding a global optimum.
• Implement: Kruskal’s algorithm for minimum spanning trees.

4. Backtracking

• Incrementally building solutions, exploring all possible paths, and abandoning invalid ones.
• Solve: Sudoku solver, N-Queens problem, generating permutations.

Time Complexity

• O(1): Constant Time
• O(log n): Logarithmic Time
• O(n): Linear Time
• O(n log n): Linearithmic Time
• O(n²): Quadratic Time
• O(2^n): Exponential TimeO(n!): Factorial Time

Arrays:

• Read: O(1)
• Insertion: O(n)
• Deletion: O(n)
• Fast at reading but slow at insertion and deletion.

Linked Lists:

• Read: O(n)
• Insertion: O(1)
• Deletion: O(1)
• Slow at reading but efficient for insertion and deletion.

Stacks:

• Push: O(1)
• Pop: O(1)
• Peak: O(1)
• Follow the LIFO (Last In, First Out) principle
• Useful for fast retrieval of the topmost element but can be cumbersome for inserting or deleting elements in the middle or end.

Queues:

• Enqueue: O(1)
• Dequeue: O(1)
• Front: O(1)
• Follow the FIFO (First In, First Out) principle, first element in line is the first to come out.
• Think of them as playlists for organising items in order of arrival.

Trees:

• Read/Search: O(log n)
• Insertion: O(log n)
• Deletion: O(log n)
• Nodes connected by edges; root, parent-child connections.

Binary Trees:

• Efficient searching of ordered values
• Follow a binary search property where left child nodes are less than the parent and right child nodes are greater.
• Useful for tasks like number guessing games or dictionary implementations

Hash Maps:

• Read: O(1)
• Insertion: O(1)
• Deletion: O(1)
• Similar to arrays but with named indexes (keys)
• uUnordered but provide fast lookup.

Graphs:

• Traversal/Search: O(V + E) (V: number of vertices, E: number of edges)
• Insertion: O(1)
• Deletion: O(1)
• Versatile models for connections between nodes and edges
• Can be directed or undirected with no neighbouring limit.
• Can include cycles and weights on paths.
• Used for tasks like route optimisation.

Note: Focus on patterns not on number of Questions

1. Sliding Window Pattern
2. Subset Pattern
3. Modified Binary Search Pattern
4. Top K Elements Pattern
5. Binary Tree DFS Pattern
6. Topological Sort Pattern
7. Binary Tree BFS Pattern
8. Two Pointers Pattern

I will add more here if I will get 500 claps.

— — — — — — — — — —

If you like the article and would like to support me, make sure to:

• 👏 Clap for the story (500 claps)
• For all new updates: Subscribe
• 📰 View more content on my medium profile
• 🔔 Follow Me: LinkedIn | Youtube | GitHub | Website

— — — — — — — — — —

Day-1: Why Data Structure and Algorithm

Day-2: Nodes : Most basic building blocks of data structures

Day-3: Implementing Nodes : Most basic building blocks of data structures