08/6/14

Codility ‘MaxProductOfThree’ Solution

Short Problem Definition:

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

Link

MaxProductOfThree

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

After sorting the largest product can be found as a combination of the last three elements. Additionally, two negative numbers add to a positive, so by multiplying the two largest negatives with the largest positive, we get another candidate. If all numbers are negative, the three largest (closest to 0) still get the largest element!

Solution:
def solution(A):
    if len(A) < 3:
        raise Exception("Invalid input")
        
    A.sort()
    
    return max(A[0] * A[1] * A[-1], A[-1] * A[-2] * A[-3])

A better solution has been suggested in the commends by

def betterSolution(A):
    if len(A) < 3:
        raise Exception("Invalid input")
        
    minH = []
    maxH = []
    
    for val in A:
        if len(minH) < 2:
            heapq.heappush(minH, -val)
        else:
            heapq.heappushpop(minH, -val)
            
        if len(maxH) < 3:
            heapq.heappush(maxH, val)
        else:
            heapq.heappushpop(maxH, val)
    
    
    max_val = heapq.heappop(maxH) * heapq.heappop(maxH)
    top_ele = heapq.heappop(maxH)
    max_val *= top_ele
    min_val = -heapq.heappop(minH) * -heapq.heappop(minH) * top_ele
    
    return max(max_val, min_val)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/5/14

Codility ‘GenomicRangeQuery’ Solution

Short Problem Definition:

Find the minimal nucleotide from a range of sequence DNA.

Link

GenomicRangeQuery

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Remember the last position on which was the genome (A, C, G, T) was seen. If the distance between Q and P is lower than the distance to the last seen genome, we have found the right candidate.

Solution:
def writeCharToList(S, last_seen, c, idx):
    if S[idx] == c:
        last_seen[idx] = idx
    elif idx > 0:
        last_seen[idx] = last_seen[idx -1]

def solution(S, P, Q):
    
    if len(P) != len(Q):
        raise Exception("Invalid input")
    
    last_seen_A = [-1] * len(S)
    last_seen_C = [-1] * len(S)
    last_seen_G = [-1] * len(S)
    last_seen_T = [-1] * len(S)
        
    for idx in xrange(len(S)):
        writeCharToList(S, last_seen_A, 'A', idx)
        writeCharToList(S, last_seen_C, 'C', idx)
        writeCharToList(S, last_seen_G, 'G', idx)
        writeCharToList(S, last_seen_T, 'T', idx)
    
    
    solution = [0] * len(Q)
    
    for idx in xrange(len(Q)):
        if last_seen_A[Q[idx]] >= P[idx]:
            solution[idx] = 1
        elif last_seen_C[Q[idx]] >= P[idx]:
            solution[idx] = 2
        elif last_seen_G[Q[idx]] >= P[idx]:
            solution[idx] = 3
        elif last_seen_T[Q[idx]] >= P[idx]:
            solution[idx] = 4
        else:    
            raise Exception("Should never happen")
        
    return solution
    

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/4/14

Codility ‘CountDiv’ Solution

Short Problem Definition:

Compute number of integers divisible by k in range [a..b].

Link

CountDiv

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

This little check required a bit of experimentation. One needs to start from the first valid value that is bigger than A and a multiply of K.

Solution:
def solution(A, B, K):
    if B < A or K <= 0:
        raise Exception("Invalid Input")

    min_value =  ((A + K -1) // K) * K

    if min_value > B:
      return 0

    return ((B - min_value) // K) + 1

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/3/14

Codility ‘CountSemiprimes’ Solution

Short Problem Definition:

Count the semiprime numbers in the given range [a..b]

Link

SemiPrimes

Complexity:

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

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

Execution:

First get all semiprimes from an adaptation of the Sieve of Eratosthenes. Because we will be computing the difference many times a prefix sum is adequate. Get the number of semiprimes up to the point. The index P is decreased by 1 because we want to know all primes that start from P.

Solution:
def sieve(N):
    semi = set()
    sieve = [True]* (N+1)
    sieve[0] = sieve[1] = False

    i = 2
    while (i*i <= N):
        if sieve[i] == True:
            for j in xrange(i*i, N+1, i):
                sieve[j] = False
        i += 1

    i = 2
    while (i*i <= N):
        if sieve[i] == True:
            for j in xrange(i*i, N+1, i):
                if (j % i == 0 and sieve[j/i] == True):
                    semi.add(j)
        i += 1

    return semi

def solution(N, P, Q):

    semi_set = sieve(N)

    prefix = []

    prefix.append(0) # 0
    prefix.append(0) # 1
    prefix.append(0) # 2
    prefix.append(0) # 3
    prefix.append(1) # 4

    for idx in xrange(5, max(Q)+1):
        if idx in semi_set:
            prefix.append(prefix[-1]+1)
        else:
            prefix.append(prefix[-1])

    solution = []

    for idx in xrange(len(Q)):
        solution.append(prefix[Q[idx]] - prefix[P[idx]-1])

    return solution

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/2/14

Codility ‘BinaryGap’ Solution

Short Problem Definition:

Find longest sequence of zeros in binary representation of an integer.

Link

BinaryGap

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

The solution is straight-forward! Use of binary shift.

Solution:
def solution(N):
    cnt = 0
    result = 0
    found_one = False

    i = N    
        
    while i:
        if i & 1 == 1:
            if (found_one == False):
                found_one = True
            else:
                result = max(result,cnt)
            cnt = 0
        else:
            cnt += 1
        i >>= 1
   
    return result

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
08/1/14

Codility ‘MaxProfit’ Solution

Short Problem Definition:

Given a log of stock prices compute the maximum possible earning.

Link

MaxProfit

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

Keep the minimal value up to day. The profit on day i is profit[i] – min_profit.

Solution:
def solution(A):
    max_profit = 0
    max_day = 0
    min_day = 200000
    
    for day in A:
        min_day = min(min_day, day)
        max_profit = max(max_profit, day-min_day)
    
    return max_profit

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

Facebooktwittergoogle_plusredditpinterestlinkedin