Intermediate LevelDATA STRUCTURES · C++ TrackCompiler: g++ -std=c++20 -O2
C++ Data Structures & STL Containers
std::string operations, dynamic std::vector buffers, and fast hash lookups with std::unordered_map.
Exercises:10 Practice Labs
All C++ ModulesData Structure Coding Labs (10)Click any card to start in laboratory
Lab #01 · Strings
Easy8 mins
08. std::string Operations & Character Iteration
Iterate across `std::string` characters and use string utilities.
Objective: Write a function `std::string reverseString(const std::string& s)` that returns the reversed string.
Interactive SandboxStart Lab
Lab #02 · Data Structures
Medium12 mins
09. std::vector Dynamic Arrays & Iterators
Work with `std::vector`, dynamic resizing, and `<algorithm>` sorting.
Objective: Write a program that populates a `std::vector<int>`, filters even numbers, and calculates their average.
Interactive SandboxStart Lab
Lab #03 · Hash Maps
Medium12 mins
10. std::unordered_map & Fast Lookups
Implement O(1) hash map lookups using C++ standard `std::unordered_map`.
Objective: Solve Two Sum in C++ using `std::unordered_map<int, int>` to find pair indices matching target.
Interactive SandboxStart Lab
Lab #04 · Advanced Data Structures
Hard25 mins
Data Structures: O(1) LRU Cache (Doubly Linked List + Hash Map)
Design and implement a high-performance Least Recently Used (LRU) Cache supporting get() and put() in O(1) time complexity.
Objective: Design and implement a Least Recently Used (`LRU`) Cache in C++ operating in strictly $O(1)$ average time complexity:
1. **Architecture & Data Structures**:
- Use a custom **Doubly Linked List** (`Node` structure with `key`, `value`, `prev`, `next`) to maintain access order.
- Use `std::unordered_map<int, Node*>` to map keys directly to node pointers for instant $O(1)$ lookup.
- Maintain dummy `head` and `tail` sentinel nodes to avoid edge-case pointer checks.
2. **LRUCache Class Specifications**:
- `LRUCache(int capacity)`: Initializes the cache with positive capacity.
- `int get(int key)`: Returns the value of the key if it exists, otherwise returns `-1`. Moves the accessed node to the front (head) of the list.
- `void put(int key, int value)`: Updates value if key exists (and moves to head). If key does not exist, inserts new node at the head. If capacity is exceeded, evicts the least recently used node from the tail and removes it from the hash map.
- `void displayCache() const`: Displays current cached items from most recently used to least recently used.
3. **In `main()`**:
- Initialize `LRUCache cache(2)`.
- Perform sequence: `put(1, 10)`, `put(2, 20)`, `get(1)`, `put(3, 30)` (evicts key 2), `get(2)` (returns -1), `put(4, 40)` (evicts key 1), `get(1)` (-1), `get(3)` (30), `get(4)` (40).
Interactive SandboxStart Lab
Lab #05 · Tree Data Structures
Hard22 mins
Data Structures: Trie (Prefix Tree) with Autocomplete & Frequency
Construct a high-performance Trie (Prefix Tree) supporting word insertions, prefix searches, frequency tracking, and autocomplete suggestions.
Objective: Implement a dynamic Prefix Tree (`Trie`) in C++ to store a dictionary of strings and support fast prefix queries:
1. **TrieNode Structure**:
- `TrieNode* children[26]`: Array of pointers for lowercase English letters ('a' through 'z').
- `bool isEndOfWord`: Boolean flag indicating completed word termination.
- `int prefixCount`: Number of words passing through this node.
2. **Trie Class Methods**:
- `Trie()`: Constructor initializing root.
- `void insert(const std::string& word)`: Inserts a word into the trie in $O(L)$ time ($L = \text{word length}$).
- `bool search(const std::string& word) const`: Returns `true` if the exact word exists.
- `bool startsWith(const std::string& prefix) const`: Returns `true` if any word starts with the prefix.
- `int countPrefix(const std::string& prefix) const`: Returns the total number of words sharing the prefix.
- `std::vector<std::string> getSuggestions(const std::string& prefix) const`: Uses DFS traversal to return all words completing the given prefix.
3. **In `main()`**:
- Insert words: `"byte"`, `"bytes"`, `"byteslab"`, `"build"`, `"buffer"`, `"bug"`.
- Search exact words and prefixes.
- Print autocomplete suggestions for prefix `"bu"` and `"byte"`.
Interactive SandboxStart Lab
Lab #06 · Tree Data Structures
Hard25 mins
Data Structures: Binary Search Tree (Insert, Delete, LCA & Balancing)
Implement a complete Binary Search Tree (BST) with multi-case node deletion (0, 1, 2 children), traversals, Lowest Common Ancestor (LCA), and balance checking.
Objective: Implement a robust Binary Search Tree (`BST`) data structure in C++:
1. **BSTNode Structure**:
- `int value`, `BSTNode* left`, `BSTNode* right`.
2. **BST Class Operations**:
- `void insert(int val)`: Inserts a value maintaining BST property.
- `bool search(int val) const`: Searches for a key in $O(\log N)$ average time.
- `void deleteNode(int val)`: Removes a node handling all 3 structural cases:
- Leaf node (0 children).
- Node with 1 child.
- Node with 2 children (replaces with in-order successor minimum from right subtree).
- `void inorderTraversal() const`: Prints sorted values.
- `void levelOrderTraversal() const`: Breadth-first traversal using `std::queue`.
- `int findLCA(int n1, int n2) const`: Finds the Lowest Common Ancestor of two nodes.
- `bool isBalanced() const`: Checks if height difference between left and right subtrees of every node is at most 1.
3. **In `main()`**:
- Insert values: `50, 30, 70, 20, 40, 60, 80`.
- Print In-order and Level-order traversals.
- Find LCA of `(20, 40)` (should be `30`) and `(20, 80)` (should be `50`).
- Delete node `30` (2 children) and verify tree integrity.
Interactive SandboxStart Lab
Lab #07 · Heap Data Structures
Hard25 mins
Data Structures: Binary Min-Heap & Continuous Stream Median
Construct an array-based Binary Min-Heap from scratch with sift-up/down, and implement a 2-Heap continuous stream median tracker.
Objective: Construct a custom Binary Heap from scratch and solve the continuous Running Stream Median problem:
1. **Custom MinHeap Implementation**:
- Private `std::vector<int> heap`.
- `void push(int val)`: Adds element and performs **sift-up** to preserve min-heap invariant.
- `void pop()`: Replaces root with last element and performs **sift-down**.
- `int top() const`: Returns minimum element in $O(1)$.
- `int size() const` and `bool empty() const`.
2. **MedianFinder Class (Two-Heap Pattern)**:
- Uses a Max-Heap for lower half numbers and a Min-Heap for upper half numbers.
- `void addNum(int num)`: Inserts number and rebalances heap sizes in $O(\log N)$.
- `double findMedian() const`: Returns exact median in $O(1)$ time.
3. **In `main()`**:
- Test MinHeap operations (`push`, `pop`, `top`).
- Stream numbers: `5, 15, 1, 3, 2, 8, 7` and display running median after each insertion.
Interactive SandboxStart Lab
Lab #08 · Graph Algorithms & Data Structures
Hard25 mins
Data Structures: Weighted Graph with Dijkstra's Shortest Path & BFS
Build an adjacency list weighted graph in C++, implementing BFS, DFS, cycle detection, and Dijkstra's shortest path with route reconstruction.
Objective: Implement a Weighted Graph in C++ with fundamental graph traversal and routing algorithms:
1. **Graph Representation**:
- `int numVertices`.
- `std::vector<std::vector<std::pair<int, int>>> adjList`: Stores `(destination, weight)` pairs for each vertex.
2. **Graph Methods**:
- `void addEdge(int u, int v, int weight, bool bidirectional = false)`: Adds weighted connection.
- `void bfs(int startVertex) const`: Breadth-First Search traversal using a queue.
- `void dfs(int startVertex) const`: Depth-First Search traversal using recursion.
- `bool hasCycle() const`: Detects cycles in graph.
- `std::pair<int, std::vector<int>> dijkstra(int start, int target) const`:
- Computes shortest path distance using `std::priority_queue`.
- Reconstructs and returns the exact path array from `start` to `target` using a `parent[]` array.
3. **In `main()`**:
- Construct a network topology with 6 nodes (0 to 5) and weighted edges.
- Execute BFS and DFS from node 0.
- Run Dijkstra from node 0 to node 5, printing the minimum total path cost and the reconstructed route.
Interactive SandboxStart Lab
Lab #09 · Linked List Data Structures
Medium18 mins
Data Structures: Singly Linked List (Insert, Delete, Reverse & Middle)
Implement a Singly Linked List with positional insertions, node deletions, in-place 3-pointer reversal, and Floyd's cycle & middle detection.
Objective: Implement a comprehensive `SinglyLinkedList` in C++:
1. **Node Structure**:
- `struct Node { int data; Node* next; };`
2. **LinkedList Class Operations**:
- `void insertHead(int val)`: Inserts at the beginning in $O(1)$.
- `void insertTail(int val)`: Appends to the end.
- `void insertAt(int index, int val)`: Inserts at zero-based position index.
- `bool deleteNode(int val)`: Searches for `val` and removes the first matching node, releasing memory with `delete`.
- `void reverse()`: Reverses the linked list in-place using a 3-pointer iterative algorithm (`prev`, `curr`, `next`).
- `int findMiddle() const`: Uses Floyd's Tortoise and Hare (Slow & Fast pointers) to return the middle node value in a single pass.
- `void display() const`: Prints the chain in `10 -> 20 -> 30 -> nullptr` format.
3. **In `main()`**:
- Build list: `insertTail(10)`, `insertTail(20)`, `insertTail(30)`, `insertTail(40)`, `insertTail(50)`.
- Print original list and find middle element (should be `30`).
- Reverse list and display (`50 -> 40 -> 30 -> 20 -> 10 -> nullptr`).
- Delete node `30` and display updated chain.
Interactive SandboxStart Lab
Lab #10 · Linked List Data Structures
Hard20 mins
Data Structures: Circular Linked List (Split Halves & Josephus Problem)
Implement a Circular Linked List where the tail links back to the head, supporting list splitting and the classical Josephus elimination algorithm.
Objective: Implement a `CircularLinkedList` in C++ with advanced pointer manipulations:
1. **Circular Structure**:
- `Node* head` where the last node's `next` points back to `head`.
2. **CircularLinkedList Methods**:
- `void insert(int val)`: Inserts a node while maintaining circular tail-to-head linking.
- `bool deleteNode(int val)`: Deletes a node (handling head deletion, middle deletion, and single-node list) without breaking the circular cycle.
- `void display() const`: Traverses the circular list using `do-while` loop and prints until returning to head.
- `void splitIntoTwoHalves(CircularLinkedList& firstHalf, CircularLinkedList& secondHalf)`: Uses fast and slow pointers to split the circular list into two independent circular sub-lists.
3. **Josephus Problem Solver**:
- `int solveJosephus(int n, int k)`: Simulates the historical **Josephus Circle Elimination**:
- Construct a circular list of $n$ people numbered 1 to $n$.
- Traverse the circle and eliminate every $k$-th person until only 1 survivor remains.
- Return the survivor's number.
4. **In `main()`**:
- Create circular list with `[10, 20, 30, 40, 50, 60]`.
- Display circular chain.
- Split into two halves and display both circular sub-lists (`[10, 20, 30]` and `[40, 50, 60]`).
- Run `solveJosephus(7, 3)` (with 7 people eliminating every 3rd, survivor is person `4`).
Interactive SandboxStart Lab