C++ Coding Test Course, Arrays and Lists

Coding tests are an important tool used by many companies today to evaluate job seekers. Today, we will discuss a problem centered around arrays and lists. Arrays and lists are the most basic forms of data structures and are fundamentally used in many algorithm problems. An array stores data in a fixed size of contiguous memory space, while a list can store elements in a dynamic size. Understanding the differences between these two and developing problem-solving skills using them is important.

Problem: Find the Sum of Two Numbers in an Array

Find the indices of two numbers in the given integer array that can make a specific sum. The elements of the array can be duplicated, and the two numbers must be selected from different indices.

Input Format

  • The first line contains the size of the array n (1 ≤ n ≤ 10^4).
  • The second line contains n integers of the array a[0], a[1], ..., a[n-1] (1 ≤ a[i] ≤ 10^9).
  • The third line contains the integer target that needs to be found.

Output Format

Output the indices of the two found numbers, separated by a space. If they do not exist, output -1.

Example

    Input:
    5
    2 7 11 15
    9

    Output:
    0 1

Problem-Solving Strategy

This problem is a classic example of finding the sum of two numbers in an array and can be solved through the following process:

  1. Using a HashMap:

    2. Use a HashMap to store the array elements and their indices. For each element, calculate target - current_number and check if that value is present in the HashMap. If it exists, return that index and the current index. This approach has an average time complexity of O(n).

C++ Code Implementation


#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

vector twoSum(vector& nums, int target) {
    unordered_map hashMap; // Declaring HashMap
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i]; // Finding needed number
        if (hashMap.find(complement) != hashMap.end()) {
            return {hashMap[complement], i}; // Returning indices
        }
        hashMap[nums[i]] = i; // Storing number and its index
    }
    return {-1}; // If not found
}

int main() {
    int n, target;
    cin >> n;
    vector nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i]; // Input array
    }
    cin >> target; // Input target

    vector result = twoSum(nums, target);
    for (int idx : result) {
        cout << idx << " "; // Output result
    }
    return 0;
}

Code Explanation

The above code works by taking the given array and target value as input and finding the indices of two numbers. By using unordered_map to store each number and its index, it can be solved while traversing the array only once. This ensures a time complexity of O(n) even in the worst case.

Result Verification

To verify that the written code works correctly, we will prepare various test cases. For example:

  • n=5, input array: [2, 7, 11, 15], target: 9 → result: 0 1
  • n=4, input array: [3, 2, 4], target: 6 → result: 1 2
  • n=3, input array: [3, 3], target: 6 → result: 0 1
  • n=2, input array: [1, 2], target: 3 → result: 0 1
  • n=1, input array: [2], target: 2 → result: -1 (no element exists)

Conclusion

Today, we covered a coding test problem using arrays and lists. The problem of finding the sum of two numbers is not a difficult one, but it is worth practicing given the various approaches available. Using HashMaps is a good example of efficiently reducing time complexity. In the next lesson, we will cover other data structures or algorithm approaches. Keep practicing coding!