DSA Exercises

Welcome to TheCodingCollege.com! In this post, we provide a comprehensive set of Data Structures and Algorithms (DSA) exercises to help you enhance your problem-solving skills. These exercises cover beginner to advanced levels and include hints and solutions for each category.

1. Array Exercises

Problem 1: Reverse an Array

  • Description: Write a function to reverse an array in place.
  • Example:
    Input: [1, 2, 3, 4, 5]
    Output: [5, 4, 3, 2, 1]

Problem 2: Find the Second Largest Element

  • Description: Find the second largest element in an array.
  • Example:
    Input: [12, 35, 1, 10, 34, 1]
    Output: 34

2. Linked List Exercises

Problem 1: Detect a Cycle in a Linked List

  • Description: Implement an algorithm to detect if a linked list has a cycle.
  • Hint: Use Floyd’s Cycle Detection Algorithm.

Problem 2: Reverse a Linked List

  • Description: Reverse a singly linked list.
  • Example:
    Input: 1 -> 2 -> 3 -> 4 -> 5
    Output: 5 -> 4 -> 3 -> 2 -> 1

3. Stack Exercises

Problem 1: Balanced Parentheses

  • Description: Check if a given string of parentheses is balanced.
  • Example:
    Input: "(())"
    Output: True

Problem 2: Next Greater Element

  • Description: For each element in an array, find the next greater element.
  • Example:
    Input: [4, 5, 2, 10]
    Output: [5, 10, 10, -1]

4. Queue Exercises

Problem 1: Implement a Queue Using Stacks

  • Description: Implement a queue using two stacks.

Problem 2: Sliding Window Maximum

  • Description: Find the maximum element in every sliding window of size k.
  • Example:
    Input: arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
    Output: [3, 3, 5, 5, 6, 7]

5. Sorting Exercises

Problem 1: Sort an Array of 0s, 1s, and 2s

  • Description: Sort the array without using any sorting algorithm.
  • Hint: Use the Dutch National Flag Algorithm.

Problem 2: Merge Two Sorted Arrays

  • Description: Merge two sorted arrays into a single sorted array.
  • Example:
    Input: arr1 = [1, 3, 5], arr2 = [2, 4, 6]
    Output: [1, 2, 3, 4, 5, 6]

6. Graph Exercises

Problem 1: Find Connected Components

  • Description: Count the number of connected components in an undirected graph.

Problem 2: Detect a Cycle in a Graph

  • Description: Check if a given graph contains a cycle.
  • Hint: Use DFS or Union-Find for detection.

7. Dynamic Programming Exercises

Problem 1: Longest Increasing Subsequence

  • Description: Find the length of the longest increasing subsequence in an array.
  • Example:
    Input: [10, 9, 2, 5, 3, 7, 101, 18]
    Output: 4

Problem 2: 0/1 Knapsack Problem

  • Description: Given weights and values of items, find the maximum value in a knapsack of capacity W.

8. String Exercises

Problem 1: Check for Anagrams

  • Description: Write a function to check if two strings are anagrams of each other.
  • Example:
    Input: "listen", "silent"
    Output: True

Problem 2: Longest Palindromic Substring

  • Description: Find the longest palindromic substring in a given string.
  • Example:
    Input: "babad"
    Output: "bab"

9. Tree Exercises

Problem 1: Find the Height of a Tree

  • Description: Calculate the height of a binary tree.

Problem 2: Lowest Common Ancestor

  • Description: Find the lowest common ancestor of two nodes in a binary tree.

10. Challenge Problems

Problem 1: Travelling Salesman Problem

  • Description: Find the minimum cost of visiting all cities exactly once and returning to the starting city.

Problem 2: N-Queens Problem

  • Description: Place N queens on an N x N chessboard such that no two queens attack each other.

Conclusion

Practice makes perfect! These DSA exercises are designed to help you grasp key concepts and sharpen your problem-solving skills.

Leave a Comment