KDAB Challenge Solutions Answers to KDAB’s 20 Years Developer Challenge
13.01.2020
Task 1
Proxy types can be tricky. If we got a QChar (or a reference to a QChar) by accessing a character in a QString with the operator[] as most people would expect to, the automatic type deduction requested by auto current = hello[i] would deduce that current is of type QChar.
But QString::operator[] does not return a QChar. It returns a QCharRef. Even if we think of it as a reference to a QChar, the compiler does not, and the automatic type deduction can not remove the reference part like it would if the return type was a proper reference (QChar&).
This means that current will be a value of type QCharRef. When we modify it, it will modify the original string (contrary to what most people expect because of C++’s value semantics).
One of the solutions here is not to use automatic type deduction and explicitly specify the type of current to be QChar.
QChar current = hello[i];Another thing that could help is to declare the hello string to be const. It is a good practise to use const by default when declaring variables.
The second issue in the first task was that the original string ends with an exclamation mark, while the string in the Q_ASSERT does not.
Task 2
The problem in the second task is similar to the previous one. When we see strings being concatenated, we assume that the result is also a string.
String concatenation is slow (you can check out this post for more info) and Qt allows us to activate delayed (lazy) concatenation by defining QT_USE_QSTRINGBUILDER. Instead of operator+ returning a string, it will return a class called QStringBuilder which will keep references to all strings we want to concatenate and perform the concatenation only when we convert it to a QString.
This means that when we use the automatic type deduction – auto message = ... – we get a message variable that is not a string, but rather an object that keeps references to all the strings we want to concatenate. When we try to print it out with qDebug, it will concatenate all the strings and print out the result.
The problem is that one of the references in our example will be a dangling reference – reference to a temporary string returned by the tr function that has been destroyed before the actual concatenation is performed. So, we get undefined behavior (most likely a crash in this case).
This is easily fixed by explicitly specifying the type of message to be a QString. This will perform the concatenation before the temporary string returned by the tr function is destroyed.
Task 3
The final task is quite different to the previous ones. It shows a function implemented with two for loops nested into each other. The time complexity of the function is O(m*n) where m is the length of xs and n is the length of ys. The memory complexity is O(1).
If we analyze the function, we can deduce that it counts all the items in xs that are smaller than or equal to the smallest value in ys. While the provided example uses sorted vectors, it is obvious that this function also works for unsorted vectors.
One approach (a frequently submitted one) to solving this using the algorithms found in the standard library is to sort both collections and then use the lower_bound to find the first element in (now sorted) xs that is not smaller than the smallest element in ys (ys[0] after sorting). We can then use std::distance to get the count how many elements we have between xs.cbegin() and the item we just found.
The time complexity of this solution is O(n log n + m log m) which is better than the original implementation, but the memory complexity grew to O(m + n) because we need to copy the original vectors in order to sort them, which is significantly worse.
If we go a bit deeper, we can see that we are using just ys[0] so we don’t really need to have the whole vector sorted. We just need the smallest value in ys. We can find this in linear time with the std::min_element algorithm.
With this, we would end up with O(m log m + n) time complexity and O(m) memory complexity, as we are still sorting the xs. Better, but not good enough.
Now the question is whether we really need to sort the xs?
If we know the minimum of ys we need to compare xs against, it is much cheaper just to go through all the unsorted xs one by one and check which ones are smaller than to sort the xs first. This can easily be done with std::count_if:
int counting(const std::vector<int>& xs, const std::vector<int>& ys)
{
if (ys.empty()) return xs.size();
const int min_y = *std::min_element(ys.begin(), ys.end());
return std::count_if(xs.begin(), xs.end(), [=] (int x) {
return x <= min_y;
});
}The time complexity of this solution is O(m + n) and the memory complexity is O(1) which is the best we can do for this problem.
