C++ Solutions to "Five programming problems every Software Engineer should be able to solve in less than 1 hour". (https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour)

prob1.cpp

// Problem 1
// Write three functions that compute the sum of the numbers in a given list using a for-loop, a while-loop, and recursion.

#include <iostream>
#include <vector>

int recursiveSummation(std::vector<int> v)
{
    if(v.size() == 0)
    { return 0; }

    int lastElem = v.back();
    v.pop_back();
    return lastElem + recursiveSummation(v);
}

int forSummation(std::vector<int> v)
{
    int sum= 0;
    for(auto i : v)
    {
        sum += i;
    }
    return sum;
}

int whileSummation(std::vector<int> v)
{
    int sum= 0;
    auto vecIt = v.begin();
    while(vecIt != v.end())
    {
        sum += *vecIt;
        vecIt++;
    }
    return sum;
}
int main()
{
    srand(time(NULL));

    std::vector<int> input;
    std::cout<<"input : [";
    for(int i=0; i < 10; ++i)
    { 
        int curInput = rand() % 100;
        input.push_back(curInput); 
        std::cout<<curInput<<", ";
    }
    std::cout<<"]"<<std::endl;

    std::cout<<"Using a For Loop: " << forSummation(input) << std::endl;;
    std::cout<<"Using a While Loop: " << whileSummation(input) << std::endl;
    std::cout<<"Using Recursion : " << recursiveSummation(input) << std::endl;

    return 0;
}

prob2.cpp

// Problem 2
// Write a function that combines two lists by alternatingly taking elements. For example: given the two lists [a, b, c] and [1, 2, 3], the function should return [a, 1, b, 2, c, 3].

#include <iostream>
#include <vector>

std::vector<int> mergeVector(std::vector<int> & v1, std::vector<int> & v2)
{
    std::vector<int> result;
    int longerLength = std::max(v1.size(), v2.size()); 
    for(int i = 0; i < longerLength; ++i)
    {
        if(i < v1.size())
        { result.push_back(v1[i]); }
        if( i< v2.size())
        { result.push_back(v2[i]); }
    }
    return result;
}

int main()
{
    std::vector<int> input1 = {1, 2, 3, 4, 5};
    std::vector<int> input2 = {6, 7, 8, 9, 10, 11, 12};
    std::cout<<"input1 : [";
    for(auto it: input1)
    {
        std::cout<<it<<", ";
    }
    std::cout<<"]"<<std::endl;

    std::cout<<"input2 : [";
    for(auto it: input2)
    {
        std::cout<<it<<", ";
    }
    std::cout<<"]"<<std::endl;

    std::vector<int> result = mergeVector(input1, input2);
    for(auto &it : result)
    { std::cout<<it<<" "; }
    std::cout<<std::endl;
}

prob3.cpp

// Problem 3
// Write a function that computes the list of the first 100 Fibonacci numbers. By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. As an example, here are the first 10 Fibonnaci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34.

#include <iostream>
#include <unordered_map>

std::unordered_map<int, unsigned long long> fibonacci_map;

unsigned long long fibonacci(int i)
{
    auto searchResult = fibonacci_map.find(i);
    if(searchResult == fibonacci_map.end())
    {
        if(i == 0) { fibonacci_map.insert(std::make_pair(0, 0));}
        else if(i == 1) { fibonacci_map.insert(std::make_pair(1, 1));}
        else 
        { fibonacci_map.insert(std::make_pair(i, fibonacci(i-1) + fibonacci(i-2))); }
    }
    searchResult = fibonacci_map.find(i);
    return searchResult->second;
}

int main()
{
    //the 95th fibonacci number cause overflow, thus cannot be represented as a basic data type.
    
    for(int i=0; i < 94 ; ++i)
    {
        std::cout<<i+1<<" : "<<fibonacci(i)<<std::endl;
    }
}

prob4.cpp

// Problem 4
// Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

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

struct stringGreater
{
    bool operator()(int a, int b)
    {   
        std::string strA = std::to_string(a);
        std::string strB = std::to_string(b);
        return strA + strB > strB + strA;
    }   
};

void findTheLargestPossible(std::vector<int> input)
{
    std::string resultStr;
    std::sort(input.begin(), input.end(), stringGreater());

    for(auto &num : input)
    {
        resultStr += std::to_string(num);
    }
    std::cout<<resultStr<<std::endl;
}

int main()
{
    std::vector<int> input;
    input.reserve(10);
    std::cout<<"input: [";
    for(int i=0; i<10; ++i)
    {
        int curInput =  rand() % 1000;
        std::cout<<curInput<<", ";
        input.push_back(curInput);
    }
    std::cout<<"]"<<std::endl;
    findTheLargestPossible(input);
    return 0;
}

prob5.cpp

// Problem 5
// Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

#include <iostream>
#include <vector>

std::vector<std::string> findCombinations(std::vector<int> srcList, int dest)
{
    std::vector<std::string> result;
    int sz = srcList.size();
    if(sz == 0)
    { return result; }
    
    std::string curAll;
    for(auto i : srcList)
    { curAll += std::to_string(i); }

    if(std::stoi(curAll) == dest)
    {
        result.push_back(curAll);
        return result;
    }

    int acc = 0;
    std::vector<int> newSrcList(srcList);

    int lastElemDigit = 1;
    while(newSrcList.size() != 0)
    {
        int lastElem = newSrcList.back();
        newSrcList.pop_back();
        acc = lastElem * lastElemDigit + acc;
        lastElemDigit *= 10;

        int newDest = dest - acc;
        std::vector<std::string> subResultAdd = findCombinations(newSrcList, newDest);
        std::string appender = std::string(" + " + std::to_string(acc));
        for(auto &it: subResultAdd) { it.append(appender); }

        newDest = dest + acc;
        std::vector<std::string> subResultSub = findCombinations(newSrcList, newDest);
        appender = std::string(" - "+std::to_string(acc));
        for(auto &it: subResultSub ) { it.append(appender); }

        result.reserve(subResultAdd.size() + subResultSub.size());
        result.insert(result.end(), subResultAdd.begin(), subResultAdd.end());
        result.insert(result.end(), subResultSub.begin(), subResultSub.end());
    }
    return result;
}

int main()
{
    std::vector<int> input ;
    for(int i=1; i<=9; ++i)
    {
        input.push_back(i);
    }
    std::vector<std::string> result = findCombinations(input, 100);
    for(auto & it : result)
    {
        std::cout<<it<<std::endl;
    }
    return 0;
}