SUMMER VACATION DSA PROBLEM SHEET

Arrays (5 days)

Array Basics (2 days)

  1. Theory (0.5 days)

    1. C++ Arrays (With Examples)
    2. Java Array (With Examples)
    3. Python Array (With Examples)

  2. Problems (1.5 days)

    1. Wave Array | Practice | GeeksforGeeks
    2. Sort an array of 0s, 1s and 2s | Practice | GeeksforGeeks
    3. Subarray with given sum | Practice | GeeksforGeeks
    4. Kadane's Algorithm | Practice | GeeksforGeeks
    5. Missing number in array | Practice | GeeksforGeeks

Binary Search (2 days)

  1. Theory (0.5 days)

    1. https://www.geeksforgeeks.org/binary-search/

  2. Problems (1.5 days)

    1. Search Insert Position - LeetCode
    2. Sqrt(x) - LeetCode
    3. Find Smallest Letter Greater Than Target - LeetCode
    4. Kth Smallest Element in a Sorted Matrix - LeetCode

Two Pointers (1 day)

  1. Theory (about 1 hr)

    1. https://www.geeksforgeeks.org/two-pointers-technique/

  2. Problems (1 day)

    1. 3 Sum | Interviewbit
    2. Merge Two Sorted Lists II | Interviewbit
    3. Remove Duplicates from Sorted Array | Interviewbit

Strings (2 days)

  1. String Basics (2 days)
    1. Integer To Roman | Interviewbit
    2. Reverse the String | Interviewbit
    3. Implement StrStr | Interviewbit
    4. Vowel and Consonant Substrings! | Interviewbit
    5. Longest Common Prefix | Interviewbit
    6. Longest Palindromic Substring | Interviewbit

Linked Lists (4 days)

  1. Theory (1 day)

    1. https://www.programiz.com/dsa/linked-list

  2. Problems (3 days)

    1. Reverse a linked list - GeeksforGeeks
    2. ​​Rotate a Linked List - GeeksforGeeks
    3. Function to check if a singly linked list is palindrome - GeeksforGeeks
    4. Nth node from end of linked list | Practice | GeeksforGeeks
    5. Detect Loop in linked list | Practice | GeeksforGeeks
    6. Find the middle of a given linked list - GeeksforGeeks
    7. Delete N nodes after M nodes of a linked list - GeeksforGeeks
    8. Reverse a Linked List in groups of given size. | Practice | GeeksforGeeks
    9. Reverse alternate K nodes in a Singly Linked List - GeeksforGeeks

Stacks and Queues (5 days)

  1. Theory (2 days)

    1. https://www.programiz.com/dsa/stack
    2. https://www.geeksforgeeks.org/stack-in-cpp-stl/
    3. https://www.geeksforgeeks.org/stack-class-in-java/
    4. https://www.geeksforgeeks.org/stack-in-python/
    5. https://www.programiz.com/dsa/queue
    6. https://www.geeksforgeeks.org/queue-cpp-stl/
    7. https://www.geeksforgeeks.org/queue-interface-java/
    8. https://www.geeksforgeeks.org/queue-in-python/

  2. Problems (3 days)

    1. Balanced Parantheses! | Interviewbit
    2. Redundant Braces | Interviewbit
    3. Nearest Smaller Element | Interviewbit
    4. Largest Rectangle in Histogram | Interviewbit
    5. Min Stack | Interviewbit
    6. First Unique Character in a String - LeetCode
    7. Implement Stack using Queues - LeetCode
    8. Time Needed to Buy Tickets - LeetCode
    9. Implement Queue using Stacks - LeetCode

Hashing (3 days)

  1. Theory (1 day)

    1. https://www.programiz.com/dsa/hash-table
    2. https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/
    3. https://www.geeksforgeeks.org/java-util-hashmap-in-java-with-examples/
    4. https://www.geeksforgeeks.org/hash-map-in-python/

  2. Problems (2 days)

    1. Largest subarray of 0's and 1's | Practice | GeeksforGeeks
    2. Find All Four Sum Numbers | Practice | GeeksforGeeks
    3. Array Subset of another array | Practice | GeeksforGeeks
    4. Sorting Elements of an Array by Frequency | Practice | GeeksforGeeks
    5. Union of Two Linked Lists | Practice | GeeksforGeeks
    6. Top K Frequent Elements in Array - | | Practice | GeeksforGeeks

Tree-based Data Structures (7 days)

Binary Tree & BST (5 days)

  1. Theory (1 day)

    1. https://www.geeksforgeeks.org/introduction-to-tree-data-structure/
    2. https://www.geeksforgeeks.org/binary-tree-set-1-introduction/?ref=lbp
    3. https://www.geeksforgeeks.org/binary-tree-set-2-properties/?ref=lbp
    4. https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/?ref=lbp

  2. Problems (4 days)

    1. Inorder Traversal | Interviewbit
    2. Preorder Traversal | Interviewbit
    3. Postorder Traversal | Interviewbit
    4. Max Depth of Binary Tree | Interviewbit
    5. Right view of Binary tree | Interviewbit
    6. Sorted Array To Balanced BST | Interviewbit
    7. Root to Leaf Paths With Sum | Interviewbit
    8. ZigZag Level Order Traversal BT | Interviewbit
    9. Symmetric Binary Tree | Interviewbit
    10. Balanced Binary Tree | Interviewbit
    11. Valid BST from Preorder | Interviewbit
    12. Kth Smallest Element In Tree | Interviewbit

Heaps (1 day)

  1. Theory

    1. https://www.geeksforgeeks.org/binary-heap/

  2. Problems

    1. K Largest Elements | Interviewbit
    2. Merge K Sorted Lists | Interviewbit

Trie (1 day)

  1. Theory

    1. https://www.geeksforgeeks.org/advantages-trie-data-structure/?ref=lbp
    2. https://www.geeksforgeeks.org/trie-insert-and-search/?ref=lbp
    3. https://www.geeksforgeeks.org/trie-delete/?ref=lbp

  2. Problems

    1. Hotel Reviews | Interviewbit
    2. Shortest Unique Prefix | Interviewbit

Dynamic Programming (8 Days)

  1. Theory (3 days)

    1. https://www.youtube.com/watch?v=OQ5jsbhAv_M&list=PLcDimPvbmfT8qAxD6JH_kmXiQwTNcoK78
    2. https://www.youtube.com/watch?v=ENyox7kNKeY&list=PLcDimPvbmfT8qAxD6JH_kmXiQwTNcoK78&index=2
    3. https://www.youtube.com/watch?v=ocZMDMZwhCY&list=PLcDimPvbmfT8qAxD6JH_kmXiQwTNcoK78&index=3
    4. https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
    5. https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
    6. https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
    7. https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
    8. https://www.geeksforgeeks.org/longest-common-substring-dp-29/

  2. Problems (5 Days)

    1. Nth Fibonacci Number | Practice | GeeksforGeeks
    2. 0 - 1 Knapsack Problem | Practice | GeeksforGeeks
    3. Coin Change | Practice | GeeksforGeeks
    4. nCr | Practice | GeeksforGeeks
    5. Longest Increasing Subsequence | Practice | GeeksforGeeks
    6. Longest Common Subsequence | Practice | GeeksforGeeks
    7. Longest Common Substring | Practice | GeeksforGeeks
    8. Edit Distance | Interviewbit
    9. Ways to Decode | Interviewbit
    10. Longest valid Parentheses | Interviewbit
    11. Dungeon Princess | Interviewbit
    12. Max Product Subarray | Interviewbit
    13. Max Sum Without Adjacent Elements | Interviewbit
    14. Best Time to Buy and Sell Stocks I | Interviewbit
    15. Best Time to Buy and Sell Stocks II | Interviewbit

Graphs (8 Days)

  1. Theory (3 days)

    1. https://www.geeksforgeeks.org/graph-and-its-representations/
    2. https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
    3. https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
    4. https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
    5. https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
    6. https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
    7. https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
    8. https://www.geeksforgeeks.org/union-find-algorithm-union-rank-find-optimized-path-compression/

  2. Practice (5 days)

    1. BFS of graph | Practice | GeeksforGeeks
    2. DFS of Graph | Practice | GeeksforGeeks
    3. Find the number of islands | Practice | GeeksforGeeks
    4. Implementing Dijkstra Algorithm | Practice | GeeksforGeeks
    5. Detect cycle in a directed graph | Practice | GeeksforGeeks
    6. Detect cycle in an undirected graph | Practice | GeeksforGeeks
    7. Topological sort | Practice | GeeksforGeeks
    8. Minimum Spanning Tree | Practice | GeeksforGeeks
    9. Unit Area of largest region of 1's | Practice | GeeksforGeeks
    10. Floyd Warshall | Practice | GeeksforGeeks
    11. Shortest path from 1 to n | Practice | GeeksforGeeks
    12. Covid Spread | Practice | GeeksforGeeks
    13. Distance from the Source (Bellman-Ford Algorithm) | Practice | GeeksforGeeks
    14. Biconnected Graph | Practice | GeeksforGeeks
    15. Union-Find | Practice | GeeksForGeeks