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/18/14

Why No Wise Words Will Help


It is essential to every professional to grow her insights on the technology she is working with. In general I am talking about reading books, blogs, listening to pod-casts, solving small challenges, going to meetups or generally just talk to people from the same domain. Yet reading alone is not going to hep. You can spend hours watching tutorial videos on the newest and hottest technology trend, and learn nothing. The funny thing about this approach, is that it does not help you in any way, as long as you do not internally integrate the new knowledge. I am talking about resonance. Do you know the feeling, when the text you are reading is making you excited? You instantly know many situations, when if you already had this knowledge, everything would have been easier. Why is that?

Knowledge

Continue reading


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