08/6/14

# Codility ‘MaxProductOfThree’ Solution

##### Short Problem Definition:

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

MaxProductOfThree

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

After sorting the largest product can be found as a combination of the last three elements. Additionally, two negative numbers add to a positive, so by multiplying the two largest negatives with the largest positive, we get another candidate. If all numbers are negative, the three largest (closest to 0) still get the largest element!

##### Solution:
```def solution(A):
if len(A) < 3:
raise Exception("Invalid input")

A.sort()

return max(A * A * A[-1], A[-1] * A[-2] * A[-3])
```

A better solution has been suggested in the commends by

```def betterSolution(A):
if len(A) < 3:
raise Exception("Invalid input")

minH = []
maxH = []

for val in A:
if len(minH) < 2:
heapq.heappush(minH, -val)
else:
heapq.heappushpop(minH, -val)

if len(maxH) < 3:
heapq.heappush(maxH, val)
else:
heapq.heappushpop(maxH, val)

max_val = heapq.heappop(maxH) * heapq.heappop(maxH)
top_ele = heapq.heappop(maxH)
max_val *= top_ele
min_val = -heapq.heappop(minH) * -heapq.heappop(minH) * top_ele

return max(max_val, min_val)
```

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

08/5/14

# Codility ‘GenomicRangeQuery’ Solution

##### Short Problem Definition:

Find the minimal nucleotide from a range of sequence DNA.

GenomicRangeQuery

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Remember the last position on which was the genome (A, C, G, T) was seen. If the distance between Q and P is lower than the distance to the last seen genome, we have found the right candidate.

##### Solution:
```def writeCharToList(S, last_seen, c, idx):
if S[idx] == c:
last_seen[idx] = idx
elif idx > 0:
last_seen[idx] = last_seen[idx -1]

def solution(S, P, Q):

if len(P) != len(Q):
raise Exception("Invalid input")

last_seen_A = [-1] * len(S)
last_seen_C = [-1] * len(S)
last_seen_G = [-1] * len(S)
last_seen_T = [-1] * len(S)

for idx in xrange(len(S)):
writeCharToList(S, last_seen_A, 'A', idx)
writeCharToList(S, last_seen_C, 'C', idx)
writeCharToList(S, last_seen_G, 'G', idx)
writeCharToList(S, last_seen_T, 'T', idx)

solution =  * len(Q)

for idx in xrange(len(Q)):
if last_seen_A[Q[idx]] >= P[idx]:
solution[idx] = 1
elif last_seen_C[Q[idx]] >= P[idx]:
solution[idx] = 2
elif last_seen_G[Q[idx]] >= P[idx]:
solution[idx] = 3
elif last_seen_T[Q[idx]] >= P[idx]:
solution[idx] = 4
else:
raise Exception("Should never happen")

return solution

```

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

08/4/14

# Codility ‘CountDiv’ Solution

##### Short Problem Definition:

Compute number of integers divisible by k in range [a..b].

CountDiv

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

This little check required a bit of experimentation. One needs to start from the first valid value that is bigger than A and a multiply of K.

##### Solution:
```def solution(A, B, K):
if B < A or K <= 0:
raise Exception("Invalid Input")

min_value =  ((A + K -1) // K) * K

if min_value > B:
return 0

return ((B - min_value) // K) + 1
```

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

08/3/14

# Codility ‘CountSemiprimes’ Solution

##### Short Problem Definition:

Count the semiprime numbers in the given range [a..b]

SemiPrimes

##### Complexity:

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

expected worst-case space complexity is O(N+M)

##### Execution:

First get all semiprimes from an adaptation of the Sieve of Eratosthenes. Because we will be computing the difference many times a prefix sum is adequate. Get the number of semiprimes up to the point. The index P is decreased by 1 because we want to know all primes that start from P.

##### Solution:
```def sieve(N):
semi = set()
sieve = [True]* (N+1)
sieve = sieve = False

i = 2
while (i*i <= N):
if sieve[i] == True:
for j in xrange(i*i, N+1, i):
sieve[j] = False
i += 1

i = 2
while (i*i <= N):
if sieve[i] == True:
for j in xrange(i*i, N+1, i):
if (j % i == 0 and sieve[j/i] == True):
i += 1

return semi

def solution(N, P, Q):

semi_set = sieve(N)

prefix = []

prefix.append(0) # 0
prefix.append(0) # 1
prefix.append(0) # 2
prefix.append(0) # 3
prefix.append(1) # 4

for idx in xrange(5, max(Q)+1):
if idx in semi_set:
prefix.append(prefix[-1]+1)
else:
prefix.append(prefix[-1])

solution = []

for idx in xrange(len(Q)):
solution.append(prefix[Q[idx]] - prefix[P[idx]-1])

return solution
```

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

08/2/14

# Codility ‘BinaryGap’ Solution

##### Short Problem Definition:

Find longest sequence of zeros in binary representation of an integer.

BinaryGap

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

The solution is straight-forward! Use of binary shift.

##### Solution:
```def solution(N):
cnt = 0
result = 0
found_one = False

i = N

while i:
if i & 1 == 1:
if (found_one == False):
found_one = True
else:
result = max(result,cnt)
cnt = 0
else:
cnt += 1
i >>= 1

return result
```

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

08/1/14

# Codility ‘Distinct’ Solution

##### Short Problem Definition:

Compute number of distinct values in an array.

Distinct

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

Sorting in both C++ and Python takes N log N time. We know that for this particular problem sorting the array will be the dominant runtime complexity. This is the case for the second python solution. What about the other ones?

The first solution is a neat pythonic way of solving a distinct entries problem. The set is implemented as a hash table so it is possible that it will degrade to a linked list. Therefore the actual worst case would be N^2.

This is not the case with C++ (as code 3 shows). The std set is a Red-Black Tree and therefore has insertion complexity of log N. (overall N log N)

##### Solution:
```def solution(A):
return len(set(A))
```

```def solution(A):
if len(A) == 0:
return 0

A.sort()

nr_values = 1
last_value = A

for idx in xrange(1, len(A)):
if A[idx] != last_value:
nr_values += 1
last_value = A[idx]

return nr_values
```

```#include <set>
int solution(const vector<int> &A) {
std::set<int> theSet;

for(int idx = 0; idx < A.size(); idx++){
theSet.insert(A[idx]);
}

return theSet.size();
}
```

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

08/1/14

# Codility ‘MaxProfit’ Solution

##### Short Problem Definition:

Given a log of stock prices compute the maximum possible earning.

MaxProfit

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

Keep the minimal value up to day. The profit on day i is profit[i] – min_profit.

##### Solution:
```def solution(A):
max_profit = 0
max_day = 0
min_day = 200000

for day in A:
min_day = min(min_day, day)
max_profit = max(max_profit, day-min_day)

return max_profit
```

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