This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import heapq as hp | |
class pqueue: | |
def __init__(self, minheap = True): | |
self.heap = [] | |
self.mul = 1 if minheap else -1 | |
self.count = 0 | |
def size(self): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def find_rotation_binary_search(L): | |
left,right = 0,len(L) - 1 | |
while L[left] > L[right]: | |
mid = (left + right) / 2 | |
if L[mid] > L[right]: | |
left = mid + 1 | |
else: | |
right = mid | |
return left |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
L = 10 | |
lst = [random.randint(0,100) for _ in xrange(L)] | |
lst.sort() | |
K = random.randint(0,L) | |
lst = lst[K:] + lst[:K] # rotate by random K | |
def find_rotation_naive(L): | |
for i in xrange(len(L) - 1): | |
if L[i] > L[i+1]: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import pqueue | |
def dijkstra(graph,src,dst): | |
min_dist = dict() # stores shortest path from src, ie min_dist[u] = w denotes, weight of shortest path (src->u) = w | |
prev_vertex = dict() # prev_vertex[u], stores the previous node on the shortest path from src to u | |
pq = pqueue.pqueue() | |
pq.push( (0, src) ) | |
min_dist[src] = 0 # distance to source is 0. | |
prev_vertex[src] = None # no previous node for src | |
while not pq.empty(): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def max_diff_naive(L): | |
max_diff = start = end = 0 | |
for i in xrange(len(L)): | |
for j in xrange(i+1,len(L)): | |
if max_diff < L[j] - L[i]: | |
start,end = i,j | |
max_diff = L[j] - L[i] | |
return max_diff,start,end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def max_diff_linear(L): | |
min_index = 0 | |
max_diff = start = end = 0 | |
for i in xrange(len(L)): | |
if L[i] < L[min_index]: min_index = i | |
if max_diff < L[i] - L[min_index]: | |
max_diff = L[i] - L[min_index] | |
start,end = min_index,i | |
return max_diff,start,end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys,graphs,itertools | |
def prepare_graph(): | |
diff_by_1 = lambda (x,y): len(x) == len(y) and sum(1 for a,b in zip(x,y) if a != b) == 1 | |
graph = {} | |
for x,y in filter(diff_by_1,itertools.product(words,repeat=2)): | |
if x not in graph: graph[x] = [] | |
if y not in graph: graph[y] = [] | |
graph[x].append( ( y , 1) ) | |
graph[y].append( ( x , 1) ) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
rand_list = sorted([random.randint(-100,100) for _ in xrange(7)]) | |
K = random.randint(0,200) | |
def subset_sum(lst,K): | |
lst.sort() | |
sz = len(lst) | |
def subset_sum_helper(index,s): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
r = {random.randint(10,100) for i in xrange(10)} | |
lst = random.sample(r,len(r)) | |
l = lst[:2] + lst[2:] * 2 | |
random.shuffle(l) | |
def missing_2_numbers(lst): | |
xor = reduce(lambda a,b : a ^ b, lst) | |
mask = (xor & -xor) #get the right most set bit. | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def subset_sum(lst,K): | |
lst.sort() | |
sz = len(lst) | |
def subset_sum_helper(index,s): | |
if index == sz or s >= K : return s == K | |
return subset_sum_helper(index + 1, s) or subset_sum_helper(index + 1, s + lst[index]) | |
return subset_sum_helper(0 , 0 ) | |