An array is a collection of elements stored at contiguous memory locations. It allows constant-time access to elements if their index is known.
Analogy: Imagine a row of lockers in a school, each labeled with a number. To find an item, you go directly to the locker by its number.
Key Operations:
Interview Question:
Problem: Write a function to find the second largest number in an array of integers.
A linked list is a collection of nodes where each node contains data and a reference to the next node in the sequence.
Analogy: Consider a treasure hunt where each clue leads to the next location.
Key Operations:
Interview Question:
Problem: Reverse a linked list iteratively.
3. Stacks
A stack is a collection of elements that follows the Last In, First Out (LIFO) principle. Only the top element can be accessed or modified at any time.
Analogy: Imagine a stack of plates where you can only take or add plates from the top.
Key Operations:
Push (add): (O(1))
Pop (remove): (O(1))
Interview Question:
Problem: Implement a stack using two queues.
4. Queues
A queue follows the First In, First Out (FIFO) principle. Elements are added at the rear and removed from the front.
Analogy: Think of a line at a ticket counter where people are served in the order they arrive.
Key Operations:
Enqueue (add): (O(1))
Dequeue (remove): (O(1))
Interview Question:
Problem: Design a circular queue.
5. Hash Tables
A hash table uses a hash function to map keys to values, allowing for fast data retrieval.
Analogy: Imagine a library where each book has a unique code that tells you exactly which shelf it’s on.
Key Operations:
- Insertion, Deletion, Access: (O(1)) (on average).
Interview Question:
Problem: Implement a hash map that supports insert, delete, and get operations in (O(1)).
6. Binary Trees
A binary tree is a hierarchical structure where each node has at most two children, called the left and right child.
Analogy: Picture a family tree where each person has up to two immediate descendants.
Key Operations:
- Traversal (Inorder, Preorder, Postorder): (O(n))
Interview Question:
Problem: Write a function to check if a binary tree is a valid binary search tree (BST).
7. Binary Search Trees (BSTs)
A binary search tree is a binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.
Analogy: Think of organizing books on a shelf where smaller books are placed on the left and larger ones on the right.
Key Operations:
- Search, Insertion, Deletion: (O(h)) (where (h) is the height of the tree).
Interview Question:
Problem: Given a BST, find its (k)-th smallest element.
8. Heaps
A heap is a special tree-based structure where the parent node is always greater than or equal to (max heap) or less than or equal to (min heap) its children.
Analogy: Imagine a leaderboard where the highest scorer is always on top.
Key Operations:
Interview Question:
Problem: Implement a priority queue using a min heap.
9. Graphs
A graph is a collection of nodes (vertices) connected by edges. It can be directed or undirected, weighted or unweighted.
Analogy: Think of a city's map where intersections are nodes and roads are edges.
Key Operations:
- Traversal (DFS, BFS): (O(V + E)), where (V) is vertices and (E) is edges.
Interview Question:
Problem: Find the shortest path in an unweighted graph.
10. Tries
A trie (pronounced "try") is a tree-like data structure used for efficient retrieval of strings, especially in dictionary-like scenarios.
Analogy: Imagine an autocomplete system that narrows suggestions as you type.
Key Operations:
- Insert, Search: (O(m)), where (m) is the length of the string.
Interview Question:
Problem: Implement an autocomplete system using a trie.
11. Disjoint Sets (Union-Find)
A disjoint set is a data structure that tracks a set of elements partitioned into disjoint subsets. It supports union and find operations.
Analogy: Think of different groups of friends where you can check if two people are in the same group.
Key Operations:
- Union, Find: (O(\alpha(n))), where (\alpha) is the inverse Ackermann function.
Interview Question:
Problem: Detect a cycle in an undirected graph using the union-find algorithm.
12. Segment Trees
A segment tree is a tree used for storing intervals or segments and allows for efficient queries and updates.
Analogy: Think of a scoreboard where you can quickly find the highest score in any range.
Key Operations:
- Query, Update: (O(\log n))
Interview Question:
Problem: Build a segment tree to find the sum of elements in a given range.
Conclusion
Mastering these 12 data structures will not only strengthen your problem-solving skills but also prepare you for various scenarios in programming and technical interviews. Each data structure has its unique use cases and trade-offs, making it essential to understand when and where to apply them.
