datastructures_algorithms.md

Array and Strings

1. Find the duplicate number in an array.
2. Rotate an array.
3. Implement an algorithm to reverse a string.
4. Check if two strings are anagrams.
5. Implement a function to find the first non-repeating character in a string.
6. Given an array of integers, find the subarray with the maximum sum (Kadane's algorithm).
7. Implement an algorithm to perform string compression (e.g., "aaabbb" becomes "a3b3").
8. Determine if a string has all unique characters.
9. Implement an algorithm to check if a string is a rotation of another string.
10. Move all zeroes to the end of an array without changing the order of non-zero elements.

Linked Lists

1. Reverse a linked list.
2. Detect a cycle in a linked list.
3. Find the middle element of a linked list.
4. Merge two sorted linked lists.
5. Remove duplicates from a sorted/unsorted linked list.
6. Merge K sorted linked lists.
7. Implement a function to add two numbers represented by linked lists.
8. Check if a linked list is a palindrome.
9. Find the intersection point in Y-shaped linked lists.
10. Clone a linked list with next and random pointer.

Trees and Graphs

1. Implement depth-first search (DFS) and breadth-first search (BFS) on a graph.
2. Find the lowest common ancestor (LCA) in a binary tree.
3. Determine if a binary tree is a binary search tree (BST).
4. Implement binary tree traversals (in-order, pre-order, post-order).
5. Find the shortest path in an unweighted graph (BFS).
6. Check if a binary tree is balanced.
7. Serialize and deserialize a binary tree.
8. Determine if there's a path between two nodes in a directed graph.
9. Topological sort of a directed acyclic graph (DAG).
10. Find the shortest path in a weighted graph (Dijkstra's or Bellman-Ford).

Sorting and Searching

1. Implement various sorting algorithms to sort given arrays.
2. Search for an element in a sorted and rotated array.
3. Find the kth smallest/largest element in an array.
4. Implement binary search.
5. Count the number of occurrences of an element in a sorted array.
6. Find the peak element in an array.
7. Implement a square root function (binary search).
8. Search in a 2D matrix.
9. Implement an efficient algorithm for matrix multiplication.
10. Count inversions in an array.

Dynamic Programming

1. Calculate the nth Fibonacci number using dynamic programming.
2. Find the longest common subsequence of two strings.
3. Calculate the minimum edit distance between two strings.
4. Solve the Knapsack problem (0/1 or fractional).
5. Find the longest increasing subsequence.
6. Solve the coin change problem.
7. Find the longest palindrome subsequence.
8. Find the maximum subarray sum with no adjacent elements.
9. Solve the word break problem.
10. Determine the optimal strategy for a game (like the coin game).

Miscellaneous

1. Implement a stack using arrays/linked lists and implement a queue using stacks.
2. Design a cache with O(1) lookup time.
3. Implement a trie (prefix tree).
4. Check if a string has valid parentheses.
5. Design and implement an LRU (Least Recently Used) cache.
6. Design a data structure that supports insert, delete.