Bloomberg Interview Questions/Q 2

From Software Engineers Wiki
Jump to: navigation, search

Given an array A = [3, 7, 2,5,6,4] for a number N, print the pairs from that array A that sums up to N. You should print each pair once.

Contents

Answer #1

The brute-force algorithm is to try every combination out of the array.

void print_find_pair(std::vector<int> &rvec, int N)
{
        std::vector<int>::iterator ir1, ir2;

        for (ir1 = rvec.begin(); ; ++ir1) {
                ir2 = ir1;
                ++ir2;
                if (ir2 == rvec.end())
                        break;

                while (ir2 != rvec.end()) {
                        if (*ir1 + *ir2 == N)
                                std::cout << *ir1 << " " << *ir2 << std::endl;
                        ++ir2;
                }
        }
}

Test program:

int main(void)
{
        std::vector<int> vec { 3, 7, 2, 5, 6, 4 };

        std::cout << "Find pair for 7\n";
        print_find_pair(vec, 7);

        std::cout << "Find pair for 9\n";
        print_find_pair(vec, 9);

Test result:

Find pair for 7
3 4
2 5
Find pair for 9
3 6
7 2
5 4

Answer #2

First solution has complexity of O(N^2). If the numbers are sorted, we can find the pair faster.

First, sorting.

std::sort(vec.begin(), vec.end(), std::less<int>());

which is equivalent to

std::sort(vec.begin(), vec.end(), [](int a, int b) -> bool { return a < b; });

Then finding pair. We don't have to look at every element. Since the array is sorted and all the elements are unique, we just have to look at until N/2. After this, sum of any pair will be greater than N.

void print_find_pair(std::vector<int> &rvec, int N)
{
        std::vector<int>::iterator ir, ir_next;
        int find_value;

        for (ir = rvec.begin(); ir != rvec.end(); ++ir) {
                if (*ir > (N / 2))
                        break;

                find_value = N - *ir;

                ir_next = ir;
                ++ir_next;

                while (ir_next != rvec.end()) {
                        if (*ir_next == find_value)
                                std::cout << *ir << " " << *ir_next << std::endl;
                        else if (*ir_next > find_value)
                                break;
                        ++ir_next;
                }
        }
}

The test result is same.

Find pair for 7
2 5
3 4
Find pair for 9
2 7
3 6
4 5

Answer #3

Since the array is sorted, it doesn't have to scan the array linearly. We can make use of binary search algorithm.

void print_find_pair(std::vector<int> &rvec, int N)
{
        std::vector<int>::iterator ir, ir_next, ir_find;
        int find_value;

        for (ir = rvec.begin(); ir != rvec.end(); ++ir) {
                if (*ir > (N / 2))
                        break;

                find_value = N - *ir;
                ir_next = ir;
                ++ir_next;

                if (std::binary_search(ir_next, rvec.end(), find_value))
                        std::cout << *ir << " " << find_value << std::endl;
        }
}

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox