07/31/14

Codility ‘Peaks’ Solution

Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. A peak is an array element which is larger than its neighbors.

Link

Peaks

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

I first compute all peaks. Because each block must contain a peak I start from the end and try to find a integral divisor sized block. If each block contains a peak I return the size.

Solution:


def solution(A):
    peaks = []

    for idx in xrange(1, len(A)-1):
        if A[idx-1] < A[idx] > A[idx+1]:
            peaks.append(idx)

    if len(peaks) == 0:
        return 0

    for size in xrange(len(peaks), 0, -1):
        if len(A) % size == 0:
            block_size = len(A) // size
            found = [False] * size
            found_cnt = 0
            for peak in peaks:
                block_nr = peak//block_size
                if found[block_nr] == False:
                    found[block_nr] = True
                    found_cnt += 1

            if found_cnt == size:
                return size

    return 0

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

07/29/14

Codility ‘MinPerimeterRectangle’ Solution

Short Problem Definition:

Find the minimal perimeter of any rectangle whose area equals N.

Link

MinPerimeterRectangle

Complexity:

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

expected worst-case space complexity is O(1).

Execution:

Trivial search for the largest prime.

Solution:

import math
def solution(N):
    if N <= 0:
      return 0
  
    for i in xrange(int(math.sqrt(N)), 0, -1):
        if N % i == 0:
            return 2*(i+N/i)
            
    raise Exception("should never reach here!")

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

07/28/14

Codility ‘Count Factors’ Solution

Short Problem Definition:

Count factors of given number N.

Link

CountFactors

Complexity:

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

expected worst-case space complexity is O(1).

Execution:

This example can be found in the lesson document.

Solution:

def solution(N):
    cnt = 0
    i = 1
    while ( i * i <= N):
        if (N % i == 0):
            if i * i == N:
               cnt += 1
            else:
                cnt += 2
        i += 1
    return cnt

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

07/25/14

Codility ‘Nesting’ Solution

Short Problem Definition:

Determine whether given string of parentheses is properly nested.

Link

Nesting

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

Because there is only one type of brackets, the problem is easier than Brackets. Just check if there is always a opening bracket before a closing one.

Solution:

def solution(S):
    leftBrackets = 0
    
    for symbol in S:
        if symbol == '(':
            leftBrackets += 1
        else:
            if leftBrackets == 0:
                return 0
            leftBrackets -= 1  
    
    if leftBrackets != 0:
        return 0
    
    return 1

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

07/23/14

Codility ‘FrogJmp’ Solution

Short Problem Definition:

Count minimal number of jumps from position X to Y.

Link

FrogJmp

Complexity:

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

expected worst-case space complexity is O(1).

Execution:

Do not use float division if possible!

Solution:

def solution(X, Y, D):
    if Y < X or D <= 0:
        raise Exception("Invalid arguments")
        
    if (Y- X) % D == 0:
        return (Y- X) // D
    else:
        return ((Y- X) // D) + 1

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

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.

07/18/14

Codility ‘Fish’ Solution

Short Problem Definition:

N voracious fish are moving along a river. Calculate how many fish are alive.

Link

Fish

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Put all downstream swimming fishes on a stack. Any upstream swimming fish has to fight(eat) all fishes on the stack. If there is no fish on the stack, the fish survives. If the stack has some downstream fishes at the end, they also survive.

Solution:

def solution(A, B):
    survivals = 0
    stack = []
    
    for idx in xrange(len(A)):
        if B[idx] == 0:
            while len(stack) != 0:
                if stack[-1] > A[idx]:
                    break
                else:
                    stack.pop()
                        
            else:
                survivals += 1
        else:
            stack.append(A[idx])
            
    survivals += len(stack)
    
    return survivals

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

07/10/14

Codility ‘Brackets’ Solution

Short Problem Definition:

Determine whether a given string of parentheses is properly nested.

Link

Brackets

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Put every opening bracket on a stack. If a closing bracket is not the same as the top stack bracket, the string is not properly nested.

Solution:

def isValidPair(left, right):
    if left == '(' and right == ')':
        return True
    if left == '[' and right == ']':
        return True  
    if left == '{' and right == '}':
        return True    
    return False

def solution(S):
    stack = []
    
    for symbol in S:
        if symbol == '[' or symbol == '{' or symbol == '(':
            stack.append(symbol)
        else:
            if len(stack) == 0:
                return 0
            last = stack.pop()
            if not isValidPair(last, symbol):
                return 0
    
    if len(stack) != 0:
        return 0
            
    return 1

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