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];
}
}
}
