DSA Topic-wise Concepts, Interview Questions & Coding Problems

1. Arrays
Concepts to understand:
- Memory layout and indexing
- Time complexity of operations (access O(1), insertion/deletion O(n))
- Difference between static array and dynamic array (like ArrayList)
- Cache locality
Conceptual interview questions:
- How is an array stored in memory?
- What happens if you try to access an out-of-bound index?
- Why is access O(1) but insertion O(n) in arrays?
- How do dynamic arrays resize internally?
- Difference between array and linked list?
Coding questions to solve after concepts:
- Reverse an array
- Find max/min element
- Move all zeros to the end
- Find kth largest element
- Merge two sorted arrays
- Binary search on sorted array
- Find pairs with given sum

2. Strings
Concepts to understand:
- String immutability in Java
- String Pool
- StringBuilder vs StringBuffer
- Basic string manipulation
- Pattern matching basics (Naive, KMP)
Conceptual interview questions:
- Why are strings immutable?
- How does Java store strings internally?
- How does string concatenation work?
- Explain string matching algorithms you know.
Coding questions to solve after concepts:
- Check palindrome
- Reverse string
- Anagram check
- First non-repeating character
- Longest common prefix
- Pattern search (KMP/Naive)
- Remove duplicates from a string

3. Linked Lists
Concepts to understand:
- Node structure and pointers
- Difference between singly and doubly linked lists
- Operations: insertion, deletion, traversal
- Cycle detection and Floyd's algorithm (slow/fast pointer)
Conceptual interview questions:
- How is a linked list stored?
- Why do linked lists have O(n) access time?
- How do you detect a cycle?
- Difference between array and linked list insertion?
Coding questions to solve after concepts:
- Reverse a linked list
- Detect and find start of cycle
- Merge two sorted linked lists
- Remove nth node from end
- Find middle element
- Check palindrome linked list

4. Stacks
Concepts to understand:
- LIFO principle
- Array vs linked list implementation
- Stack operations complexity
- Call stack in recursion
- Design of min stack (O(1) getMin)
Conceptual interview questions:
- What is stack and how is it used in recursion?
- How would you implement a stack?
- Explain min stack design.
Coding questions to solve after concepts:
- Balanced parentheses
- Evaluate postfix expression
- Next greater element
- Min stack implementation
- Infix to postfix conversion

5. Queues
Concepts to understand:
- FIFO principle
- Circular queue, deque
- Priority queue basics and heap properties
- Use cases like BFS
Conceptual interview questions:
- How is a queue implemented?
- Difference between queue and deque?
- What is a priority queue and how does it work?
Coding questions to solve after concepts:
- Implement simple and circular queue
- Sliding window maximum
- BFS traversal of a graph/tree
- Implement priority queue using heap

6. Trees
Concepts to understand:
- Tree terminologies (root, leaf, height, depth)
- Binary tree vs BST properties
- Tree traversals (inorder, preorder, postorder)
- Balanced vs unbalanced trees
- Binary tree storage and recursion
Conceptual interview questions:
- What is a binary search tree?
- Explain inorder traversal and why it prints BST in sorted order
- What is tree height vs depth?
- How do you check if a tree is balanced?
Coding questions to solve after concepts:
- Inorder, preorder, postorder traversal
- Check if BST
- Find LCA of two nodes
- Convert sorted array to BST
- Find diameter of a tree
- Serialize/deserialize binary tree

7. Graphs
Concepts to understand:
- Graph representation: adjacency list vs matrix
- BFS and DFS traversal
- Cycle detection in directed/undirected graphs
- Topological sort
- Shortest path in unweighted graphs (BFS)
Conceptual interview questions:
- How are graphs represented internally?
- Difference between BFS and DFS?
- How do you detect cycles in graphs?
- When to use adjacency list vs matrix?
Coding questions to solve after concepts:
- Implement BFS and DFS
- Detect cycle in graph
- Find connected components
- Topological sort of a DAG
- Number of islands problem (graph in grid)

8. Hashing
Concepts to understand:
- Hash function and hash table structure
- Collision handling: chaining vs open addressing
- Load factor and resizing
- Use cases for hashing
Conceptual interview questions:
- How does a hash table work internally?
- What causes collisions and how do you handle them?
- What is load factor and why resize hash table?
Coding questions to solve after concepts:
- Implement hash map with chaining
- Find first non-repeating char in string
- Count element frequencies
- Check if two arrays share elements
- Two sum problem with hashing

9. Recursion & Backtracking

Concepts to understand:
- Base case and recursive calls
- Call stack and stack overflow
- Backtracking as controlled recursion with pruning
- Use cases like permutations, N-Queens
Conceptual interview questions:
- How does recursion work internally?
- What is the difference between recursion and backtracking?
- How do you avoid stack overflow?
Coding questions to solve after concepts:
- Factorial using recursion
- Generate permutations of a string
- N-Queens problem
- Subsets/power set generation
- Solve Sudoku using backtracking

10. Sorting & Searching

Concepts to understand:
- Time and space complexity of sorts
- Stable vs unstable sorting
- Divide and conquer paradigm
- Binary search prerequisites and implementation
Conceptual interview questions:
- Explain merge sort and quicksort internals
- What makes a sort stable?
- When to use binary search?
Coding questions to solve after concepts:
- Implement bubble, insertion, selection sort
- Implement merge sort and quicksort
- Binary search (iterative and recursive)
- Search in rotated sorted array
- Find peak element in array

11. Dynamic Programming

Concepts to understand:
- Overlapping subproblems and optimal substructure
- Memoization vs tabulation
- State, choice, transition formulation
Conceptual interview questions:
- How do you recognize a DP problem?
- Difference between DP and recursion?
- Explain top-down and bottom-up approaches
Coding questions to solve after concepts:
- Fibonacci with DP
- 0/1 knapsack problem
- Longest increasing subsequence
- Coin change (number of ways)
- Edit distance problem

12. Greedy Algorithms

Concepts to understand:
- Greedy choice property
- When greedy algorithms produce optimal solution
- Difference from DP approach
Conceptual interview questions:
- How do you prove greedy correctness?
- Compare greedy and DP with examples
Coding questions to solve after concepts:
- Activity selection problem
- Fractional knapsack
- Job scheduling with deadlines
- Huffman coding algorithm