Data Structures & Algorithms Aptitude Questions with Solutions
40 Data Structures & Algorithms questions with hints, worked solutions and time targets — 14 easy · 19 medium · 7 hard.
- Section: Programming MCQs
- Questions: 40
- By difficulty: 14 easy · 19 medium · 7 hard
- Cost: Free, unlimited on every plan
Arrays, linked lists, stacks, trees, sorting and complexity, asked as MCQs.
Data Structures & Algorithms: the essentials
Most questions ask for a complexity, a count, or the state after one operation.
Structures
- Stack (last in, first out): recursion, bracket matching, postfix evaluation, depth-first search. Queue (first in, first out): breadth-first search and level-order traversal.
- Linked list with only a head pointer: inserting at the head is O(1), at the tail O(n). Floyd's slow and fast pointers find a loop in O(1) space.
- Binary trees: height h, counted in edges, allows at most 2^(h + 1) − 1 nodes; if every node has 0 or 2 children, leaves = internal nodes + 1. Inorder is left, root, right.
- BST: inorder is sorted; search is O(log n) when balanced, O(n) in the worst case.
- Heap in a 0-indexed array: the children of i are 2i + 1 and 2i + 2; insert and extract are O(log n).
- Graphs: a complete graph has n(n − 1)/2 edges; adjacency lists take O(V + E) space, a matrix O(V²); a directed graph has a topological order exactly when it has no cycle.
Algorithms
- Bubble, selection and insertion sort are O(n²); insertion sort is O(n) on sorted input; bubble sort's swaps equal the inversions.
- Merge sort: O(n log n), stable, O(n) extra space. Quicksort: O(n log n) on average, O(n²) on sorted input with an end pivot. Heapsort: O(n log n), in place, unstable.
- Binary search makes at most ⌊log₂ n⌋ + 1 comparisons. The Tower of Hanoi needs 2ⁿ − 1 moves.
Questions
- Evaluating a postfix expression Medium
Evaluate the postfix expression 5 6 2 + * 12 4 / - using the usual stack method. - Infix to postfix Medium
Convert A + B * C - D / E to postfix, with * and / binding tighter than + and - and all operators left associative. - Evaluating a prefix expression Medium
Evaluate the prefix expression + 9 * 3 - 5 2. - An impossible stack output Hard
The numbers 1, 2, 3, 4 are pushed onto a stack in that order, and a pop may be performed at any point. Which output sequence is impossible? - A queue from two stacks Medium
A queue is built from two stacks: enqueue pushes onto stack A, and dequeue pops from stack B, refilling B by emptying A into it whenever B is empty. - Elements in a circular queue Medium
A circular queue occupies an array of 8 slots, with one slot always left empty so that full and empty can be told apart. - Structure behind level-order traversal Easy
Which data structure does a level-order (breadth-first) traversal of a binary tree rely on? - Constant-time list operation Easy
A singly linked list is kept with only a head pointer. Which operation runs in O(1) time? - Pointer updates in a doubly linked list Medium
A new node is inserted between two existing nodes of a doubly linked list. How many pointer fields have to be assigned? - Circular list with a tail pointer Medium
A circular singly linked list is kept with a single pointer to its last node. Which insertions are possible in O(1) time? - Detecting a loop in constant space Easy
Which technique detects a loop in a singly linked list using only O(1) extra space? - Maximum nodes for a given height Easy
A binary tree has height 5, taking the height of a single-node tree to be 0. What is the maximum number of nodes it can contain? - Leaves of a full binary tree Medium
In a binary tree every node has either 0 or 2 children. If the tree contains 10 internal nodes, how many leaves does it have? - Rebuilding a tree from two traversals Hard
A binary tree has preorder A B D E C F and inorder D B E A C F. What is its postorder traversal? - The sorted traversal Easy
Which traversal of a binary search tree visits the keys in ascending sorted order? - Worst-case BST search Easy
What is the worst-case time complexity of searching for a key in a binary search tree holding n keys? - Deleting the root of a BST Medium
A BST has 50 at the root, 30 and 70 as its children, 20 and 40 below 30, and 60 and 80 below 70. The root is deleted and replaced by its inorder successor. - From BST preorder to postorder Hard
The preorder traversal of a binary search tree is 50, 30, 20, 40, 70, 60, 80. What is its postorder traversal? - Sparsest AVL tree Hard
What is the minimum number of nodes in an AVL tree of height 4, counting the height of a single node as 0? - Inserting into a min-heap Medium
A min-heap is stored as the array [10, 20, 15, 30, 40]. The key 5 is inserted. What does the array look like afterwards? - Spotting a valid max-heap Medium
Reading each array as a complete binary tree in which the children of index i sit at 2i + 1 and 2i + 2, which array satisfies the max-heap property? - Extract-max on a heap Hard
A max-heap is stored as [50, 30, 40, 10, 20, 35]. One extract-max operation is performed. What is the resulting array? - Quicksort on sorted input Easy
Quicksort always takes the first element as its pivot. What is its running time on an array that is already sorted in ascending order? - One partition step Hard
The array [7, 2, 1, 6, 8, 5, 3, 4] is partitioned by the Lomuto scheme with the last element as pivot: a boundary index i starts at −1, every element less… - Which sort is unstable Easy
Which of these sorting algorithms is not stable in its usual implementation? - Swaps in a bubble sort Medium
How many swaps does bubble sort perform while sorting [5, 4, 3, 2, 1] into ascending order? - Best case of insertion sort Easy
What is the best-case running time of insertion sort, and on which input does it occur? - The sort that needs a buffer Easy
Which of these comparison sorts needs O(n) auxiliary space in its usual array implementation? - Comparisons in a binary search Medium
What is the maximum number of comparisons binary search makes on a sorted array of 1000 elements? - Finding both the minimum and the maximum Hard
What is the minimum number of comparisons needed to find both the smallest and the largest of 100 distinct integers? - Where linear probing lands Medium
Keys are inserted into a hash table of size 10 with h(k) = k mod 10 and linear probing. The keys 12, 22 and 32 are inserted in that order into an empty table. - Primary clustering Medium
Which collision-resolution scheme suffers from primary clustering, in which occupied slots pile up into long consecutive runs? - Edges of a complete graph Easy
How many edges does a complete undirected graph on 12 vertices have? - Space of an adjacency list Easy
A graph has V vertices and E edges. How much space does its adjacency list representation take? - Depth-first visiting order Medium
An undirected graph has these adjacency lists: A depth-first search starts at A and always moves to the unvisited neighbour that comes first alphabetically. - Shortest path by breadth-first search Medium
An undirected graph has these adjacency lists: A breadth-first search from A is used to find the shortest path to F. How many edges does that path contain? - When a topological order exists Easy
A directed graph has a topological ordering exactly when the graph... - Address in a row-major array Medium
An array A[10][20] of 4-byte integers is stored in row-major order with base address 1000, indices starting at 0. What is the address of A[3][5]? - Counting recursive calls Medium
The naive recursion fib(n) = fib(n − 1) + fib(n − 2), with fib(0) and fib(1) returned directly, is used to compute fib(5). - Tower of Hanoi Easy
What is the minimum number of moves needed to solve the Tower of Hanoi puzzle with 6 disks?
Placement tests that ask data structures & algorithms
- Full-Length Aptitude Paper CodeKairo
- Big Tech Screen — Theory Drill CodeKairo
- Capgemini — Technical & English Capgemini
- HCLTech — Written Test HCLTech
- Tech Mahindra — Aptitude & Technical Tech Mahindra
- LTIMindtree — Online Assessment LTIMindtree
- Mphasis — AMCAT Assessment Mphasis
- Virtusa — Online Test & Coder Challenge Virtusa
- Deloitte — Online Assessment Deloitte
- Morgan Stanley — Aptitude & Technical Morgan Stanley