12/11/14

# Codility ‘OddOccurrencesInArray’ Solution

##### Short Problem Definition:

Find value that occurs in odd number of elements.

OddOccurrencesInArray

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

This problem can be found in many algorithm books. A xor A cancels itself and B xor 0 is B. Therefore A xor A xor B xor C xor C is B.

##### Solution:
```def solution(A):
missing_int = 0
for value in A:
missing_int ^= value
return missing_int
```

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

12/7/14

# Codility ‘Str Symmetry Point’ Solution

##### Short Problem Definition:

Find a symmetry point of a string, if any.

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.

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/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.

08/25/14

# Codility ‘TieRopes’ Solution

##### Short Problem Definition:

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

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.

08/15/14

# Codility ‘CountDistinctSlices’ Solution

##### Short Problem Definition:

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

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.

08/14/14

# Codility ‘AbsDistinct’ Solution

##### Short Problem Definition:

Compute number of distinct absolute values of sorted array elements.

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.

08/13/14

# Codility ‘TreeHeight’ Solution

##### Short Problem Definition:

Compute the height of a binary link-tree.

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.

08/12/14

# Codility ‘MinAbsSumOfTwo’ Solution

##### Short Problem Definition:

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

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.