Data Structures & Algorithms – Tech Interview Guide
This document compiles essential Data Structures and Algorithms (DSA) topics required to pass
technical interviews. Each topic includes explanations, examples, and worked solutions.
1. Big-O Notation
Explanation: Big-O notation describes how the runtime or space requirements of an algorithm
grow with input size.
Example: Finding an element in a sorted array using binary search.
Solution: Binary search divides the array in half each step, resulting in O(log n) time complexity.
2. Arrays & Strings
Explanation: Arrays store elements in contiguous memory locations. Strings are arrays of
characters.
Example: Find the maximum sum of a subarray of size k.
Solution: Use a sliding window technique to maintain the sum in O(n) time.
3. Hash Tables
Explanation: Hash tables store key-value pairs for fast lookup.
Example: Count frequency of characters in a string.
Solution: Traverse the string and update counts in a dictionary. Lookup is O(1) average.
4. Linked Lists
Explanation: Linked lists consist of nodes where each node points to the next.
Example: Reverse a singly linked list.
Solution: Iterate through the list and reverse pointers iteratively in O(n) time.
5. Stacks & Queues
Explanation: Stacks follow LIFO, queues follow FIFO.
Example: Check if parentheses are balanced.
Solution: Use a stack to push opening brackets and pop when closing brackets appear.
6. Trees
Explanation: Trees are hierarchical data structures with nodes and children.
Example: Find the maximum depth of a binary tree.
Solution: Use recursion or BFS. The depth is 1 + max(left, right).
7. Binary Search Trees
Explanation: BSTs maintain sorted order: left < root < right.
Example: Find the kth smallest element in a BST.
Solution: Perform inorder traversal and count nodes until k is reached.
8. Heaps
Explanation: Heaps are complete binary trees used for priority queues.
Example: Find the kth largest element in an array.
Solution: Maintain a min-heap of size k while iterating through elements.
9. Recursion & Backtracking
Explanation: Recursion solves problems by calling itself on smaller inputs.
Example: Generate all permutations of a list.
Solution: Use backtracking by choosing an element, exploring, then undoing the choice.
10. Searching Algorithms
Explanation: Searching algorithms locate elements in data structures.
Example: Search for an element in a rotated sorted array.
Solution: Apply modified binary search to determine sorted halves.
11. Sorting Algorithms
Explanation: Sorting arranges elements in a defined order.
Example: Sort an array of numbers.
Solution: Use merge sort for guaranteed O(n log n) time complexity.
12. Graphs
Explanation: Graphs consist of vertices connected by edges.
Example: Count number of islands in a grid.
Solution: Use DFS or BFS to mark visited land cells.
13. Dynamic Programming
Explanation: DP solves problems by storing results of overlapping subproblems.
Example: Climbing stairs problem.
Solution: Use dp[n] = dp[n-1] + dp[n-2] to compute ways.
14. Greedy Algorithms
Explanation: Greedy algorithms choose locally optimal solutions.
Example: Activity selection problem.
Solution: Sort activities by end time and select compatible ones.
15. Bit Manipulation
Explanation: Bit manipulation uses bitwise operations.
Example: Find the single number in an array where others appear twice.
Solution: Use XOR operation to cancel duplicate values.
End of Document – Practice these topics thoroughly to succeed in technical interviews.