1. What is a "Data Structure"?

A data structure is a specialized format for organizing, processing, retrieving, and storing data. It is a mathematical or logical model for organizing data so that it can be used efficiently.

2. What are the common types of Data Structures?

Linear: Array, Linked List, Stack, Queue.
Non-Linear: Tree, Graph, Hash Table.

3. What is an "Array"?

A collection of items of the same data type stored in contiguous memory locations. It allows for fast random access using an index.

4. What is a "Linked List"?

A linear data structure where elements (nodes) are stored in nodes, and each node points to the next node in the sequence. It's not stored in contiguous memory.

5. What are the different types of Linked Lists?

Singly Linked List: Each node points to the next node.
Doubly Linked List: Each node points to both the next and previous nodes.
Circular Linked List: The last node points back to the first node.

6. What's the difference between an Array and a Linked List?

Array: Fixed size (usually); fast access (O(1)); contiguous memory.
Linked List: Dynamic size; slow access (O(n)); non-contiguous memory.

7. What is a "Stack"?

A linear data structure that follows the "Last In, First Out" (LIFO) principle. Elements are added and removed from the same end (top).

8. What are the common operations on a Stack?

push(): Add an item to the top.
pop(): Remove and return the top item.
peek(): Return the top item without removing it.

9. What is a "Queue"?

A linear data structure that follows the "First In, First Out" (FIFO) principle. Elements are added at the rear and removed from the front.

10. What are the different types of Queues?

Linear Queue
Circular Queue
Priority Queue
Double-Ended Queue (Deque)

11. What is a "Hash Table" (Hash Map)?

A data structure that stores key-value pairs. It uses a "hash function" to compute an index into an array of buckets, from which the desired value can be found.

12. What is "Collision" in a Hash Table?

Occurs when two different keys result in the same hash value (index).

13. How do you handle Collisions in Hash Tables?

Chaining: Each bucket contains a linked list of entries that hash to the same index.
Open Addressing: Finding another empty slot within the table (e.g., Linear Probing, Quadratic Probing).

14. What is a "Binary Tree"?

A hierarchical tree structure where each node has at most two children, referred to as the left and right child.

15. What are the different types of Binary Trees?

Full Binary Tree: Each node has 0 or 2 children.
Complete Binary Tree: All levels are filled except possibly the last, and the last level is filled from left to right.
Perfect Binary Tree: All internal nodes have 2 children and all leaves are at the same level.

16. What is a "Binary Search Tree" (BST)?

A binary tree where the left child of a node contains a value less than the node's value, and the right child contains a value greater than the node's value.

17. What are the "Tree Traversal" methods?

In-order: Left, Root, Right (gives sorted order in BST).
Pre-order: Root, Left, Right.
Post-order: Left, Right, Root.
Level-order: Visit nodes level by level (BFS).

18. What is a "Balance Tree"?

A tree where the height of the left and right subtrees of any node differs by at most one (e.g., AVL Tree, Red-Black Tree).

19. What is an "AVL Tree"?

A self-balancing binary search tree where the difference between the heights of left and right subtrees (Balance Factor) cannot be more than one.

20. What is a "Heap"?

A specialized tree-based data structure that satisfies the "Heap Property":

Max-Heap: Root is the maximum element.
Min-Heap: Root is the minimum element.

21. What is a "Graph"?

A non-linear data structure consisting of a finite set of vertices (nodes) and an set of edges connecting them.

22. What are the two types of Graphs?

Directed Graph (Digraph): Edges have a direction.
Undirected Graph: Edges have no direction.

23. What are the common ways to represent a Graph?

Adjacency Matrix: A 2D array of size V x V.
Adjacency List: An array of lists.

24. What is "Breadth-First Search" (BFS)?

A graph traversal algorithm that visits all the vertices at the current level before moving on to the next level (uses a Queue).

25. What is "Depth-First Search" (DFS)?

A graph traversal algorithm that explores as far as possible along each branch before backtracking (uses a Stack or Recursion).

26. What is the "Time Complexity" of common operations in a BST?

Search/Insert/Delete: Average O(log n), Worst-case O(n) (if unbalanced).

27. What is a "Trie" (Prefix Tree)?

A tree-based data structure used for efficient information retrieval, particularly for storing and searching strings (like autocomplete).

28. What is a "Segment Tree"?

A tree data structure used for storing information about intervals or segments, allowing for efficient range queries (like sum, min, max).

29. What is "Fenwick Tree" (Binary Indexed Tree)?

A data structure that provides efficient methods for calculation and manipulation of the prefix sums of a sequence of values.

30. What is a "Disjoint Set Union" (DSU)?

A data structure that keeps track of a set of elements partitioned into several non-overlapping (disjoint) subsets, providing "find" and "union" operations.

31. What's the difference between "BFS" and "DFS"?

BFS: Uses a queue; finds physical proximity; best for shortest path in unweighted graphs.
DFS: Uses a stack; explores a single path to completion; best for connectivity and cycles.

32. What is "Priority Queue"?

A specialized queue where each element has an associated "priority." Elements with high priority are served before elements with low priority.

33. What is a "B-Tree"?

A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time (often used in databases).

34. What is a "B+ Tree"?

A variation of a B-tree where all data is stored in leaf nodes, and internal nodes only contain keys for navigation (even more efficient for databases).

35. What is "Spanning Tree"?

A subset of edges of a connected, undirected graph that connects all the vertices together, without any cycles and with the minimum possible number of edges.

36. What is "Adjacency Matrix" vs "Adjacency List"?

Matrix: O(1) to check edge; O(V^2) space; best for dense graphs.
List: O(V) to check edge; O(V+E) space; best for sparse graphs.

37. What is a "Complete Binary Tree" vs "Full Binary Tree"?

Full: Every node has 0 or 2 children.
Complete: All levels filled except the last, filled from left to right.

38. What is "Post-order Traversal" applications?

Used for deleting a tree and for evaluating mathematical expressions in post-fix notation.

39. What is "In-order Traversal" applications?

Used to get the sorted output of a Binary Search Tree.

40. What is "Pre-order Traversal" applications?

Used to create a copy of a tree and for expression trees (prefix notation).

41. What is "Asymptotic Notation"?

Mathematical tools used to describe the complexity of an algorithm (e.g., Big O, Big Omega, Big Theta).

42. What is "Big O Notation"?

A mathematical notation that describes the upper bound of an algorithm's time or space complexity (the worst-case scenario).

43. What is a "Doubly Circular Linked List"?

A list where each node has both next and previous pointers, and the last node points back to the first while the first points back to the last.

44. What is "Stack Overflow"?

Occurs when the stack memory exceeds its capacity, usually due to excessive recursion or large local variables.

45. What is "Queue Underflow"?

Occurs when an operation tries to remove an element from an empty queue.

46. What is a "Sparse Matrix"?

A matrix in which most of the elements are zero. It can be stored efficiently using a non-linear data structure like a Linked List.

47. What is "Binary Search" and its complexity?

A fast search algorithm on sorted arrays that works by repeatedly dividing the search interval in half. Complexity: O(log n).

48. What is the difference between "Linear" and "Binary" search?

Linear: Unordered data; O(n) average.
Binary: Ordered data; O(log n) average.

49. What is "Memory Fragmentation"?

A phenomenon in which storage space is used inefficiently, reducing capacity and performance (Internal and External).

50. What is "Garbage Collection" in Data Structures?

The process of identifying and reclaiming memory that is no longer being used by the application, managed by the language runtime (like Java, Python).

Data Structures Interview Questions

Table of Contents

What is a "Data Structure"?

What are the common types of Data Structures?

What is an "Array"?

What is a "Linked List"?

What are the different types of Linked Lists?

What's the difference between an Array and a Linked List?

What is a "Stack"?

What are the common operations on a Stack?

What is a "Queue"?

What are the different types of Queues?

What is a "Hash Table" (Hash Map)?

What is "Collision" in a Hash Table?

How do you handle Collisions in Hash Tables?

What is a "Binary Tree"?

What are the different types of Binary Trees?

What is a "Binary Search Tree" (BST)?

What are the "Tree Traversal" methods?

What is a "Balance Tree"?

What is an "AVL Tree"?

What is a "Heap"?

What is a "Graph"?

What are the two types of Graphs?

What are the common ways to represent a Graph?

What is "Breadth-First Search" (BFS)?

What is "Depth-First Search" (DFS)?

What is the "Time Complexity" of common operations in a BST?

What is a "Trie" (Prefix Tree)?

What is a "Segment Tree"?

What is "Fenwick Tree" (Binary Indexed Tree)?

What is a "Disjoint Set Union" (DSU)?

What's the difference between "BFS" and "DFS"?

What is "Priority Queue"?

What is a "B-Tree"?

What is a "B+ Tree"?

What is "Spanning Tree"?

What is "Adjacency Matrix" vs "Adjacency List"?

What is a "Complete Binary Tree" vs "Full Binary Tree"?

What is "Post-order Traversal" applications?

What is "In-order Traversal" applications?

What is "Pre-order Traversal" applications?

What is "Asymptotic Notation"?

What is "Big O Notation"?

What is a "Doubly Circular Linked List"?

What is "Stack Overflow"?

What is "Queue Underflow"?

What is a "Sparse Matrix"?

What is "Binary Search" and its complexity?

What is the difference between "Linear" and "Binary" search?

What is "Memory Fragmentation"?

What is "Garbage Collection" in Data Structures?