09/26/14

# Codility ‘CountTriangles’ Solution

##### Short Problem Definition:

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

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.

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

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

09/17/14

# Codility ‘NailingPlanks’ Solution

##### Short Problem Definition:

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

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.

09/16/14

# Codility ‘MinMaxDivision’ Solution

##### Short Problem Definition:

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

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.