C++ tasks from Yandex

Task 1

At an interview I was asked how to by a given vector of integers build resulting vector containing the products of all the elements except current. Below I provided my solution in C++:

#include <vector>
#include <iostream>

using V = std::vector<int>;

V func(const V& v)
{
    V result;
    result.resize(v.size());

    int product = 1;

    for (size_t pos = 0; pos != v.size(); ++pos)
    {
        result[pos] = product;

        int a = v[pos];
        product *= a;
    }
    int reverse_product = v.back();
    for (size_t reverse_pos = 1; reverse_pos < v.size(); ++reverse_pos)
    {
        const size_t pos = v.size() - reverse_pos - 1;
        result[pos] *= reverse_product;

        int a = v[pos];
        reverse_product *= a;
    }

    return result;
}

V v = {1, 2, 3, 10};

int main()
{
    auto v1 = func(v);
    
    for (auto a: v1)
    {
        std::cout << a << ", ";
    }
}

The output is:

60, 30, 20, 6,

Task 2

By given words construct a vector containing the anagrams, for example:

["eat", "def", "tea", "abc", "ate", "cab"] ->
[["eat", "tea", "ate"], ["def"], ["abc", "cab"]]
#include <string>
#include <vector>
#include <map>

using InputV = std::vector<std::string>;
using M = std::unordered_map<std::string, std::vector<std::string>>;
using OutputV = std::vector<std::vector<std::string>>;

OutputV anagramm(const InputV& in)
{
    M m;
    
    for (const std::string& s : in)
    {
        const std::string sorted = s;
        
        std::sort(sorted.begin(), sorted.end());
        
        auto i = m.find(sorted); //O(1)
        
        if (i != m.end())
        {
            std::vector<std::string> & val = i->second;
            
            val.push_back(s); //O(1)
        }
        else
        {
            std::vector<std::string> val { s };
            
            m.emplace(sorted, val); //O(1)
        }
    }
    
    OutputV v;
    
    for (auto & [key, val] : m)
    {
        v.push_back(val);
    }
    
    return v;
}

Task 3

Find the length of the longest substring containing unique symbols, for example:

abcabcbbddee -> 3 (abc)
bbbbb -> 1 (b)
pwwkew -> 3 (wke)
ababab -> 2 (ab)
bba -> 2
abba -> 2 
using M = unordered_map<char, size_t>;

std::string in;

size_t begin = 0;
size_t len = 0;
size_t max_len = 0;

for (auto i = in.begin(); ++i; i != in.end())
{
    const size_t pos = static_cast<size_t>(i - in.begin());

    const char symbol = *i;
    
    auto map_i = m.find(symbol);
    
    bool duplicate_found = false;
    
    if (map_i != m.end())
    {
        const size_t prev_pos = i->second;

        if (pos - prev_pos < len)
        {
            duplicate_found = true;
        }
    }
    
    if (!duplicate_found)
    {
        ++len;
    }
    else
    {
        const size_t prev_pos = i->second;
        
        begin = prev_pos + 1;

        if (max_len < len)
        {
            max_len = len;
        }

        len = pos - begin;

        m.erase(map_i);
    }

    m.emplace(symbol, pos);
}

Task 4

Remove smiles like this:

:-))))
:-((
:-)
:-(

from a given text.

enum class State
{
    None,
    Prefix,
    Brace
}

std::size_t eat_smile(const std::string & in, std::size_t pos)
{
    const std::string prefix = ":-";
    State state = State::None;
    bool open_brace;
    size_t brace_count;
    
    size_t end_pos = pos;
    
    for (; end_pos != in.length(); ++end_pos)
    {
        char ch = in[end_pos];
        
        switch (state)
        {
            case State::None:
                if (ch == prefix[0])
                {
                    state = State::Prefix;
                }
            break;

            case State::Prefix:
                if (ch == prefix[1])
                {
                    state = State::Brace;
                    brace_count = 0;
                }
                else
                {
                    return end_pos;
                }
                break;
            
            case State::Brace:
                {
                    const bool open = ch == ')';
                    const bool close = ch == '(';
                    
                    if (open || close)
                    {
                        if (brace_count == 0)
                        {
                            open_brace = open;
                            ++brace_count;
                        }
                    }
                    else
                    {
                        if (open_brace == open)
                        {
                            ++brace_count;
                        }
                        else
                        {
                            return end_pos;
                        }
                    }
                    
                    break;
                }
        }

        return end_pos;
    }
}

std::string remove_smiles(const std::string & in)
{
    std::ostringstream out;
    
    for (size_t pos = 0; pos != in.length();)
    {
        const end_pos = eat_smile(in, pos);
        
        const size_t len = end_pos - pos;
        
        if (len >= 3)
        {
            pos = end_pos;
        }
        else
        {
            out << in[pos];
        }
    }
}

Leave a Reply

Your email address will not be published.