Master theorem

Analysing complexity of recursive functions is not always easy, especially when the function does something fancy. Luckily, clever brains have provided a cookbook that makes determining the complexity of a recursive algorithm quite easy.

We may consider a recursive function as:
R(N) = A * R(\frac{N}{B}) + O(N^C)
Let me explain the symbols. R is a recursive function, that is called on the problem of size N. As it’s recursive, it calls itself A times, for a smaller problem of size N/B. In many recursive implementation, especially divide and conquer techniques, we got a “merge” step (please think about mergesort). The complexity of the merge step is expressed as the last term of the above formula.

Then we may determine three cases that will describe the complexity of the call.
1. A = B^C then O(R(N)) = N ^ C log N
2. A < B^C then O(R(N)) = N ^ C
3. A > B^C then O(R(N)) = N ^ {log _b{c}}

Do you remember mergesort? Mergesort has two recursive calls, that divide the problem into two pieces. When the recursion is done, then comes an extra “merge” step, that has O(N) complexity. If we plug this information into the formula we got: A = 2, B = 2, C = 1. What leads to 2 = 2 ^ 1. We take the first case, and obtain complexity of O(N) = N log N.

Find the k-closest elements to a given value in a sorted array

We are given a sorted array, value V, and a number K. The value represents the number that may appear in the array, but it’s not mandatory. We are expected to find a set of size K, that contains the elements from the array, that are the closest to the value .

The solution uses the famous binary search algorithm. Firstly we find the value V itself, or the closest to V, in the array. The latter, we obtain just as a result of a regular binary search, that returns the position of the element if it exists, or the position where it would appear. Let’s call this position P. We know that the element at position P, will be included in the result set. Now we need to consider the elements on the left and the right hand side of P. As the array is sorted, the closest element to the one on the position P, will lay on the position P-1, or P+1. We choose the one that is closer, and iteratively process till we fill the set to the expected size. An example code:

unsigned int binary_search(vector<int> array, int el){
 unsigned int begin = 0;
 unsigned int end = array.size() - 1;
 unsigned int medium;
 while(begin < end){
  medium = begin + (end - begin)/2;
  if(array < el)begin = medium + 1;
  else end = medium;
 }
 return medium;
}

vector<int> get_k_closest(vector<int> array, int el, unsigned int k){
 unsigned int split = binary_search(array, el);
 int l = split, r = split + 1;
 unsigned int counter = k;
 vector<int> result;
 while(counter){
  if(l >= 0 && r < array.size()){
   // choose the element that is closer
   if(abs(array[l] - el) < abs(array[r] - el))
    result.push_back(array[l--]);
   else result.push_back(array[r++]);
  } else {
   if(l >= 0)
    result.push_back(array[l--]);
   else if(r < array.size())
    result.push_back(array[r++]);
  }
  counter--;
 }
 return result;
}

Reservoir Sampling

There is a huge set S of numbers of size N that can’t fit in the memory. Choose K of elements from the stream randomly, with equal probability of being selected.

Without to much introduction, let’s just say that the answer to the problem is Reservoir Sampling. An example code could look like:

std::vector<int> reservoir_sampling(Stream S; unsigned long long N, unsigned int K){
 unsigned long long i = 0;
 std::vector<int> reservoir;
 
 // fill the reservoir
 for(; i < K; ++i)
  reservoir.push_back(S.next());

 // replace if needed
 for(; i < N; ++i){
  int next_token = S.next();
  unsigned int r = rand() % i;
  if(r < K)reservoir[i] = next_token;
 }
 return reservoir;
}

Find the number of set bits in the result of multiplication of big numbers

You are given a number that might be so big that it doesn’t fit in any standard type, however the number is provided in a form of [a, b, c, d, …] where every letter stands for the bit number that is set in the byte representation, so you can read it easily. In example [1, 3, 4] represents 1101 = 13. Then you multiply the number by 3. How many bits are set to 1 in the binary representation of the result?

This is a real interview question that has been asked to a friend of mine quite recently. To figure out the solution, we need to firstly consider what the multiplication by 3 really means. Let’s take an example.

 01101
x00011
--------
 01101
+11010
--------
0100111

As you can see the result is the sum of the number itself and the number shifted to left by 1. The former is obvious, as it is the result of multiplying by 1. The latter is what multiplication by 2 does. Multiplication by 2^n shifts the byte left by n positions in a general case.

Coming back to our result we get [1, 3, 4] x 3 = [1, 3, 4] << 1 + [1, 3, 4] = [2, 4, 5] + [1, 3, 4]. Now we may answer the question: what bytes will be set after this addition? Recalling the binary arithmetic and we may notice that the solution lays in calculating the result of the addition of the. In simpler words we just need to implement binary addition of numbers represented in the form of [2,4,5] and [1,3,4]. The answer will be the size of the result structure.

int getNumberOfSetBits(vector<int> number)
{
        // calculate the number shifted by 2
        vector<int> shifted = number;
        for(unsigned int i = 0; i < number.size(); i++)
                shifted[i]++;

        bool carry = false;
        vector<int> result;

        // the first element of number will surely be a part of the result
        result.push_back(number[0]);

        // start the addition 
        for(unsigned int i = 1; i < number.size(); i++)
        {
                if(number[i] == shifted[i-1])
                {
                        if(carry)
                        {
                                result.push_back(number[i]);
                        }
                        carry = true;
                }
                else
                {
                        result.push_back(number[i]);
                        result.push_back(shifted[i-1]);
                        carry = false;
                }
        }

        // do not forget the carry the last one from shifted
        int last = shifted.size() - 1;
        if(carry)
                result.push_back(shifted[last] + 1);
        else result.push_back(shifted[last]);

        return result.size(); 
}

The code could be optimized as actually the structure result is not necessary. But it keeps more visible what was the idea behind the algorithm.

Regards

Joe Kidd

Remove elements from std::vector

The title of the post would suggest an answer that is just obvious and discourage you from reading it. Unfortunately I meet very often production code, that removes elements from a vector according to a certain predicate, that is written in a horrible way.

Problem definition

The problem starts with a vector of certain objects, for simplicity let us assume we are considering integers. Then we are given a predicate saying that we would like to clean the vector from the values meeting certain condition. In our case we could remove all even numbers, or prime numbers, or numbers with the sum of digits equal 9, or whatever your imagination brings. In the real world the problem could be more sophisticated and we could remove all the connections that were disconnected and there is no reason to maintain them further.

How it usually looks like

What programmers usually do, they iterate over the collection and check every element if it meets a certain condition. If no, the element should be removed. This way of thinking is not bad, however when it comes to implementation, the things usually go wrong. Here is what most of the developers I know usually do:

for(auto i = v.begin(); i != v.end(): i++)
{
   if(predicate(*i))
   {
      i = v.erase(i);
   }
}

Now, you could ask what is wrong with this code. I would answer with another question: what is the complexity? At first glance it might look like it is O(n), but when you think what erase actually does, it appears that it is actually O(n^2). The erase operation is O(n) costly as it has to rearrange the vector after removing elements. We are even informed about this, when we take a more careful look at the standard:

Because vectors use an array as their underlying storage, erasing elements in positions other than the vector end causes the container to relocate all the elements after the segment erased to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

To give you some intuition about what happens, let us imagine the vector that looks like following

[ 5 | 4 | 7 | 8 | 1 | 3 | 6 ] 

We want to remove the element 8. When this happens, all the elements on the right hand from 8 has to be shifted left.

[ 5 | 4 | 7 | x | 1 | 3 | 6 ] 
[ 5 | 4 | 7 | 1 | x | 3 | 6 ] 
[ 5 | 4 | 7 | 1 | 3 | x | 6 ] 
[ 5 | 4 | 7 | 1 | 3 | 6] 

What is O(n) operation. Considering the outer loop we fall into O(n^2) complexity, that is not acceptable as long as we may get something better and in this case we can.

How it should look like

The STL library provides you a set of algorithms that make the operations on the containers easier. One of them is the remove_if operation, that accepts two iterators which indicate the range that should be considered, and the mentioned predicate. The remove_if approach is way more clever than the loop/erase one. L What the specification says about remove_if is:

The removal is done by replacing the elements for which pred returns true by the next element for which it does not, and signaling the new size of the shortened range by returning an iterator to the element that should be considered its new past-the-end element.

To clarify it even more, let us take a look at the example. Let us consider the vector from the previous example and see how remove_if would work when the predicate is “remove if the number is divisible by 4”.

[ 5 | 4 | 7 | 8 | 1 | 3 | 6 ] 
[ 5 | 7 | 1 | 3 | 6 | 4 | 8 ] 
-------------------- xxxxxxxx
       good            bad

As we can see the elements that meet the predicate have been moved to the end of the array. Secondly the remove_if returns the iterator indicating the position after “the last good element” (6 in this case), that we may use to remove the range of “bad elements”. Before we will do it, it is worth to mention that the order of “good elements” is maintained, but it is not necessary the case for “bad elements”.

Finally we could get a code that looks like follows:

v.erase(
   remove_if(v.begin(), v.end(), [](const int & in){return i % 4 == 0;}),
   v.end());

Yes, we still use the erase method, but this time we are removing from the end of the vector so there is no necessity of rearrangement the elements and the erase operation is O(1). In this case the complexity would be O(n), what is quite satisfactory in comparison to O(n^2).

Summary

I think that this article clearly shows how important it is, to understand well the mechanism behind Standard Template Library. It is a really powerful tool and knowing how to use it properly makes your life way easier and your programs way faster.