Skip to content

Instantly share code, notes, and snippets.

@tuxdna
Last active February 8, 2018 14:11
Show Gist options
  • Save tuxdna/6a4da241e3bccef70154632d719f2a4d to your computer and use it in GitHub Desktop.
Save tuxdna/6a4da241e3bccef70154632d719f2a4d to your computer and use it in GitHub Desktop.
Some coding problems
# 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)
# 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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment