Data structures and algorithms interview questions
Arrays, linked lists, stacks, queues, trees, searching, sorting and complexity.
1. What is the difference between an array and a linked list?
An array stores elements in contiguous memory with a fixed size (in C) and gives O(1) access by index, but inserting in the middle is O(n). A linked list stores nodes connected by pointers, grows dynamically and inserts in O(1) at a known node, but access by position is O(n).
Asked in: Infosys, Wipro Elite NTH
2. What is the difference between a stack and a queue?
A stack is LIFO (last in, first out): push and pop at one end, used for function calls, undo and bracket matching. A queue is FIFO (first in, first out): insert at the rear and remove from the front, used for scheduling and BFS.
3. What is time complexity? What does O(n) mean?
Time complexity describes how running time grows with input size n. O(1) is constant, O(log n) logarithmic (binary search), O(n) linear (one loop), O(n log n) (merge sort) and O(n²) (nested loops). Space complexity measures extra memory in the same way.
4. How does binary search work?
On a sorted array, compare the target with the middle element; if smaller, search the left half, if larger the right half, and repeat. Each step halves the range, so it takes O(log n) time.
Asked in: Tech Mahindra
5. Compare common sorting algorithms.
Bubble, selection and insertion sort are O(n²) (insertion is fast on nearly sorted data). Merge sort is O(n log n) always and stable but needs extra memory. Quick sort is O(n log n) on average, O(n²) in the worst case, and sorts in place. Heap sort is O(n log n) in place.
6. What is hashing?
Mapping a key to an index in a table using a hash function, giving average O(1) insert and lookup. When two keys land in the same slot (a collision) they are handled by chaining (a list per slot) or open addressing (probing for another slot).
7. What is a binary search tree?
A binary tree where every node's left subtree has smaller keys and right subtree larger keys. Search, insert and delete take O(log n) when balanced and O(n) when skewed. An in-order traversal gives sorted order.
8. What are tree traversals? BFS versus DFS?
Depth-first traversals of a tree are in-order (left, root, right), pre-order (root, left, right) and post-order (left, right, root). BFS visits level by level using a queue; DFS goes deep first using recursion or a stack.
9. How do you reverse a linked list?
Walk the list with three pointers (previous, current, next): save next, point current back to previous, move previous and current one step forward. When current becomes null, previous is the new head. O(n) time, O(1) space.
10. How do you detect a loop in a linked list?
Floyd's method: move a slow pointer one step and a fast pointer two steps at a time. If they ever meet there is a cycle; if fast reaches null there is none.
11. What is the difference between recursion and iteration?
Recursion solves a problem by calling the function on smaller inputs, which is natural for trees and divide-and-conquer but uses stack memory. Iteration uses loops and constant extra memory. Any recursion can be rewritten iteratively, sometimes with an explicit stack.
12. What is dynamic programming?
Solving a problem by breaking it into overlapping subproblems and storing their answers so each is computed once, either top-down with memoisation or bottom-up with a table. Examples: Fibonacci, knapsack, longest common subsequence, coin change.
Asked in: TCS NQT, Wipro Elite NTH, LTIMindtree