12/7/14

Codility ‘Str Symmetry Point’ Solution

Short Problem Definition:

Find a symmetry point of a string, if any.

Link

StrSymmetryPoint

Complexity:

expected worst-case time complexity is O(length(S));

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

Execution:

This problem gave me a lot of headache. It is so trivial I that over-complicated it. I thought that you should find a symmetry point at any possible position, ignoring the residual characters. You would obviously try to maximize the length of this symmetrical sub-array. I was not able to come with any O(S) algorithm for this problem derivation. So just to remind you, this problem is a simple palindrome check. Additionally, you drop all evenly sized strings as their symmetry point is between the indexes.

Solution:
def solution(S):
    l = len(S)

    if l % 2 == 0:
        return -1

    mid_point = l // 2

    for idx in xrange(0, mid_point):
        if S[idx] != S[l - idx - 1]:
            return -1

    return mid_point

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/26/14

Codility ‘CountTriangles’ Solution

Short Problem Definition:

Count the number of triangles that can be built from a given set of edges.

Link

CountTriangles

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

Apply the caterpillar method. We know that in a sorted array every position between Q and R will be bigger than Q and therefore P+Q will be bigger than R. I therefore either increment Q if P+Q is not larger than R or increment R as far as possible.

Solution:
def solution(A):
    A.sort()
    print A
    triangle_cnt = 0
    
    for P_idx in xrange(0, len(A)-2):
        Q_idx = P_idx + 1
        R_idx = P_idx + 2
        while (R_idx < len(A)):
            if A[P_idx] + A[Q_idx] > A[R_idx]:
                triangle_cnt += R_idx - Q_idx
                R_idx += 1
            elif Q_idx < R_idx -1:
                    Q_idx += 1
            else:
                R_idx += 1
                Q_idx += 1
                
    return triangle_cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/17/14

Codility ‘NailingPlanks’ Solution

Short Problem Definition:

Count the minimum number of nails that allow a series of planks to be nailed..

Link

NailingPlanks

Complexity:

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

expected worst-case space complexity is O(M)

Execution:

The solution gets 100/100, but I am skeptical. The runtime is rather O(N * (log(M)+M)) than O((N+M)*log(M)).  Maybe it can be proven that the execution of the linear scan will never have to scan all possible positions. I also violate the space complexity by creating a copy of A+B.

Solution:
PLANK_START = 0
PLANK_END = 1

NAIL_ARR_IDX = 0
NAIL_HIT_LOCATION = 1

class NoNailFoundException(Exception):
    def __init__(self):
        pass

def findPosOfNail(nails, plank, previous_max):
    nail_idx = -1
    result = -1

    # logarithmic scan O(log(M))
    lower_idx = 0
    upper_idx = len(nails) - 1

    while lower_idx <= upper_idx:
        mid_idx = (lower_idx + upper_idx) // 2
        if nails[mid_idx][NAIL_HIT_LOCATION] < plank[PLANK_START]:
            lower_idx = mid_idx + 1
        elif nails[mid_idx][NAIL_HIT_LOCATION] > plank[PLANK_END]:
            upper_idx = mid_idx - 1
        else:
            upper_idx = mid_idx - 1
            result = nails[mid_idx][PLANK_START]
            nail_idx = mid_idx

    if result == -1:
        raise NoNailFoundException

    # linear scan O(M)
    nail_idx += 1
    while nail_idx < len(nails):
        if nails[nail_idx][NAIL_HIT_LOCATION] > plank[PLANK_END]:
            break
        result = min(result, nails[nail_idx][NAIL_ARR_IDX])
        if result <= previous_max:
            return result
        nail_idx += 1

    if result == -1:
        raise NoNailFoundException

    return result

def getNrNailsRequired(planks, nails):
    result = 0
    for plank in planks:
        result = max(result, findPosOfNail(nails, plank, result))

    return result+1

def solution(A, B ,C):
    planks = zip(A,B)

    nails = sorted(enumerate(C), key=lambda var: var[1])

    try:
        return getNrNailsRequired(planks, nails)
    except NoNailFoundException:
        return -1

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

Facebooktwittergoogle_plusredditpinterestlinkedin
09/16/14

Codility ‘MinMaxDivision’ Solution

Short Problem Definition:

Divide array A into K blocks and minimize the largest sum of any block.

Link

MinMaxDivision

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

Binary search for the minimal size of a block. A valid block can be checked in a boolean fashion. Two special cases can be sped up (courtesy to CodeSays). At the time of writing (19.9.2014) do not use the variable passed to the solution function as M! It is NOT the maximum element in the test cases! The specification says, that no element is larger than M, yet there is not guarantee that M == max(A).

Solution:
def blockSizeIsValid(A, max_block_cnt, max_block_size):
    block_sum = 0
    block_cnt = 0

    for element in A:
        if block_sum + element > max_block_size:
            block_sum = element
            block_cnt += 1
        else:
            block_sum += element
        if block_cnt >= max_block_cnt:
            return False

    return True

def binarySearch(A, max_block_cnt, using_M_will_give_you_wrong_results):
    lower_bound = max(A)
    upper_bound = sum(A)

    if max_block_cnt == 1:      return upper_bound
    if max_block_cnt >= len(A): return lower_bound

    while lower_bound <= upper_bound:
        candidate_mid = (lower_bound + upper_bound) // 2
        if blockSizeIsValid(A, max_block_cnt, candidate_mid):
            upper_bound = candidate_mid - 1
        else:
            lower_bound = candidate_mid + 1

    return lower_bound

def solution(K, M, A):
    return binarySearch(A,K,M)

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/25/14

Codility ‘TieRopes’ Solution

Short Problem Definition:

Tie adjacent ropes to achieve the maximum number of ropes of length >= K.

Link

TieRopes

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

I am a bit skeptical about the correctness of my solution. It gets 100/100 through…

Solution:
def solution(K, A):
    cnt = 0
    current = 0
    for part in A:
        current += part
        if current >= K:
            cnt +=1
            current = 0

    return cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/15/14

Codility ‘CountDistinctSlices’ Solution

Short Problem Definition:

Count the number of distinct slices (containing only unique numbers).

Link

CountDistinctSlices

Complexity:

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

expected worst-case space complexity is O(M)

Execution:

Using the caterpillar method I expand the caterpillar to the right as long as a duplicate element is found. The right side has to retract as long as this duplicate element has been eliminated from the next slice. An observation showed that the number of sub-slices is equal to front-back+1.

Solution:
def solution(M, A):
    the_sum = 0
    front = back = 0
    seen = [False] * (M+1)
    while (front < len(A) and back < len(A)):
        while (front < len(A) and seen[A[front]] != True):
            the_sum += (front-back+1)
            seen[A[front]] = True
            front += 1
        else:
            while front < len(A) and back < len(A) and A[back] != A[front]:
                seen[A[back]] = False
                back += 1
                
            seen[A[back]] = False
            back += 1
            
                
    return min(the_sum, 1000000000)  

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/14/14

Codility ‘AbsDistinct’ Solution

Short Problem Definition:

Compute number of distinct absolute values of sorted array elements.

Link

AbsDistinct

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Additional storage is allowed. Therefore a simple python solution will suffice.

Solution:
def solution(A):
    return len(set([abs(x) for x in A]))

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/13/14

Codility ‘TreeHeight’ Solution

Short Problem Definition:

Compute the height of a binary link-tree.

Link

TreeHeight

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

The height of a tree is the maximal height +1 of its subtrees. In this specification a tree with just the root node has a height of 0.

Solution:
'''
class Tree(object):
  x = 0
  l = None
  r = None
'''

def getHeight(sub_T):
    if sub_T == None:
        return 0
    return max(getHeight(sub_T.l), getHeight(sub_T.r))+1

def solution(T):
    return max(getHeight(T.l), getHeight(T.r))

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/12/14

Codility ‘MinAbsSumOfTwo’ Solution

Short Problem Definition:

Find the minimal absolute value of a sum of two elements.

Link

MinAbsSumOfTwo

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

Using the caterpillar method on a sorted list.

Solution:

C-style python

def solution(A):
    value = 2000000000
    front_ptr = 0
    back_ptr = len(A)-1
    A.sort()
    
    while front_ptr <= back_ptr: value = min(value, abs(A[front_ptr] + A[back_ptr])) if abs(A[front_ptr]) > abs(A[back_ptr]):
            front_ptr += 1
        else:
            back_ptr -= 1
            
    return value

Functional pythonesque:

from itertools import *
def getAbsDiff(t):
  return abs(t[0] + t[1])

def solution(A):
  A.sort(key=abs)
  return getAbsDiff(min(chain(izip(A, A),izip(A,A[1:])), key = getAbsDiff))

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/11/14

Codility ‘CommonPrimeDivisors’ Solution

Short Problem Definition:

Check whether two numbers have the same prime divisors.

Link

CommonPrimeDivisors

Complexity:

expected worst-case time complexity is O(Z*log(max(A)+max(B))2);

expected worst-case space complexity is O(1)

Execution:

I will post an explaining image soon!

Solution:
def gcd(p, q):
  if q == 0:
    return p
  return gcd(q, p % q)

def hasSameFactors(p, q):
    if p == q == 0:
        return True
    
    denom = gcd(p,q)
    
    while (p != 1):
        p_gcd = gcd(p,denom)
        if p_gcd == 1:
            break
        p /= p_gcd
    else:
        while (q != 1):
            q_gcd = gcd(q,denom)
            if q_gcd == 1:
                break
            q /= q_gcd
        else:
            return True
    
    return False


def solution(A, B):
    if len(A) != len(B):
        raise Exception("Invalid input")
    cnt = 0
    for idx in xrange(len(A)):
        if A[idx] < 0 or B[idx] < 0:
            raise Exception("Invalid value")
        if hasSameFactors(A[idx], B[idx]):
            cnt += 1
    
    return cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin