Skip to content

Instantly share code, notes, and snippets.

Alex Bowe alexbowe

View GitHub Profile
@alexbowe
alexbowe / tree_iterators.py
Last active Apr 14, 2019
Method to simplify many programming interview tree questions.
View tree_iterators.py
'''
Interview hack: Memorize preorder/inorder/postorder tree ITERATORS (no recursion) and their reverses.
It simplifies a disproportionate number of questions to simple for loops (see below).
I consider the implementations below the simplest way to memorize the iterative tree traversal algorithms,
because they are so similar to each other, and to their respective recursive versions.
Notes:
- We only visit a node after we have expanded its children (i.e. added them to the stack) in the desired order.
- `x is curr` does the expanded flagging for us, because we always expand the current node.
@alexbowe
alexbowe / tweet_finder.py
Last active May 17, 2017
Find the Nth Tweet from your Twitter archive .csv file
View tweet_finder.py
# To run, from shell type: python tweet_finder.py
# Must be run in the same directory as the downloaded csv file.
import csv
# Modify this number if you want a different nth Tweet
# Should be 1-based (i.e. first tweet is the 1th, not 0th)
num = 40000
# Change the path if you want to run it from a different directory
path = "tweets.csv"
@alexbowe
alexbowe / 750kotoba.html
Created Jan 11, 2014
Example of using TinySegmenter.js to tokenize Japanese and provide the word count of the input from a textbox.
View 750kotoba.html
<!DOCTYPE html>
<html>
<head>
<!-- http://chasen.org/~taku/software/TinySegmenter/ -->
<script type="text/javascript" src="tiny_segmenter.js" charset="UTF-8"></script>
<script>
var segmenter = new TinySegmenter();
function countWords() {
s = document.getElementById("inputText").value;
@alexbowe
alexbowe / int_mapper_one_liner.py
Created Aug 17, 2013
A shorthand way to get a unique integer mapper in Python
View int_mapper_one_liner.py
# here is a tidy way to get a hashable object (such as a word) to map to a unique int in python
from collections import defaultdict
mapper = defaultdict(lambda: len(mapper))
mapper["hello"] # 0
mapper["world"] # 1
mapper["and"] # 2
mapper["hello"] # 0
mapper["alex"] # 3
@alexbowe
alexbowe / funky_typedef.c
Last active Dec 20, 2015
C function pointer typedef example (for nicer variable declarations).
View funky_typedef.c
/*
I have read a bunch of posts about function pointers,
such as http://denniskubes.com/2013/03/22/basics-of-function-pointers-in-c/
but I rarely see this *one weird trick*.
It is C's (admittedly clunky) syntax for typedefing a function pointer of a given signiature.
Hide the clunkiness in the typedef to keep your code tidy and maintainable.
*/
#include <stdio.h>
@alexbowe
alexbowe / composite_rank.py
Created Jul 28, 2011
Ranks k-composites that sum to n
View composite_rank.py
def gam_to_lam(c, n):
i, m = 0, 0
L = [0] * n
while 1:
i = i+1
if c[i-1] > 0:
for j in range(1, c[i-1] + 1):
m = m + 1
L[m-1] = i
@alexbowe
alexbowe / gist:951513
Created May 2, 2011
Computing Theory Question
View gist:951513
The following is an interesting problem I found in the book Introduction to Computer Theory (2nd edition),
by Daniel Cohen, Wiley, 1997. See what you think ...
“ In the English language, we can observe that some adjectives apply to themselves. For example, the word
“short” is a fairly short word. We mighy say, “short” is short. Also, the adjective “polysyllabic” is indeed
polysyllabic. Some other possible adjectives of this type are “unfrequent”, “melodious”, “arcane”,
“unhyphenated”, “English”, “non-palindromic”, and “harmless”. Let us call all these adjectives that describe
themselves homothetic. Let us call all other adjectives (those that do not decribe themselves) heterothetic.
For example, the words “gymnastic”, “myopic”, and “recursive” are all heterothetic adjectives The word
“heterothetic” is an adjective, and therefore like all adjectives it is either homothetic or heterothetic.
@alexbowe
alexbowe / streams.py
Created Apr 23, 2011
Lazy functional style streams for Python
View streams.py
null_stream = (None, None)
def map(f, stream):
if stream is null_stream: return null_stream
return (f(head(stream)), lambda: map(f, tail(stream)))
def reduce(f, result, stream):
if stream is null_stream: return result
return reduce(f, f(result, head(stream)), tail(stream))
@alexbowe
alexbowe / gist:907073
Created Apr 7, 2011
15bit popcount from Hacker's Delight, p. 72
View gist:907073
//Special for 15-bit values on 64bit processors
//with fast multiplication
//From Hacker's Delight, p. 72
inline uint32_t popcount15(uint32_t x)
{
uint64_t y;
y = x * 0x0002000400080010;
y = y & 0x1111111111111111;
y = y * 0x1111111111111111;
y = y >> 60;
@alexbowe
alexbowe / popcount.erl
Created Apr 4, 2011
Popcount table generated at compile-time using ct_expand. See https://gist.github.com/901235
View popcount.erl
-module(popcount).
-compile({parse_transform, ct_expand}).
-compile({popcount_table}).
-export([popcount16/1, popcount32/1]).
-define(TABLE(B), ct_expand:term( popcount_table:gen_table(B) )).
-define(TABLE16, ct_expand:term( ?TABLE(16) )).
popcount16(V) -> erlang:element(V+1, ?TABLE16).
popcount32(V) -> popcount16( V band 16#ffff )
You can’t perform that action at this time.