Bohdan polamayster
polamayster
/ trie.py
Created
August 25, 2020 21:04
This file contains hidden or 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 Trie: | |
| def __init__(self): | |
| """ | |
| Initialize your data structure here. | |
| """ | |
| self.tops = {} | |
| def insert(self, word: str) -> None: | |
| """ |
polamayster
/ topological_sort.py
Last active
January 17, 2022 22:56
This file contains hidden or 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 networkx as nx | |
| def tps(dg: nx.DiGraph): | |
| dependencies_order, visited_nodes = [], set() | |
| def traverse(dg: nx.DiGraph, node): | |
| visited_nodes.add(node) | |
| for dependency in dg.successors(node): | |
| if dependency not in visited_nodes: | |
| traverse(dg, dependency) |
polamayster
/ levenshtein_edit_distance.py
Last active
March 22, 2021 10:00
This file contains hidden or 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 ld(a, b): | |
| if len(a) < len(b): | |
| return ld(b, a) | |
| if len(b) == 0: | |
| return len(a) | |
| prev_row = range(len(b) + 1) | |
| for i, ai in enumerate(a, 1): | |
| cur_row = [i] | |
| for j, bj in enumerate(b, 1): | |
| if ai != bj: |
polamayster
/ unbounded_knapsack.py
Created
February 19, 2018 17:41
This file contains hidden or 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_duffel_bag_value(cake_tuples, weight_capacity): | |
| max_values_at_capacities = [0] * (weight_capacity + 1) | |
| for current_capacity in range(weight_capacity + 1): | |
| current_max_value = 0 | |
| for cake_weight, cake_value in cake_tuples: | |
| if cake_weight == 0 and cake_value != 0: | |
| return float('inf') | |
| if cake_weight <= current_capacity: |
polamayster
/ isBalanced.py
Last active
August 3, 2021 09:22
This file contains hidden or 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 isBalanced(string): | |
| stack = [] | |
| for i in range(len(string)): | |
| try: | |
| if string[i] == "(": | |
| stack.append('(') | |
| elif string[i] == ")": | |
| stack.pop() | |
| except IndexError: | |
| return False |
polamayster
/ lcs_length.py
Created
October 16, 2016 15:11
This file contains hidden or 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 lcs_length(a, b): | |
| table = [[0] * (len(b) + 1)] * (len(a) + 1) | |
| for i, ca in enumerate(a, 1): | |
| for j, cb in enumerate(b, 1): | |
| table[i][j] = ( | |
| table[i - 1][j - 1] + 1 if ca == cb else | |
| max(table[i][j - 1], table[i - 1][j])) | |
| return table[-1][-1] |
polamayster
/ pascal_triangle.py
Last active
October 16, 2016 14:52
This file contains hidden or 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 pascal_triangle(n): | |
| prev = [] | |
| for row in xrange(n): | |
| curr = [1] | |
| for index in xrange(1, row): | |
| curr.append(prev[index-1] + prev[index]) | |
| if row > 0: curr.append(1) | |
| print curr | |
| prev = curr |
polamayster
/ binsearch.py
Last active
October 16, 2016 15:36
This file contains hidden or 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 binsearch(needle, haystack): | |
| lo, hi, found = 0, len(haystack)-1, None | |
| while lo <= hi and found is None: | |
| mid = lo + (hi - lo) // 2 | |
| if haystack[mid] == needle: | |
| found = mid | |
| if haystack[mid] < needle: | |
| lo = mid + 1 | |
| else: | |
| hi = mid - 1 |
polamayster
/ quicksort.py
Last active
October 4, 2016 09:14
This file contains hidden or 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 | |
| def quicksort(list, lo=None, hi=None): | |
| if lo is None: | |
| lo, hi = 0, len(list)-1 | |
| if lo < hi: | |
| pivot = partition(list, lo, hi) | |
| quicksort(list, lo, pivot-1) | |
| quicksort(list, pivot + 1, hi) |
polamayster
/ graph_search.py
Last active
October 23, 2016 13:51
This file contains hidden or 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
| #!/usr/bin/env python | |
| import sys | |
| import networkx as nx | |
| from collections import deque | |
| def bfs(graph): | |
| queue = deque([]) | |
| queue.append(graph.nodes()[0]) |
NewerOlder