Mastering The Top 10 Coding Patterns

Dear Readers ??!,

When preparing for coding interviews, it's hard to master various data structures and the common coding patterns, Here are 10 most important data structure coding patterns you should be familiar with, I wrote along with explanations & example of C++ program.

1. Sliding Window

Pattern: Used for problems involving contiguous subarrays or substrings.

Example Problem: Find the maximum sum of a contiguous subarray of size k.

Example Code:

#include <iostream>
#include <vector>
#include <climits>
// either writing each time std:: you can used std namespace
int maxSumSubarray(const std::vector<int>& arr, int k) {
    int maxSum = INT_MIN;
    int windowSum = 0;
    
    for (int i = 0; i < arr.size(); ++i) {
        windowSum += arr[i];
        if (i >= k - 1) {
            maxSum = std::max(maxSum, windowSum);
            windowSum -= arr[i - (k - 1)];
        }
    }
    
    return maxSum;
}

int main() {
    std::vector<int> arr = {2, 1, 5, 1, 3, 2};
    int k = 3;
    std::cout << "Maximum sum of a subarray of size " << k << " is " << maxSumSubarray(arr, k) << std::endl;
    return 0;
}        

2. Two Pointers

Pattern: this patter is used for problems involving pairs in an array or a linked list, often to find elements that meet certain criteria.

Example Problem: Find if there exists a pair of numbers in the array that adds up to a specific target.

Example Code:

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

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;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 6};
    int target = 6;
    std::sort(arr.begin(), arr.end());  // Ensure the array is sorted
    std::cout << "Pair with sum " << target << (hasPairWithSum(arr, target) ? " exists." : " does not exist.") << std::endl;
    return 0;
}        

3. Fast and Slow Pointers

Pattern: Useful for problems involving cyclic patterns in linked lists or arrays.

Example Problem: Detect a cycle in a linked list.

Example Code:

#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int val) : value(val), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = head;  // Creating a cycle

    std::cout << "The linked list " << (hasCycle(head) ? "has a cycle." : "does not have a cycle.") << std::endl;
    return 0;
}        

4. Merge Intervals

Pattern: Useful for problems, involving overlapping intervals.

Example Problem: Merge overlapping intervals.

Example Code:

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

struct Interval {
    int start;
    int end;
    Interval(int s, int e) : start(s), end(e) {}
};

std::vector<Interval> mergeIntervals(std::vector<Interval>& intervals) {
    if (intervals.empty()) {
        return {};
    }
    
    std::sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start; });
    
    std::vector<Interval> merged;
    merged.push_back(intervals[0]);
    
    for (const Interval& interval : intervals) {
        if (merged.back().end >= interval.start) {
            merged.back().end = std::max(merged.back().end, interval.end);
        } else {
            merged.push_back(interval);
        }
    }
    
    return merged;
}

int main() {
    std::vector<Interval> intervals = {Interval(1, 3), Interval(2, 6), Interval(8, 10), Interval(15, 18)};
    std::vector<Interval> merged = mergeIntervals(intervals);
    
    std::cout << "Merged intervals: ";
    for (const Interval& interval : merged) {
        std::cout << "[" << interval.start << ", " << interval.end << "] ";
    }
    std::cout << std::endl;
    return 0;
}        

5. Cyclic Sort

Pattern: Useful for problems involving a range of consecutive numbers.

Example Problem: Find the missing number in an array containing numbers from 0 to n.

Example Code:

#include <iostream>
#include <vector>

int findMissingNumber(std::vector<int>& nums) {
    int i = 0;
    while (i < nums.size()) {
        if (nums[i] < nums.size() && nums[i] != nums[nums[i]]) {
            std::swap(nums[i], nums[nums[i]]);
        } else {
            ++i;
        }
    }
    
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != i) {
            return i;
        }
    }
    
    return nums.size();
}

int main() {
    std::vector<int> nums = {3, 0, 1};
    std::cout << "The missing number is: " << findMissingNumber(nums) << std::endl;
    return 0;
}        

6. In-place Reversal of a Linked List

Pattern: Useful for reversing or rotating linked lists.

Example Problem: Reverse a singly linked list.

Example Code:

#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int val) : value(val), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    
    while (current != nullptr) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    head = reverseList(head);
    
    std::cout << "Reversed list: ";
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->value << " ";
        current = current->next;
    }
    std::cout << std::endl;

    return 0;
}        

7. Tree Traversal

Pattern: Used for problems involving tree traversal, like pre-order, in-order, and post-order traversal.

Example Problem: In-order traversal of a binary tree.

Example Code:

#include <iostream>
#include <vector>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

void inOrderTraversal(TreeNode* root, std::vector<int>& result) {
    if (root == nullptr) {
        return;
    }
    inOrderTraversal(root->left, result);
    result.push_back(root->value);
    inOrderTraversal(root->right, result);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
    
    std::vector<int> result;
    inOrderTraversal(root, result);
    
    std::cout << "In-order traversal: ";
    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}        

8. Binary Search

Pattern: Used for problems involving searching in sorted arrays.

Example Problem: Find the index of a target number in a sorted array.

Example Code:

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    int target = 5;
    std::cout << "Index of " << target << " is: " << binarySearch(nums, target) << std::endl;
    return 0;
}        

9. Top K Elements

Pattern: Used for problems involving finding the top K elements in a collection.

Example Problem: Find the Kth largest element in an array.

Example Code:

#include <iostream>
#include <vector>
#include <queue>

int findKthLargest(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.top();
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    std::cout << "The " << k << "th largest element is: " << findKthLargest(nums, k) << std::endl;
    return 0;
}        

10. Graph Traversal (BFS and DFS)

Pattern: Used for problems involving graph traversal, like finding connected components or shortest paths.

Example Problem: Perform BFS traversal of a graph.

Example Code:

#include <iostream>
#include <vector>
#include <queue>

void bfs(int start, const std::vector<std::vector<int>>& adjList) {
    std::vector<bool> visited(adjList.size(), false);
    std::queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        std::cout << node << " ";
        
        for (int neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    std::vector<std::vector<int>> adjList = {
        {1, 2},
        {0, 3, 4},
        {0, 4},
        {1, 5},
        {1, 2, 5},
        {3, 4}
    };
    
    std::cout << "BFS traversal starting from node 0: ";
    bfs(0, adjList);
    std::cout << std::endl;
    
    return 0;
}        

Summary

These coding patterns cover a wide range of common problems that you you'll see often in technical interviews. By mastering these patterns, you'll fell confident and able to tackle a variety of problems in an real time interview.

Thanks ??.

Shahbaz Ali