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 merge(a1, a2): | |
res = [] | |
i = 0 | |
j = 0 | |
while i < len(a1) and j < len(a2): | |
if a1[i] < a2[j]: | |
res.append(a1[i]) | |
i += 1 | |
else: | |
res.append(a2[j]) |
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 quicksort(a): | |
if len(a) <= 1: | |
return a | |
lesser = [x for x in a[1:] if x < a[0]] | |
greater = [x for x in a[1:] if x >= a[0]] | |
return quicksort(lesser) + [a[0]] + quicksort(greater) | |
print quicksort([4, 6, 5, 3, 4, 7, 6, 5, 8, 9]) |
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 sublists(a, n): | |
if n == 0: | |
return [[]] | |
elif len(a) == 0: | |
return [] | |
else: | |
return sublists(a[1:], n) + [[a[0]] + s for s in sublists(a[1:], n - 1)] | |
def partition(a): |
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
from collections import defaultdict | |
def weights(triples): | |
tree = defaultdict(list) | |
weights = defaultdict(int) | |
cache = defaultdict(int) | |
for t in triples: | |
weights[t[0]] = t[2] | |
tree[t[1]].append(t[0]) |
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 product(lists): | |
result = [[]] | |
for l in lists: | |
result = [x + [y] for x in result for y in l] | |
for prod in result: | |
yield prod | |
def inverse_phone(mappings, s): | |
numbers = set([int(n) for n in s]) | |
combinations = product([mappings[n] for n in numbers]) |
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 trie(*words): | |
root = {} | |
for word in words: | |
curr_node = root | |
for letter in word: | |
curr_node = curr_node.setdefault(letter, {}) | |
curr_node.setdefault(None, None) | |
return root | |
def trie_contains(trie, word): |
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
class RollingHash: | |
s = None | |
start = 0 | |
end = 0 | |
hash = 0 | |
def __init__(self, s, length): | |
self.s = s | |
self.end = length - 1 | |
for i in range(length): |
OlderNewer