12/18/14

Eclipse for C++ Development on Windows 7 64-bit Broken Console

It is the year 2014 and for some reason Eclipse CDT (both 32 and 64bit version) since Ganimede won’t output anything the programmer wants to print to the C++ console. The other side effect is, that it is impossible to start the gdb debugger. This problem has been posted all around the web since 2010 and yet it persists with Luna.

EmptySpace

I was able to compile the source using Eclipse, but had to switch to the Cygwin console and execute the binary manually. Doing this is a tedious process and wastes a lot of time. The bad news is, that I have found no solution for Cygwin. The good news is, that the MinGW linker will accept static gcc libraries linkage. So, for the rest of this guide, I will be assuming that you can use the MinGw GNU. Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
08/1/14

Codility ‘Distinct’ Solution

Short Problem Definition:

Compute number of distinct values in an array.

Link

Distinct

Complexity:

expected worst-case time complexity is O(N * log(N));

expected worst-case space complexity is O(N)

Execution:

Sorting in both C++ and Python takes N log N time. We know that for this particular problem sorting the array will be the dominant runtime complexity. This is the case for the second python solution. What about the other ones?

The first solution is a neat pythonic way of solving a distinct entries problem. The set is implemented as a hash table so it is possible that it will degrade to a linked list. Therefore the actual worst case would be N^2.

This is not the case with C++ (as code 3 shows). The std set is a Red-Black Tree and therefore has insertion complexity of log N. (overall N log N)

Solution:
def solution(A):
    return len(set(A))

def solution(A):
    if len(A) == 0:
        return 0

    A.sort()

    nr_values = 1
    last_value = A[0]

    for idx in xrange(1, len(A)):
        if A[idx] != last_value:
            nr_values += 1
            last_value = A[idx]

    return nr_values

#include <set>
int solution(const vector<int> &A) {
    std::set<int> theSet;

    for(int idx = 0; idx < A.size(); idx++){
        theSet.insert(A[idx]);
    }

    return theSet.size();
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
07/22/14

Codility ‘Tape Equilibrium’ Solution

Short Problem Definition:

Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|.

Link

TapeEquilibrium

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

In the first run I compute the left part up to the point i and the overall sum last. Then I compute the minimal difference between 0..i and i+1..n.

Solution:
import sys

def solution(A):
    #1st pass
    parts = [0] * len(A)
    parts[0] = A[0]
 
    for idx in xrange(1, len(A)):
        parts[idx] = A[idx] + parts[idx-1]
 
    #2nd pass
    solution = sys.maxint
    for idx in xrange(0, len(parts)-1):
        solution = min(solution,abs(parts[-1] - 2 * parts[idx]));  
 
    return solution

#include <algorithm>
#include <climits>

int solution(vector<int> &A) {
    unsigned int size = A.size();

    vector<long long> parts;
    parts.reserve(size+1);

    long long last = 0;

    for (unsigned int i=0; i<size-1; i++){
        if (i == 0){
            parts.push_back(A[i]);
        } else {
            parts.push_back(A[i]+parts[i-1]);
        }
        if (i==size-2){
            last = parts[i]+ A[i+1];
        }
    }

    long long solution = LLONG_MAX;

    for(unsigned int i=0; i<parts.size(); i++){
        solution = min(solution,abs(last - 2 * parts[i]));
    }

    return solution;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
06/5/14

Codility ‘MaxCounters’ Solution

Short Problem Definition:

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Link

MaxCounters

Complexity:

expected worst-case time complexity is O(N+M);

expected worst-case space complexity is O(N)

Execution:

The idea is to perform the specified operation as stated. It is not required to iterate over the whole array if a new value is set for all the values. Just save the value and check it when an increase on that position is performed.

Solution:
#include <algorithm>

vector<int> solution(int N, vector<int> &A) {
    vector<int> sol;
    int current_max = 0;
    int last_increase = 0;

    for(int i=0; i<N;i++){
        sol.push_back(0);
    }

    for(unsigned int i=0; i<A.size();i++){
        if (A[i] > N) {
            last_increase = current_max;
        } else {
            sol[A[i]-1] = max(sol[A[i]-1], last_increase);
            sol[A[i]-1]++;
            current_max = max(current_max, sol[A[i]-1]);
        }
    }

    for(int i=0; i<N;i++){
        sol[i] = max(sol[i], last_increase);
    }

    return sol;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
05/22/14

Codility ‘PermCheck’ Solution

Short Problem Definition:

Check whether array N is a permutation.

Link

PermCheck

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

Mark elements as seen in a boolean array. Elements seen twice or out of bounds of the size indicate that the list is no permutation. The check if the boolean array only contains true elements is not required. This solution only works with permutations starting from 1.

Solution:
def solution(A):
    seen = [False] * len(A)

    for value in A:
        if 0 <= value > len(A):
            return 0
        if seen[value-1] == True:
            return 0
        seen[value-1] = True

    return 1

int solution(vector<int> &A) {
    // the use of a auto_ptr would be better, but it does not work with arrays
    // use of boost::scoped_array seems like an overkill
    bool * seen = new bool[A.size()];
    
    for (unsigned int i=0; i< A.size(); i++){
        seen[i] = false;
    }    
    
    for (unsigned int i=0; i< A.size(); i++){
        if (!(0 < A[i] && A[i] <=A.size() && seen[A[i]-1] == false)){
            delete[] seen;
            return 0;
        } else {
            seen[A[i]-1] = true;
        }
    }
    
    delete[] seen;
    return 1;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
03/20/14

Out of Scope boost::bind

Thanks to the guys at StackOverflow I was able to come up with a clear example to demonstrate my point. The idea originated from unclear copying of member variables (in this context a function pointer) and as a result to very cryptic core dumps. It is not too uncommon that a object is no longer valid even through there are pointers still referencing it. This has been know for a long time now and the C++ standard library solves it by providing the programmer with many different types of smart pointers. And yes, other languages solve this by not exposing pointers to the developer. And as we know, the bug is usually located between the chair and the monitor, which makes this idea easy to follow.

Continue reading


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin