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

Codility ‘ChocolatesByNumbers’ Solution

Short Problem Definition:

There are N chocolates in a circle. Count the number of chocolates you will eat.

Link

ChocolatesByNumbers

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

N and M meet at their least common multiply. Dividing this LCM by M gets the number of steps(chocolates) that can be eaten.

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

def lcm(p,q):
    return p * (q / gcd(p,q))

def solution(N, M):
    return lcm(N,M)/M

def naive(N,M):
    eaten = [False] * N
    at = 0
    cnt = 0
    while eaten[at] != True:
        eaten[at] = True
        at = (at + M) % N
        cnt += 1
        
    return cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/9/14

Codility ‘EquiLeader’ Solution

Short Problem Definition:

Find the index S such that the leaders of the sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

Link

EquiLeader

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Get the leader as in the training material. Afterwards check every position if both sides have enough leader occurrences.

Solution:
def solution(A):
    candidate_ele = ''
    candidate_cnt = 0

    for value in A:
        if candidate_ele == '':
            candidate_ele = value
            candidate_cnt = 1
        else:
            if value != candidate_ele:
                candidate_cnt -= 1
                if candidate_cnt == 0:
                    candidate_ele = ''
            else:
                candidate_cnt += 1

    if candidate_cnt == 0:
        return 0

    cnt = 0
    last_idx = 0

    for idx, value in enumerate(A):
        if value == candidate_ele:
            cnt += 1
            last_idx = idx

    if cnt < len(A)//2:
        return 0

    equi_cnt = 0
    cnt_to_the_left = 0
    for idx, value in enumerate(A):
        if value == candidate_ele:
            cnt_to_the_left +=1
        if cnt_to_the_left > (idx + 1)//2 and \
            cnt - cnt_to_the_left > (len(A) - idx - 1) //2:
            equi_cnt += 1

    return equi_cnt

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/8/14

Codility ‘Dominator’ Solution

Short Problem Definition:

Find an index of an array such that its value occurs at more than half of indices in the array.

Link

Dominator

Complexity:

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

expected worst-case space complexity is O(1)

Execution:

As explained in the training material…

Solution:
def solution(A):
    candidate_ele = ''
    candidate_cnt = 0
    
    for value in A:
        if candidate_ele == '':
            candidate_ele = value
            candidate_cnt = 1
        else:
            if value != candidate_ele:
                candidate_cnt -= 1
                if candidate_cnt == 0:
                    candidate_ele = ''
            else:
                candidate_cnt += 1
        
    if candidate_cnt == 0:
        return -1
        
    cnt = 0
    last_idx = 0
    
    for idx, value in enumerate(A):
        if value == candidate_ele:
            cnt += 1
            last_idx = idx
            
    if cnt > len(A)//2:
        return last_idx
        
    return -1

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

Facebooktwittergoogle_plusredditpinterestlinkedin
08/7/14

Codility ‘Triangle’ Solution

Short Problem Definition:

Determine whether a triangle can be built from a given set of edges.

Link

Triangle

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

By sorting the array, we have guaranteed that P+R > Q and Q+R > P (because R is always the biggest). Now what remains, is the proof that P+Q > R, that can be found out by traversing the array. The chance to find such a combination is with three adjacent values as they provide the highest P and Q.

Solution:
def solution(A):
    if len(A) < 3:
        raise Exception("invalid input")

    A.sort()
    
    for i in xrange(len(A)-2):
        if A[i] + A[i+1] > A[i+2]:
            return 1
            
    return 0

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

Facebooktwittergoogle_plusredditpinterestlinkedin