Questions
8–11 questions in major PSU papers
Difficulty
Medium
Importance
Core — never skip
Overview
Data Structures and Algorithms form the backbone of computer science, testing your ability to optimize storage and process data efficiently. In Indian PSU exams, this topic is critical as it assesses your analytical thinking and logical foundation, appearing consistently across all major technical papers.
Asymptotic Analysis and Complexity
Understanding Time and Space complexity is essential for evaluating the performance of algorithms as input size grows. You must master Big-O, Omega, and Theta notations to compare algorithmic efficiency accurately.
- Big-O notation represents the upper bound (worst-case).
- Master Theorem: T(n) = aT(n/b) + f(n).
- Space complexity includes auxiliary space and input space.
- Constant time is O(1), Logarithmic is O(log n), Linear is O(n).
Linear Data Structures
Arrays, Linked Lists, Stacks, and Queues are fundamental building blocks for complex operations. PSUs frequently ask about their access times, memory overhead, and insertion/deletion constraints.
- Array access is O(1) via indexing.
- Stack follows LIFO (Last-In-First-Out) principle.
- Queue follows FIFO (First-In-First-Out) principle.
- Linked List insertion at head is O(1).
- Circular Queue avoids wasted space.
Trees and Graphs
Trees and Graphs represent non-linear relationships, and mastering their traversal techniques is vital. Expect numerical problems on tree heights, traversal orderings, and shortest path calculations.
- BST (Binary Search Tree) search time is O(h).
- AVL trees are self-balancing BSTs with height O(log n).
- Binary Heap: Parent index (i-1)/2, Left child 2i+1.
- BFS uses Queue; DFS uses Stack.
- Dijkstra's algorithm finds single-source shortest path.
Sorting and Searching
These algorithms are frequently tested for their best, average, and worst-case time complexities. Focus on the distinction between comparison-based and non-comparison-based sorts.
- QuickSort average case: O(n log n), worst case O(n^2).
- MergeSort is stable and O(n log n) in all cases.
- Bubble Sort is O(n^2) and stable.
- Binary Search requires a sorted array: O(log n).
- Heap Sort uses a Max-Heap or Min-Heap structure.
Formula Sheet
T(n) = aT(n/b) + f(n) (Master Theorem)
Nodes in Binary Tree of height h: 2^(h+1) - 1
Parent of node i: floor((i-1)/2)
Left child of node i: 2i + 1
Exam Tip
Focus on memorizing the complexity table for all common algorithms, as 40% of questions are direct comparisons of these values.
Common Mistakes
- Confusing the best-case and worst-case time complexities of sorting algorithms like QuickSort.
- Neglecting the overhead of pointers in Linked Lists vs contiguous memory in Arrays.
- Miscalculating tree height or number of nodes for full vs complete binary trees.
More Revision Notes
Ready to test yourself?
Play topic-wise Data Structures & Algorithms questions in Aspirant Arcade — gamified MCQ practice.
Download Free