A Few Notes on LeetCode
I’ve recently been using LeetCode to brush up on those algorithm/CS-type fundamentals that have degraded since my undergrad days. Here’s a couple notes I’ve made over the first two weeks, in no particular order.
numpyis available. Quite a few problems I’ve found give a two-dimensional array in the form of
List[List], which I’ll immediately pack into a
np.array. This allows for both horizontal and vertical slicing (useful for, well, slicing) as well as the other
numpyn-dimensional routines. Also, when
- Generator syntax for tree traversal. Writing something like
def it(node): if(node): yield node yield from it(node.left) yield from it(node.right)
makes it possible to do a
for n in node(root):to iterate over all the nodes in a tree in a particular traversal order. Occasionally, the tree structure is too large for the recursion limit so it is sometimes necessary to write the stack/queue explicitly (as well as breadth-first search is not as intuitive in generator form), but this allows for a quick implementation of a search as a first pass. The traversal order can be changed by altering the order of the
yieldstatements. It’s also useful to wrap things like linked-lists or palindrome numbers into generators.
Getting to know the python standard library better. The
collectionsmodule has some useful containers:
dequefor O(1) implementations of a queue or stack,
d.get(key, default)all over,
Counterto count items in lists and strings. Also,
dictkeys are guaranteed to be in insertion order since version 3.7. The
heapqmodule gives an implementation of a min heap and
bisectgives efficient searching of sorted lists. Adding the
@lru_cache(None)decorator to a recursive function can take it from “time limit exceeded” to “dynamic programming”. And of course
itertoolsseemingly has every way of sticking iterators together.
I naturally find myself tending towards the simulation/numerical solution to the problem even though that is not usually the most efficient implementation. Times I’ve reached for
np.isclosehave all been wrong; floating point numbers hardly show their faces and most solutions have an exact answer. I’ve gone for the simulation solution for problems like this and this. Problems about solving equations seem to be more about correct parsing than eigenvalues and eigenvectors.
I’ve used HackerRank in the past, which has a similar in-browser coding process to solve a problem against test cases, but there the problems were organized into particular skills. I’ve been sticking to using the “random problem” button on LeetCode. Nothing wrong with either approach, just a difference.
I took way too long to realize there is a “Tree Visualizer” button in the “Testcase” console, which gives a nice rendering of the input tree.
sqlite3is also available. I used it for the design Twitter problem and the design underground system problem, but mostly just for the practice. You can provision an in-memory database using