Welcome all!
I'm Oleg. Specialization: C ++ / C / OS kernels / drivers / hardware / networks / embedded. I have been living and working abroad for about a year and a half. Now in Finland, before that there was Poland. They told me about the peculiarities of moving to both countries before me, who is interested - write, I will answer your questions. A lot has also been written about life in these countries. But someday I will present my impressions of both in the form of a free essay.
Now I want to talk about a problem that I spent half a day solving, although it was not worth it. And the funny thing is that I solved some similar problems in interviews. I ran into her while digging one of my home projects.
So, given a certain number of sets of integers of different sizes. You need to find the numbers that are in all the sets except one. The index of the set where the element is missing is also required.
Suppose there are sets {1, 2, 3}, {3, 0, 4}, {5}. In this artificial example, the element {3}, which is present in the zero and first sets and is absent in the second, claims to be a find. It can also be written as a set {3, 2}. Literally, this record is deciphered as follows: the value 3 is absent in the set 2. One more condition: only positive integers from 1 to 64 participate. The elements of each set are unique.
Fundamentally, this is a kind of generalization of the classic interview problem. The latter is formulated as follows: numbers are received at the input of a certain block of the program, it is necessary to cut off duplicates. It can be solved in an elementary way using the STL unordered_set primitive. It is good because it has O (1) - constant search time for short number sequences. Within the framework of a limited task, it is quite pleasant to itself in taste and color. Besides, when adding a duplicate to it, it simply won't add it. It is also not necessary to check the return value in that case. That is, we have a saving of three lines of code, which are anyway contained in the implementation of the template. But, since the range of numbers in my project is limited, you can do without it at all. Yes, if you expand the range of numbers, then unordered_set, or something like that, you have to use.
For simplicity, let's set the number of sets equal to 3. The set is stored in a vector, or STL template vector <vector>. The result is a set of pairs of non-negative numbers vector <pair <int, int>>. In a pair, in the first place is the element itself, in the second is the index of the set where it is not.
void PrepareData(const vector<vector<int> >& src, vector<pair<int, int> >& res)
{
vector<pair<int, int> > data(MAX); //
for(unsigned i(0); i < src.size(); ++i)
{
const auto& rf(src[i]);
for(unsigned j(0); j < rf.size(); ++j)
{
ASSERT(((0 < rf[j]) && (MAX > rf[j])) && "!!! An invalid data !!!");
++data[rf[j]].first; //
data[rf[j]].second += i; //
}
}
auto fs(((src.size() - 1) * src.size()) >> 1); //
for(unsigned i(0); i < data.size(); ++i) //
{
if(data[i].first == src.size() - 1) //
{
pair<int, int> cur{i, 0}; //
cur.second = fs - data[i].second; // ,
res.push_back(cur);
}
}
}1)
2) . . , .
3) data . , , ,
4) , (a[1] + a[n]) * n / 2
5) , ,
6) , ,
That's all, half a day of torment. The code does not pretend to be beautiful. The desire was only to present an idea, or an approach to solving such problems. Special thanks to Ilyawataru, who recommended that I pay attention to the optimality of my algorithms.
Link to code https://yadi.sk/d/F2dLt6v_uvjKdQ