Data Structures & Algorithms in C++

This guide covers essential data structures and algorithms commonly asked in technical interviews for embedded systems and validation engineering roles.

---

Arrays

Basic Operations

#include <iostream>
#include <vector>
#include <algorithm>

// ============================================================
// STATIC ARRAY
// ============================================================
int arr[5] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);  // Get array size

// ============================================================
// DYNAMIC ARRAY (std::vector)
// ============================================================
std::vector<int> vec = {1, 2, 3, 4, 5};

// Common operations
vec.push_back(6);           // Add to end: O(1) amortized
vec.pop_back();             // Remove from end: O(1)
vec.insert(vec.begin(), 0); // Insert at beginning: O(n)
vec.erase(vec.begin());     // Remove from beginning: O(n)
int first = vec.front();    // Access first: O(1)
int last = vec.back();      // Access last: O(1)
int elem = vec[2];          // Random access: O(1)
size_t len = vec.size();    // Get size: O(1)
bool empty = vec.empty();   // Check if empty: O(1)
vec.clear();                // Remove all: O(n)
vec.reserve(100);           // Pre-allocate capacity

// Iteration
for (int i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

for (const auto& val : vec) {
    std::cout << val << " ";
}

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Two Pointers Technique

// Find pair with given sum (sorted array)
bool hasPairWithSum(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

// Remove duplicates from sorted array (in-place)
int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;

    int writeIdx = 1;
    for (int readIdx = 1; readIdx < nums.size(); readIdx++) {
        if (nums[readIdx] != nums[readIdx - 1]) {
            nums[writeIdx++] = nums[readIdx];
        }
    }
    return writeIdx;
}

// Reverse array in-place
void reverseArray(std::vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        std::swap(arr[left++], arr[right--]);
    }
}

Sliding Window

// Maximum sum subarray of size k
int maxSumSubarray(const std::vector<int>& arr, int k) {
    if (arr.size() < k) return -1;

    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;
    for (int i = k; i < arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];  // Slide window
        maxSum = std::max(maxSum, windowSum);
    }
    return maxSum;
}

// Longest substring without repeating characters
int lengthOfLongestSubstring(const std::string& s) {
    std::unordered_map<char, int> charIndex;
    int maxLen = 0, start = 0;

    for (int end = 0; end < s.length(); end++) {
        if (charIndex.count(s[end]) && charIndex[s[end]] >= start) {
            start = charIndex[s[end]] + 1;
        }
        charIndex[s[end]] = end;
        maxLen = std::max(maxLen, end - start + 1);
    }
    return maxLen;
}

Binary Search

// Standard binary search
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;  // Not found
}

// Find first occurrence
int findFirst(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // Continue searching left
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// Find last occurrence
int findLast(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // Continue searching right
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// Search in rotated sorted array
int searchRotated(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

---

Linked List

Singly Linked List

// Node definition
struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* n) : val(x), next(n) {}
};

// ============================================================
// BASIC OPERATIONS
// ============================================================

// Insert at beginning: O(1)
ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;
}

// Insert at end: O(n)
ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) return newNode;

    ListNode* curr = head;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = newNode;
    return head;
}

// Delete node with value: O(n)
ListNode* deleteNode(ListNode* head, int val) {
    if (!head) return nullptr;

    if (head->val == val) {
        ListNode* temp = head->next;
        delete head;
        return temp;
    }

    ListNode* curr = head;
    while (curr->next && curr->next->val != val) {
        curr = curr->next;
    }

    if (curr->next) {
        ListNode* temp = curr->next;
        curr->next = curr->next->next;
        delete temp;
    }
    return head;
}

// Get length: O(n)
int getLength(ListNode* head) {
    int count = 0;
    while (head) {
        count++;
        head = head->next;
    }
    return count;
}

// Search: O(n)
bool search(ListNode* head, int val) {
    while (head) {
        if (head->val == val) return true;
        head = head->next;
    }
    return false;
}

Common Interview Problems

// ============================================================
// REVERSE LINKED LIST (Iterative)
// ============================================================
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// ============================================================
// REVERSE LINKED LIST (Recursive)
// ============================================================
ListNode* reverseListRecursive(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

// ============================================================
// DETECT CYCLE (Floyd's Cycle Detection)
// ============================================================
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) return true;
    }
    return false;
}

// Find cycle start
ListNode* detectCycleStart(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            // Found cycle, find start
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

// ============================================================
// FIND MIDDLE NODE
// ============================================================
ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// ============================================================
// MERGE TWO SORTED LISTS
// ============================================================
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// ============================================================
// REMOVE NTH NODE FROM END
// ============================================================
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;

    ListNode* first = &dummy;
    ListNode* second = &dummy;

    // Move first n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        first = first->next;
    }

    // Move both until first reaches end
    while (first) {
        first = first->next;
        second = second->next;
    }

    // Delete nth node from end
    ListNode* temp = second->next;
    second->next = second->next->next;
    delete temp;

    return dummy.next;
}

// ============================================================
// CHECK PALINDROME
// ============================================================
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;

    // Find middle
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Reverse second half
    ListNode* secondHalf = reverseList(slow->next);

    // Compare
    ListNode* first = head;
    ListNode* second = secondHalf;
    bool result = true;

    while (second) {
        if (first->val != second->val) {
            result = false;
            break;
        }
        first = first->next;
        second = second->next;
    }

    // Restore list (optional)
    slow->next = reverseList(secondHalf);

    return result;
}

---

Hash Map / Unordered Map

Basic Operations

#include <unordered_map>
#include <map>

// ============================================================
// UNORDERED MAP (Hash Table) - Average O(1) operations
// ============================================================
std::unordered_map<std::string, int> hashMap;

// Insert
hashMap["apple"] = 5;
hashMap.insert({"banana", 3});
hashMap.emplace("cherry", 7);

// Access
int count = hashMap["apple"];           // Creates entry if not exists
int count2 = hashMap.at("banana");      // Throws if not exists

// Check existence
if (hashMap.count("apple")) { /* exists */ }
if (hashMap.find("apple") != hashMap.end()) { /* exists */ }

// Delete
hashMap.erase("apple");

// Iteration
for (const auto& [key, value] : hashMap) {
    std::cout << key << ": " << value << "\n";
}

// ============================================================
// ORDERED MAP (Red-Black Tree) - O(log n) operations
// ============================================================
std::map<std::string, int> orderedMap;
// Keys are automatically sorted
orderedMap["zebra"] = 1;
orderedMap["apple"] = 2;
orderedMap["mango"] = 3;
// Iteration gives: apple, mango, zebra

Common Interview Problems

// ============================================================
// TWO SUM
// ============================================================
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> numToIndex;

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (numToIndex.count(complement)) {
            return {numToIndex[complement], i};
        }
        numToIndex[nums[i]] = i;
    }
    return {};
}

// ============================================================
// FIRST NON-REPEATING CHARACTER
// ============================================================
int firstUniqChar(const std::string& s) {
    std::unordered_map<char, int> freq;

    for (char c : s) {
        freq[c]++;
    }

    for (int i = 0; i < s.length(); i++) {
        if (freq[s[i]] == 1) return i;
    }
    return -1;
}

// ============================================================
// GROUP ANAGRAMS
// ============================================================
std::vector<std::vector<std::string>> groupAnagrams(
    std::vector<std::string>& strs) {

    std::unordered_map<std::string, std::vector<std::string>> groups;

    for (const auto& s : strs) {
        std::string key = s;
        std::sort(key.begin(), key.end());
        groups[key].push_back(s);
    }

    std::vector<std::vector<std::string>> result;
    for (auto& [key, group] : groups) {
        result.push_back(std::move(group));
    }
    return result;
}

// ============================================================
// SUBARRAY SUM EQUALS K
// ============================================================
int subarraySum(const std::vector<int>& nums, int k) {
    std::unordered_map<int, int> prefixCount;
    prefixCount[0] = 1;  // Empty prefix

    int count = 0, prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;

        // Check if (prefixSum - k) exists
        if (prefixCount.count(prefixSum - k)) {
            count += prefixCount[prefixSum - k];
        }

        prefixCount[prefixSum]++;
    }
    return count;
}

// ============================================================
// LRU CACHE
// ============================================================
class LRUCache {
private:
    int capacity_;
    std::list<std::pair<int, int>> cache_;  // {key, value}
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map_;

public:
    LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        if (map_.find(key) == map_.end()) return -1;

        // Move to front (most recently used)
        cache_.splice(cache_.begin(), cache_, map_[key]);
        return map_[key]->second;
    }

    void put(int key, int value) {
        if (map_.find(key) != map_.end()) {
            // Update existing
            map_[key]->second = value;
            cache_.splice(cache_.begin(), cache_, map_[key]);
            return;
        }

        // Evict if full
        if (cache_.size() == capacity_) {
            int lruKey = cache_.back().first;
            cache_.pop_back();
            map_.erase(lruKey);
        }

        // Insert new
        cache_.push_front({key, value});
        map_[key] = cache_.begin();
    }
};

---

Trees

Binary Tree

// Node definition
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// ============================================================
// TREE TRAVERSALS
// ============================================================

// Inorder (Left, Root, Right) - gives sorted order for BST
void inorder(TreeNode* root, std::vector<int>& result) {
    if (!root) return;
    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

// Preorder (Root, Left, Right)
void preorder(TreeNode* root, std::vector<int>& result) {
    if (!root) return;
    result.push_back(root->val);
    preorder(root->left, result);
    preorder(root->right, result);
}

// Postorder (Left, Right, Root)
void postorder(TreeNode* root, std::vector<int>& result) {
    if (!root) return;
    postorder(root->left, result);
    postorder(root->right, result);
    result.push_back(root->val);
}

// Level Order (BFS)
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;

    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        std::vector<int> level;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

// Iterative Inorder using Stack
std::vector<int> inorderIterative(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> stack;
    TreeNode* curr = root;

    while (curr || !stack.empty()) {
        while (curr) {
            stack.push(curr);
            curr = curr->left;
        }
        curr = stack.top();
        stack.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}

Binary Search Tree (BST)

// ============================================================
// BST OPERATIONS
// ============================================================

// Search: O(h) where h = height
TreeNode* searchBST(TreeNode* root, int val) {
    if (!root || root->val == val) return root;

    if (val < root->val) {
        return searchBST(root->left, val);
    }
    return searchBST(root->right, val);
}

// Insert: O(h)
TreeNode* insertBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);

    if (val < root->val) {
        root->left = insertBST(root->left, val);
    } else {
        root->right = insertBST(root->right, val);
    }
    return root;
}

// Delete: O(h)
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;

    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Node found
        if (!root->left) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        if (!root->right) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // Two children: get inorder successor
        TreeNode* successor = root->right;
        while (successor->left) {
            successor = successor->left;
        }
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

// Validate BST
bool isValidBST(TreeNode* root, long minVal = LONG_MIN, long maxVal = LONG_MAX) {
    if (!root) return true;

    if (root->val <= minVal || root->val >= maxVal) return false;

    return isValidBST(root->left, minVal, root->val) &&
           isValidBST(root->right, root->val, maxVal);
}

Common Tree Problems

// ============================================================
// MAXIMUM DEPTH
// ============================================================
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

// ============================================================
// CHECK IF BALANCED
// ============================================================
int checkHeight(TreeNode* root) {
    if (!root) return 0;

    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) return -1;

    int rightHeight = checkHeight(root->right);
    if (rightHeight == -1) return -1;

    if (std::abs(leftHeight - rightHeight) > 1) return -1;

    return 1 + std::max(leftHeight, rightHeight);
}

bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

// ============================================================
// LOWEST COMMON ANCESTOR
// ============================================================
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;

    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    if (left && right) return root;
    return left ? left : right;
}

// ============================================================
// PATH SUM
// ============================================================
bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;

    if (!root->left && !root->right) {
        return root->val == targetSum;
    }

    return hasPathSum(root->left, targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}

// ============================================================
// INVERT BINARY TREE
// ============================================================
TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;

    std::swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);

    return root;
}

// ============================================================
// SERIALIZE AND DESERIALIZE
// ============================================================
class Codec {
public:
    std::string serialize(TreeNode* root) {
        if (!root) return "null";

        return std::to_string(root->val) + "," +
               serialize(root->left) + "," +
               serialize(root->right);
    }

    TreeNode* deserialize(const std::string& data) {
        std::queue<std::string> nodes;
        std::stringstream ss(data);
        std::string item;

        while (std::getline(ss, item, ',')) {
            nodes.push(item);
        }

        return buildTree(nodes);
    }

private:
    TreeNode* buildTree(std::queue<std::string>& nodes) {
        std::string val = nodes.front();
        nodes.pop();

        if (val == "null") return nullptr;

        TreeNode* node = new TreeNode(std::stoi(val));
        node->left = buildTree(nodes);
        node->right = buildTree(nodes);

        return node;
    }
};

---

Sorting Algorithms

// ============================================================
// QUICK SORT - Average O(n log n), Worst O(n²)
// ============================================================
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// ============================================================
// MERGE SORT - O(n log n) always
// ============================================================
void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    std::vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;

    while (i < leftArr.size() && j < rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (i < leftArr.size()) arr[k++] = leftArr[i++];
    while (j < rightArr.size()) arr[k++] = rightArr[j++];
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// ============================================================
// HEAP SORT - O(n log n)
// ============================================================
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

---

Time & Space Complexity Reference

Data Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)*	O(1)*	O(n)
Hash Map	N/A	O(1)†	O(1)†	O(1)†	O(n)
BST	O(log n)‡	O(log n)‡	O(log n)‡	O(log n)‡	O(n)
Heap	O(1)§	O(n)	O(log n)	O(log n)	O(n)

*With reference to node, †Average case, ‡Balanced tree, §For min/max only

---

Related Topics

• C++ for Hardware - Core C++ concepts
• Design Patterns - Singleton, Factory, Observer

---

References

• Introduction to Algorithms (CLRS)
• LeetCode, HackerRank problem sets
• cppreference.com