Some coding problems

closest_pair2d.py

# find closest pair of points in 2d space in O(nlogn)

import sys
import math


def euclidean_distance(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return math.sqrt((x2-x1)**2 + (y2 - y1)**2)


def closest(P, X, Y, x_start, x_end, y_start, y_end):
    if x_end - x_start <= 3:
        min_dist_rv = [sys.maxsize, None, None]
        # base case
        for i in range(x_start, x_end - 1):
            for j in range(i+1, x_end):
                d = euclidean_distance(X[i], X[j])
                if d < min_dist_rv[0]:
                    min_dist_rv = [d, X[i], X[j]]

        return min_dist_rv

    else:  # divide into two halves and recurse
        x_mid = int((x_end - x_start) / 2)
        # TODO:
        Y_left = [y for y in Y if X[x_start][0] <= y[0] <= X[x_mid - 1][0]]
        Y_right = [y for y in Y if X[x_mid][0] <= y[0] <= X[x_end - 1][0]]

        rv_left = closest(P, X, Y_left, x_start, x_mid, 0, len(Y_left))
        rv_right = closest(P, X, Y_right, x_mid, x_end, 0, len(Y_right))

        if rv_left[0] < rv_right[0]:
            delta = rv_left[0]
            min_dist_rv = rv_left
        else:
            delta = rv_right[0]
            min_dist_rv = rv_right

        # TODO:
        # find all the points that lie with **delta** distance of the dividing strip
        # rightmost point in left part is X[x_mid-1]
        # leftmost point in right part is X_right[x_mid]
        split_x = (X[x_mid-1][0] + X[x_mid][0]) / 2.0
        left_margin_x = split_x - delta
        right_margin_x = split_x + delta

        # pick a point in the slice which are also in X_left
        for i in range(x_start, x_mid):
            if X[i][0] < left_margin_x:
                continue

            # this point is within the left side of the split split
            # check against points on the right side of the split
            p1 = X[i]
            for p2 in Y_right:
                # skip out of bounds points
                if p2[0] > right_margin_x or p2[1] < p1[1] - delta or p2[1] > p1[1] + delta:
                    continue

                # this point is within the bounds
                distance = euclidean_distance(p1, p2)
                if distance < min_dist_rv[0]:
                    min_dist_rv = [distance, p1, p2]
        return min_dist_rv


P = ((2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4))
X = sorted(P, key=lambda p: p[0])
Y = sorted(P, key=lambda p: p[1])
N = len(P)

rv = closest(P, X, Y, 0, N, 0, N)

print("The smallest distance is %f ", rv)

substring_with_2letters.py

# Find substring with only two letters, in O(n)

DEBUG = False


def assertEquals(x, y):
    if x != y:
        raise AssertionError("%s not equals %s" % (x, y))


def solve(s):
    s = s + "\0"
    N = len(s)
    # base case
    if N <= 2:
        return s, len(s)

    # print(s)
    c = s[0]
    table = {c: [0, 0]}
    e_max = [1, 0, 1]
    prev_char = c
    start_index = 0
    for i in range(1, N):  # maintain the inviarant that table doesn't hold more than 2 chars
        c = s[i]
        if DEBUG:
            print("i = %s, start_index = %s, char = %s, prev_char = %s, table = %s"
                  % (i, start_index, c, prev_char, table))
        if c not in table and len(table) == 2:  # 3rd character encountered
            # print("   A")
            sublen = i - start_index
            e_max = [sublen, start_index, i] if sublen > e_max[0] else e_max
            table = {prev_char: table[prev_char], c: [i, i]}
            start_index = table[prev_char][0]
        elif c not in table:
            # print("   B")
            table[c] = [i, i]
        else:
            if c == prev_char:
                # print("   C")
                table[c][1] = i
            else:
                # print("   D")
                table[c] = [i, i]

        prev_char = c

    max_len, begin, end = e_max
    return s[begin:end], max_len


def test0():
    # assertEquals(solve("ab"), ("ab", 2))
    assertEquals(solve("aa"), ("aa", 2))


def test1():
    assertEquals(solve("aabbbcccccc"), ("bbbcccccc", 9))
    assertEquals(solve("abccc"), ("bccc", 4))
    assertEquals(solve("bbbcccccc"), ("bbbcccccc", 9))


def test2():
    assertEquals(solve("abababaccacabbb"), ("abababa", 7))
    assertEquals(solve("abababa"), ("abababa", 7))


def test3():
    assertEquals(solve("ababbcccdddd"), ("cccdddd", 7))
    assertEquals(solve("cccdddd"), ("cccdddd", 7))


if __name__ == "__main__":
    DEBUG = False
    # test0()
    test1()
    test2()
    test3()