In this lesson, we'll tackle Advanced Vector Manipulation, a crucial topic in any technical interview. C++ vectors are versatile and powerful data structures used in almost every aspect of programming. Mastering advanced manipulation techniques can streamline your code, optimize time complexity, and solve complex problems efficiently.

Merge Sort is one of the most common sorting algorithms tested in coding interviews. Merge Sort takes in two vectors sorted in ascending order. The output should efficiently merge them into a single sorted vector. For example, merging {1, 3, 5, 7} and {2, 4, 6, 8} yields {1, 2, 3, 4, 5, 6, 7, 8}.

The mergeSortedVectors algorithm is designed to merge two sorted vectors into a single sorted vector. The algorithm employs the Two Pointer Technique to efficiently accomplish this task with a linear time complexity of O(n + m), where n and m are the sizes of the two input vectors. Here is an overview of the algorithm:

1. Initialization: Create an empty vector mergedVector to store the result. Initialize two pointers (or indices), i and j, to zero; these pointers will traverse vec1 and vec2, respectively.

2. Traverse Both Vectors: Use a while loop to iterate through both vectors until one of the pointers reaches the end of its respective vector.

   • Comparison: In each iteration, compare the elements pointed to by i and j.
   • Appending Smaller Element: Append the smaller element to mergedVector and increment the corresponding pointer.

3. Append Remaining Elements: Once one vector is fully traversed, append the remaining elements of the other vector to mergedVector.

   • Remaining Elements of vec1: Use a while loop to append remaining elements of vec1, if any.
   • Remaining Elements of vec2: Use a while loop to append remaining elements of vec2, if any.

4. Return Result: The mergedVector now contains all elements from vec1 and vec2 in sorted order.

This approach ensures that the merging process is performed in an efficient manner, taking advantage of the pre-sorted nature of the input vectors.

Here's how to implement this in C++:

C++
Copy to clipboard
1#include <iostream>
2#include <vector>
3
4std::vector<int> mergeSortedVectors(const std::vector<int>& vec1, const std::vector<int>& vec2) {
5    std::vector<int> mergedVector;
6    size_t i = 0, j = 0;
7
8    while (i < vec1.size() && j < vec2.size()) {
9        if (vec1[i] < vec2[j]) {
10            mergedVector.push_back(vec1[i]);
11            i++;
12        } else {
13            mergedVector.push_back(vec2[j]);
14            j++;
15        }
16    }
17
18    // Append remaining elements of vec1, if any
19    while (i < vec1.size()) {
20        mergedVector.push_back(vec1[i]);
21        i++;
22    }
23
24    // Append remaining elements of vec2, if any
25    while (j < vec2.size()) {
26        mergedVector.push_back(vec2[j]);
27        j++;
28    }
29
30    return mergedVector;
31}
32
33int main() {
34    std::vector<int> vec1 = {1, 3, 5, 7};
35    std::vector<int> vec2 = {2, 4, 6, 8};
36
37    std::vector<int> mergedVector = mergeSortedVectors(vec1, vec2);
38
39    std::cout << "Merged Vector: ";
40    for (int num : mergedVector) {
41        std::cout << num << " ";
42    }
43    
44    return 0;
45}

Let's break down the mergeSortedVectors function step by step:

Function Definition

This line defines the function mergeSortedVectors which takes two constant references to std::vector<int> and returns a std::vector<int>.

C++
Copy to clipboard
1std::vector<int> mergeSortedVectors(const std::vector<int>& vec1, const std::vector<int>& vec2)

Initialize Variables

This step initializes an empty vector mergedVector to store the merged result, and two size type variables i and j to zero. These variables will be used as pointers to traverse vec1 and vec2, respectively.

C++
Copy to clipboard
1std::vector<int> mergedVector;
2size_t i = 0, j = 0;

Traverse Both Vectors

This while loop runs as long as both i is less than the size of vec1 and j is less than the size of vec2, ensuring that both vectors are traversed.

C++
Copy to clipboard
1while (i < vec1.size() && j < vec2.size()) {

Comparison and Appending Smaller Element

Inside the loop, we compare the elements at the current positions pointed to by i and j. The smaller element is appended to mergedVector, and the corresponding pointer, either i or j, is incremented.

C++
Copy to clipboard
1if (vec1[i] < vec2[j]) {
2    mergedVector.push_back(vec1[i]);
3    i++;
4} else {
5    mergedVector.push_back(vec2[j]);
6    j++;
7}

Append Remaining Elements of vec1

After the main loop, if there are any remaining elements in vec1, this while loop appends them to mergedVector.

C++
Copy to clipboard
1while (i < vec1.size()) {
2    mergedVector.push_back(vec1[i]);
3    i++;
4}

Append Remaining Elements of vec2

Similarly, if there are any remaining elements in vec2, this while loop appends them to mergedVector.

C++
Copy to clipboard
1while (j < vec2.size()) {
2    mergedVector.push_back(vec2[j]);
3    j++;
4}

Return Merged Vector

Finally, the function returns the mergedVector which contains all the elements from vec1 and vec2 in a sorted order.

C++
Copy to clipboard
1return mergedVector;

In summary, the mergeSortedVectors function efficiently merges two given sorted vectors into a single sorted vector using the Two Pointer Technique. By leveraging the sorted property of the input vectors, this function performs the merging process in linear time complexity, O(n + m).

Grasping this lesson's subject matter is key to becoming proficient in C++ and acing your technical interviews. Following a comprehensive understanding of the basics, take time to dive into the exercises. Remember, the goal isn't just to memorize these algorithms but to learn how to dissect and tackle real-world problems using these tools. Let's proceed to practice!

In the upcoming exercises, you'll get the opportunity to apply these techniques in various scenarios to strengthen your understanding. This will include tasks like merging sorted vectors with different properties, handling edge cases, and learning to optimize your code further. Let's practice and master vector operations and algorithms!