| def kmp_match(seq, subseq): | |
| """ | |
| Implementation of the Knuth-Morris-Pratt (KMP) algorithm in Python. | |
| This algorithm finds valid shifts to locate subsequence `subseq` in | |
| sequence `seq`. | |
| """ | |
| n = len(seq) | |
| m = len(subseq) |
| # Union-Find (Disjoint Set Union) | |
| # more information on wiki: | |
| # http://en.wikipedia.org/wiki/Disjoint-set_data_structure | |
| class UF(object): | |
| def __init__(self, size): | |
| self.p = [None]*size | |
| self.rank = [1]*size |
| #!/usr/bin/env python -O | |
| # | |
| # Copyright (c) 2013 Kyle Gorman | |
| # | |
| # Permission is hereby granted, free of charge, to any person obtaining a | |
| # copy of this software and associated documentation files (the | |
| # "Software"), to deal in the Software without restriction, including | |
| # without limitation the rights to use, copy, modify, merge, publish, | |
| # distribute, sublicense, and/or sell copies of the Software, and to | |
| # permit persons to whom the Software is furnished to do so, subject to |
| from collections import defaultdict | |
| from itertools import chain | |
| from banyan import SortedDict, OverlappingIntervalsUpdator | |
| class Rectangle(object): | |
| def __init__(self, left, bottom, right, top): | |
| self.left = left | |
| self.top = top |
| class Day(object): | |
| def __init__(self, visits, contacts): | |
| self.visits = visits | |
| self.contacts = contacts | |
| def __add__(self, other): | |
| total_visits = self.visits + other.visits | |
| total_contacts = self.contacts + other.contacts | |
| return Day(total_visits, total_contacts) |
An (undirected) Graph is a collection V of vertices, and a collection E of edges each of which connects a pair of vertices.
| """ | |
| This problem was asked by Google. | |
| Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place. | |
| Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue. | |
| For example, if the stack is [1, 2, 3, 4, 5], it should become [1, 5, 2, 4, 3]. If the stack is [1, 2, 3, 4], it should become [1, 4, 2, 3]. | |
| Hint: Try working backwords from the end state. |
| #!/usr/bin/env python3 | |
| """ | |
| Binary Indexed Tree / Fenwick Tree | |
| https://www.hackerearth.com/practice/notes/binary-indexed-tree-made-easy-2/ | |
| https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ | |
| https://www.youtube.com/watch?v=v_wj_mOAlig | |
| https://www.youtube.com/watch?v=kPaJfAUwViY | |
| """ |
I screwed up using git ("git checkout --" on the wrong file) and managed to delete the code I had just written... but it was still running in a process in a docker container. Here's how I got it back, using https://pypi.python.org/pypi/pyrasite/ and https://pypi.python.org/pypi/uncompyle6
apt-get update && apt-get install gdb
