Skip to content

Instantly share code, notes, and snippets.

Buck Shlegeris bshlgrs

Block or report user

Report or block bshlgrs

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
View animal rights survey
--- This survey is made with GuidedTrack.
*question: Which of the following comes closest to your view about the treatment of animals?
Animals deserve the same rights as people to be free from harm and exploitation.
*question: Is there anything you want to clarify about that answer?
*type: paragraph
>> same_rights_as_people = 1

I often see people get confused by binary search tree balancing. This is very fair, because all the algorithms to make it work are quite complicated, and understanding them deeply is a lot of work.

But the misconceptions I see are often not about the mechanics of BST balancing, which are legitimately really complicated, but about the motivation and goals of these mechanisms. So I’ve written a few brief notes here in the hope that they let people understand what BST balancing mechanisms are supposed to do.

The key selling point of a BST is that it has O(log(n)) search and modification. The O(log(n)) here comes from the height of the tree. So we just require that the height of the tree doesn’t grow to more than a constant factor of the logarithm of the number of nodes.

Two common balancing mechanisms are AVL trees and red-black trees. In a red-black tree, the maintained invariant is that the paths from the root to a leaf can’t differ in length by more than a factor of two. So it’s fine for your left subtree

View parallel

Avoid parallel arrays.

If you want to represent a bunch of people who have names and ages, it’s cleaner to do

let people = [{name: “Buck”, age: 23}, {name: “Daniel”, age: 25}] 


let names = [“Buck”, “Daniel”];
let ages = [23, 25];
View theorem

Here’s more detail on what I want to be able to do. I want to be able to write class hierarchies and reason about what properties are possible for objects which have particular classes. I have no idea whether something like this exists.

abstract class Animal {
  def makeNoise(): String
  def numberOfLegs: Int

abstract class Insect extends Animal {
View nginx.conf
server {
listen 80; ## listen for ipv4; this line is default and implied
location /dice/ {
location /music-game/ {
bshlgrs / threadlocals_are_a_lie.c
Last active Oct 13, 2016
This is a demonstration that threadlocal storage can be written to by other threads.
View threadlocals_are_a_lie.c
#include <pthread.h>
#include <stdio.h>
__thread int very_local = 5;
/* this function is run by the second thread */
void *do_other_thing(void *very_local_pointer)
printf("in thread 2, very_local is %d\n", very_local);
*(int*) very_local_pointer = 10;

Evaluating lifestyle interventions to reduce environmental impact

Summary: I investigated a variety of possible pro-environment actions, and concluded that none of them were worth my time. I don’t think that any pro-environmental actions are as time/money efficient as giving to the best climate change charities, and I don’t think that those climate change charities are anywhere near the best human-oriented charities we currently have available as donation targets. I briefly consider non-direct effects of pro-environmental actions.

People often tell me I should care about the environment, and take steps to protect it. I’m on board with that in principle. However, before I spent a few hours researching this, I had no idea of how to judge how much environmental damage is caused by different things I’m doing, and which supposedly environmentally friendly measures I should bother taking.

For example, I’m aware that


list of programming project ideas

Board games

Any two player board game is a good exercise for basic programming logic, and you can make it into a console application. Checkers, Connect-4, Othello, Poker, Go, whatever. Chess is somewhat harder than those other games.

Here are some ways to extend these projects:

  • Add the ability to save and load games
  • Add an AI
View select_across_sorted_arrays.rb
# Returns the number of items in arr smaller than x.
def rank(arr, x, start_idx = 0, end_idx = nil)
return 0 if arr.empty?
end_idx = arr.length if end_idx.nil?
# this makes sense I promise, I'll explain later
return arr.length if start_idx == arr.length
return 0 if end_idx == 0
View data structure project

fun data structure projects

  • Binary search trees! There are lots of little-known self-balancing BST implementations. Basically no-one has heard of any except AVL trees, red-black trees, and BTrees.
    • Implement a lesser-known BST in a language of your choice; figure out how fast it is; try to make it as fast as a reference implementation. Try to find a semi-realistic application where your implementation is faster than a competitor. (For example, splay trees probably outperform red-black trees in cases with serious temporal locality.) This project is definitely possible.
You can’t perform that action at this time.