A Few Nice Coding Challenges

A recent interview process required passing some coding challenges.

When I first started programming I spent a decent amount of time on Project Euler, but since then I rarely do these crack-the-interview coding challenges. I find project-based work more interesting, I work mostly with data, and – based on what I understand from experienced interviewers – facility with brain teasers and coding challenges correlates less with good programming than time spent programming correlates with good programming. Anyway, I spent a few afternoons working through coding challenges on Codility to get a feel for the types of questions that get asked of software engineering candidates.

Most of these were actually a lot of fun, and a lot of them introduced or reinforced good ideas about managing time and space complexity (Codility scores are based on program runtime), something that I tend to overlook.

For what it’s worth I passed the test, had some fun, and doubt I would have passed without working through the sample problems. I wouldn’t be surprised if I find my way back to Project Euler again. Among some duds, here are a few of the more interesting problems I looked at:

Negative Binary

Basically, this problem asks for translation into and out of base -2 notation, which is like binary except every odd bit takes a negative value. That is, for zero-indexed array A of length N with lowest-value bit first:

Given the negative binary representation of one value X, the problem asks you to create the negative binary representation of -X. The real insight is seeing that regardless of whether A[i] is even (positive) or odd (negative), adding one integer to its negative double equals the negation of the original number: . For example, 16 + (-32) = -16, and (-32) +64 = 32.

In other words:

So we can just transform bit sequences directly by mapping them to new sequences. The solution ain’t pretty, but works in . It’s a basic case-of pattern to transform bits according to the basic insight above, plus edge cases for last index and trailing zeroes, as well as a solver for checking our output and debugging.

def solution(A):
    """
   Negative binary notation (base -2) works just like binary, but instead of each bit representing 2^n, each bit
   represents 2^(-n). For example, "1011" in regular binary is 8+2+1 = 11. In negative binary, "1011" is -8-2+1 = -9.
   Given a list of bits -> [0,1] A in negative binary summing to X, return the shortest negative binary representation
   of -X.
   """
    B=(len(A)+1)*[0]
    i = 0
    while i < len(A):
        if A[i] == 1 and i == len(A)-1:
            B[i], B[i+1] = 1, 1
            i +=1
        elif A[i] == 0:
            B[i] = 0
            i += 1
        elif A[i] == 1 and A[i+1] == 0:
            B[i], B[i+1] = 1, 1
            i += 2
        elif A[i] == 1 and A[i+1] == 1:
            B[i], B[i+1] = 1, 0
            i += 2

    while B and B[-1] == 0:
    B.pop()

    return A, solver(A), B, solver(B)

def solver(A):
    """
   Return value of negative binary input
   """
    mysum = 0
    for i in range(len(A)):
        mysum+= A[i] * (-2)**i
    return mysum

Number of Disc Intersections

Another interesting one to think about: here you’re given a list of integers and told that for each value in the list, a circle of radius (list index value) centered at (list index) will be drawn, and you’re asked to count the number of intersections between all circles in the list.

Insight here is that after sorting, while leftmost-bounded circle’s right bound is greater than leftmost bound of successive circles, add that to intersection counts. There’s a much simpler (and faster) way to do it that I found online, posted below my solution.

def solution(A):
    """
   NumberofDiscIntersections
   Solution creates tuple of left and right bound for each circle, sorts
   tuples by left bound, starts with first circle, counts number of times the right bound of the first circle is
   greater than the left bound of successive circles, delete circle and iterate through circles until none left.
   """
    tuple_lis = []
    for i in range(len(A)):
        val = (i-A[i], i+A[i])
        tuple_lis.append(val)
    lsort  = sorted(tuple_lis)
    intersections = 0
    for n in range(len(lsort)):
        try:
            intersections += (next(i for (i,x) in enumerate([y[0] for y in lsort]) if x > lsort[0][1]) - 1)
        except:
            intersections += (len(lsort) - 1)
        del lsort[0]
    return intersections

def solution(A):
    """
   NumberofDiscIntersections
   Faster, simpler
   """
    upper = sorted([i + val for i, val in enumerate(A)])
    lower = sorted([i - val for i, val in enumerate(A)])

    counter = 0
    j = 0
    for i, uval in enumerate(upper):
        while j < len(upper) and uval >= lower[j]:
            counter += j-i
            j += 1
        if counter > 10**7: return -1

    return counter

Maximum Stock Price

Given a list of yesterday’s stock prices, what’s the most profit you could have made from a long position within that day? My solution, and another I found that saves some time eliminating the min price loop.

def compl(A):
    """
   Given a list A of ints representing a stock price at successive times of the day, return the maximum profit that
   can be obtained from a long position within that day. E.g., A = [10, 7, 5, 8, 11, 9] -> 6
   """
    max_total = 0
    for i in A:
        max_val = 0
        for j in range(len(A)-1):
            max_val = max(max_val, A[j]-i)
        max_total = max(max_total, max_val)
    if max_total <= 0:
        return 0
    return max_total

def get_max_profit(stock_prices_yesterday):
    """
   O(n) solution. By greedy updating the minimum price you avoid one loop.
   """
    if len(stock_prices_yesterday) < 2:
        raise IndexError('Getting a profit requires at least 2 prices')

    min_price = stock_prices_yesterday[0]
    max_profit = stock_prices_yesterday[1] - stock_prices_yesterday[0]

    for index, current_price in enumerate(stock_prices_yesterday):
        if index == 0:
            continue
        potential_profit = current_price - min_price
        max_profit = max(max_profit, potential_profit)
        min_price  = min(min_price, current_price)
    return max_profit