Short Problem Definition:

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

Link

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[0] * A[1] * A[-1], A[-1] * A[-2] * A[-3])

A better solution has been suggested in the commends by Mindaugas Tvaronavičius. Here the solution in O(N) time using two heaps.

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)

Short Problem Definition:

Find the minimal nucleotide from a range of sequence DNA.

Link

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 = [0] * 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
    

Short Problem Definition:

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

Link

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

Short Problem Definition:

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

Link

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[0] = sieve[1] = 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):
                    semi.add(j)
        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

Short Problem Definition:

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

Link

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

Short Problem Definition:

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

Link

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