computation
Will Faught
August 2016
Why Some Diversity Thinkers Aren’t Buying Tech Industry’s ‘Pipeline’ Excuses
“Diversity thinkers”? Who comes up with that terminology? The pipeline is a valid argument because that’s exactly what’s happening. Anyone who disagrees ought to first take a look in the mirror: have you ever bought your kid a gender-specific toy? A doll for a girl? An action figure for a boy? Because if so, that’s the problem right there. The problem is you. The problem is social. The problem is parents holding their girls back by only giving them “girly” things.
coding computation computer science computers computing feminism npr planet money programming tech technology
1 minute
May 2013
Signatures For Built-In Python Methods
Ian Kelly: Methods implemented in C don’t really even have established argument specs. They just take tuples and dicts and use the PyArg_Parse* family of functions to unpack them. So effectively, all built-in methods have the argspec (self, *args, **keywords) The signature for Exception.__init__ seems to be (self, *args).
1 minute
OS X Computer Name Is Not The Host Name
If you configure the OS X computer name in System Preferences, Sharing, Computer Name, but it’s not reflected by /bin/hostname, then execute sudo scutil --set HostName MYHOSTNAME and restart.
1 minute
Exit Status-Colored Bash Prompt
My PS1 and PS2 Bash prompts: function colorprompt { status="$?" bold="\[\033[1m\]" cyan="\[\033[1;36m\]" red="\[\e[0;31m\]" off="\[\033[m\]" if [ “$status” -eq 0 ] then export PS1="$bold$cyan$$off " else export PS1="$bold$red$$off " fi export PS2="$bold>$off " } export PROMPT_COMMAND=colorprompt The color of the prompt is cyan if the last exit status was zero, otherwise it’s red. I disliked having little space to type commands in deeply nested directories, and I’m usually the same user on the same machine, so I only have the prompt $ terminator.
1 minute
By default, there’s no meta key configured for OS X Terminal. For example, you can’t move backward one word in Bash. To configure the option key as the meta key, check “Use option as meta key” in Preferences, Settings, Keyboard.
1 minute
April 2013
I recently installed Homebrew on OS X and observed that the Homebrew binary path was added to the end of $PATH instead of the beginning, so even though I installed Python with Homebrew, python still resolved to the OS X version. Instead of fixing this in my ~/.profile with prepending the Homebrew path to $PATH, I edited /etc/paths and moved the Homebrew path to the first line. Now $PATH always has the Homebrew path first.
1 minute
March 2013
Some great software engineering job interview preparation materials.
1 minute
The beauty of XOR is that it’s commutative and doing the same XOR twice cancels it out: 1 XOR 0 XOR 1 = 0. 1 XOR 1 XOR 0 = 0. The solution to this problem is to XOR all the integers together: Given an unsorted integer array, where every integer occurs twice except one, which occurs once, find the single integer.
1 minute
Simulate A Die Roll With Coin Tosses
Given an unbiased coin toss function, implement an unbiased die roll function. You can’t. Here’s an incorrect solution: Toss the coin three times. There are eight possible outcomes. If you get one of the first six possible outcomes, then use that to represent the die roll. If you get the seventh or eighth possible outcome, then try again. This solution ignores the premise that the coin toss is unbiased, and thus it isn’t guaranteed to halt in the case that you keep getting the seventh or eighth possible outcomes.
1 minute
Stack That Tracks The Minimum Element
Java: class MinStack<E> { private Stack<E> elements = new Stack<E>(); private Stack<E> mins = new Stack<E>(); public void push(E element) { elements.push(element); if (mins.isEmpty() || mins.peek().compareTo(element) > 0) mins.push(element); } public E pop() { if (elements.isEmpty()) throw new EmptyStackException(); E element = elements.pop(); if (mins.peek().compareTo(element) == 0) mins.pop(); return element; } public E min() { if (mins.isEmpty()) throw new EmptyStackException(); return mins.peek(); } }
1 minute
Finding Overlapping Axis-Aligned Rectangles
An interesting algorithm for finding a pair of axis-aligned rectangles that overlap. See also sweep and prune on Wikipedia.
1 minute
Java: boolean contains(String string, String substring) { if (string == null || substring == null) throw new NullPointerException(); int sublength = substring.length(); if (sublength == 0) return true; int length = string.length(); if (length < sublength) return false; char[] cs = string.toCharArray(); char[] subcs = substring.toCharArray(); for (int i = 0; i < length; ++i) { if (cs[i] == subcs[0]) { int j = 1; while (j < sublength && cs[i + j] == subcs[j]) ++j; if (j == sublength) return true; } } return false; }
1 minute
Can You Make A Ransom Note From A Magazine?
Java: boolean ransom(String note, String magazine) { if (note == null || magazine == null) throw new NullPointerException(); if (note.length() == 0) return true; if (magazine.length() == 0 || magazine.length() < note.length()) return false; char[] cs = note.toCharArray(); Map<Char, Integer> m = new HashMap<Char, Integer>(); for (char c: cs) if (m.containsKey(c)) m.put(c, m.get(c) + 1); else m.put(c, 1); cs = magazine.toCharArray(); for (char c: cs) if (m.containsKey(c)) { int i = m.
1 minute
Java: boolean power2(int x) { return x != 0 && (x & (x - 1)) == 0; } A power of two must be greater than zero.
1 minute
Java: int atoi(String s) { if (s == null) throw new NullPointerException(); int length = s.length(); if (length == 0) throw new NumberFormatException(); char[] c = s.toCharArray(); int n = 0; boolean negative = c[0] == '-'; for (int i = negative ? 1 : 0; i < length; ++i) { if (!Character.isDigit(c[i])) throw new NumberFormatException(); n = n - 10 + (c[i] - '0'); } return negative ? -n : n; }
1 minute
Member Variables In Outer Class Scopes
Refer to member variables that enclose larger scopes by the class name to which they belong. For example, the following statement accesses the member variable of the class ShadowTest from the method methodInFirstLevel: System.out.println("ShadowTest.this.x = " + ShadowTest.this.x); Just learned about this. I guess it doesn’t come up often.
1 minute
Java: class Node { public int value; public Node left, right; public static boolean mirror(Node x, Node y) { if (x == null && y == null) return true; if (x == null || y == null) return false; return x.value == y.value && mirror(x.left, y.right) && mirror(x.right, y.left); } }
1 minute
Adrian Quark proving the Fisher–Yates shuffle is unbiased: Only later did I prove to myself that the current-or-later algorithm works. Think about the last element in an array of size n. What are the odds that it ends up at index 1? Obviously, 1/n. What about index 2? This is a bit trickier, since it’s a compound probability: we have to multiply the odds of not swapping with 1 by the odds of then swapping with 2, to find the probability of the element actually ending up at 2.
1 minute
Remember To Shut Down ExecutorService
Methods that take a java.util.concurrent.Executor might not know if it’s an ExecutorService, so you have to call ExecutorService.shutdown() yourself.
1 minute
Method Return Types Should Be As Specific As Possible
Josh Bloch: In one sense, return values should have the opposite behavior of input parameters: It’s best to return the most specific applicable collection interface rather than the most general. For example, if you’re sure that you’ll always return a SortedMap, you should give the relevant method the return type of SortedMap rather than Map. SortedMap instances are more time-consuming to build than ordinary Map instances and are also more powerful.
1 minute
February 2013
Rename Files To Their Checksums
Bash: #!/bin/bash if [ -z “$1” ] then echo “renamehash: must specify a source directory” exit 1 fi if [ -z “$2” ] then echo “renamehash: must specify a target directory” exit 1 fi fromdir="$1" todir="$2" if [ ! -d “$fromdir” ] then echo “renamehash: path $1 is not a directory” exit 1 fi if [ -e “$todir” ] then echo “renamehash: path $1 already exists” exit 1 fi mkdir -p “$todir” find “$fromdir” -type f -not -name .
1 minute
Software sanity tests are commonly conflated with smoke tests. A smoke test determines whether it is possible to continue testing, as opposed to whether it is reasonable. A software smoke test determines whether the program launches and whether its interfaces are accessible and responsive (for example, the responsiveness of a web page or an input button). If the smoke test fails, it is impossible to conduct a sanity test. In contrast, the ideal sanity test exercises the smallest subset of application functions needed to determine whether the application logic is generally functional and correct (for example, an interest rate calculation for a financial application).
1 minute
Why Java’s Object.wait/notify/notifyAll Must Be Synchronized
Best explanation I’ve seen yet of why Java’s Object.wait/notify/notifyAll must be synchronized on the same Object instance, by Chris Smith: wait() isn’t strictly guaranteed to do anything at all. Something called “spurious wakeups” might occur. That is, a call to wait() can return at any time without any good reason. So a good rule of thumb for using wait() is that you should consider it to be nothing but an optimization.
2 minutes
Strings in switch statements Binary number literals Integral literal digit group separators, e.g. 999_999_999 Generic type inference Catch statement handling multiple exception types
1 minute
Performance Numbers Useful To Software Engineers
Time in nanoseconds of common operations like system calls, context switches, forks, L1/L2 cache references, disk seeks, etc.
1 minute
January 2013
Longest contiguous subarray of a signed int array that sums to zero or greater: int[] longest(int[] a) { if (a == null) return null; int longestIndex = -1, longestLength = 0; for (int i = 0; i < a.length; ++i) { int sum = 0; int length = 0; for (int j = i; j < a.length; ++j) { sum += a[j]; ++length; if (sum >= 0 && length > longestLength) { longestIndex = i; longestLength = length; } } } if (longestIndex == -1) return null; int[] b = new int[longestLength]; for (int i = 0; i < longestLength; ++i) b[i] = a[i + longestIndex]; return b; } I realize there’s a similar O(n log n) algorithm by Jon Bentley, but I haven’t studied it yet.
1 minute
Binary Tree Sequentializations As Identities
The trace of a traversal [of a binary tree] is called a sequentialization of the tree. No one sequentialisation according to pre-, in- or post-order describes the underlying tree uniquely, but any combination of two types of sequentialisation does. Any two sequentializations of a binary tree can uniquely identify it, so you can directly compare those of any two binary trees to determine whether their structure and values are equal.
1 minute
Decide If A Binary Tree Is A Binary Search Tree
Java: Recursive solution 1: class Node { public Node left, right; public int value; private boolean first; private int previous; public boolean isBST() { first = true; return isBST(this); } private boolean isBST(Node n) { if (n == null) return true; if (!isBST(n.left)) return false; if (first) { first = false; previous = n.value; } else if (previous >= n.value) return false; previous = n.value; return isBST(n.right); } } Recursive solution 2:
1 minute
Java: class Node { public Node left, right; public LinkedList > traverse() { LinkedList<LinkedList<Node>> lists = new LinkedList<LinkedList<Node>>(); LinkedList<Node> list = new LinkedList<Node>(); Queue<Node> nodes = new LinkedList<Node>(); nodes.offer(this); int parents = 1, children = 0; while (parents > 0) { Node n = nodes.remove(); list.add(n); if (n.left != null) { nodes.offer(n.left); ++children; } if (n.right != null) { nodes.offer(n.right); ++children; } --parents; if (parents == 0) { lists.add(list); list = new LinkedList<Node>(); parents = children; children = 0; } } return lists; } } An even simpler solution:
1 minute
Java: int left = ...; int right = ...; int middle = (right - left) / 2 + left; Alternatively: int middle = (left + right) / 2; Proof: (right - left) / 2 + left = (left + right) / 2 right - left + left * 2 = left + right right + left = left + right The second method is much simpler to understand and compute.
1 minute
Convert A Sorted Array To A Binary Search Tree
Java: class Node { public Node left, right; public int value; public static Node bst(int[] a) { if (a == null || a.length == 0) return null; return build(a, 0, a.length - 1); } private static Node build(int[] a, int left, int right) { if (left > right) return null; int middle = (left + right) / 2; Node n = new Node(); n.value = a[middle]; n.left = build(a, left, middle - 1); n.
1 minute
Java: class Node { public Node[] adj; public boolean isPathTo(Node target) { if (target == null) return false; Stack<Node> s = new Stack<Node>(); HashMap<Node, Node> m = new HashMap<Node, Node>(); s.push(this); while (!s.empty()) { Node n = s.pop(); m.put(n, n); for (Node n2 : n.adj) { if (n2 == target) return true; if (n2 != null && !m.containsKey(n2)) s.push(n2); } } return false; } }
1 minute
December 2012
Decide Whether A Binary Tree Is Balanced
Java: class Node { public Node left, right; private static int height(Node n) { if (n == null) return 0; return 1 + Math.max(height(n.left), height(n.right)); } public static boolean isBalanced(Node n) { if (n == null) return true; if (Math.abs(height(n.left) - height(n.right)) > 1) return false; return isBalanced(n.left) && isBalanced(n.right); } }
1 minute
Java: public class Tower { private int number; private Stack<Integer> disks = new Stack<Integer>(); public Tower(int number) { this.number = number; } public void add(Integer i) { if (!disks.empty() && i >= disks.peek()) throw new IllegalArgumentException(); disks.push(i); } private void moveTop(Tower to) { Integer i = disks.pop(); to.disks.push(i); System.out.println("Moved " + i + " from Tower " + number + " to Tower " + to.number); } public void move(int n, Tower to, Tower temp) { if (n <= 0) return; if (to == null || temp == null) throw new NullPointerException(); move(n - 1, temp, to); moveTop(to); temp.
2 minutes
A Stack Implemented With Two Queues
Java: public class DoubleQueueStack<E> { private LinkedList<E> store = new LinkedList<E>(), other = new LinkedList<E>(); public void push(E e) { store.offer(e); } public E pop() { if (store.isEmpty()) throw new IllegalStateException(); E e = null; while (!store.isEmpty()) { e = store.remove(); if (store.isEmpty()) break; other.offer(e); } LinkedList<E> t = store; store = other; other = t; return e; } public boolean isEmpty() { return store.isEmpty(); } }
1 minute
Java: static void shuffle(T[] a) { Random r = new Random(); for (int i = a.length; i > 1; --i) { int j = r.nextInt(i); T t = a[i - 1]; a[i - 1] = a[j]; a[j] = t; } }
1 minute
A Queue Implemented With Two Stacks
Java: public class DoubleStackQueue<E> { private Stack<E> enqueue = new Stack<E>(), dequeue = new Stack<E>(); private void move(Stack<E> from, Stack<E> to) { while (!from.empty()) to.push(from.pop()); } public void enqueue(E element) { if (!dequeue.empty()) move(dequeue, enqueue); enqueue.push(element); } public E dequeue() { if (isEmpty()) throw new IllegalStateException(); if (!enqueue.empty()) move(enqueue, dequeue); return dequeue.pop(); } public boolean isEmpty() { return enqueue.empty() && dequeue.empty(); } }
1 minute
The Fallacies Of Distributed Computing
The network is reliable. Latency is zero. Bandwidth is infinite. The network is secure. Topology doesn’t change. There is one administrator. Transport cost is zero. The network is homogeneous.
1 minute
November 2012
Alex Munroe: Now imagine you meet millions of carpenters using this toolbox who tell you “well hey what’s the problem with these tools? They’re all I’ve ever used and they work fine!” And the carpenters show you the houses they’ve built, where every room is a pentagon and the roof is upside-down. And you knock on the front door and it just collapses inwards and they all yell at you for breaking their door.
2 minutes
July 2011
I’ve been learning some Ruby the past week or so. Some thoughts: Arrays seem to be lists. Ranges are needed because of eager evaluation. I like that anything defined can be changed later, even visibility or constants. I haven’t found a good explanation of blocks yet, but they appear to be first-class functions with some kind of iterator functionality grafted on. No homoiconic syntax. Abbreviated keywords (def). Yuck. No exposed class variables is a great idea.
1 minute
The Rise And Fall Of The Independent Developer
Rings true to me: And, of course, only large companies and publishers can bear these [patent and copyright infringement] costs. My fear is that It’s [sic] only a matter of time before developers find the risks and expenses prohibitive and retreat to the safety of a larger organization. We’ll be going back to square one. Over the years many of the top selling apps have been created by independent developers, starting with Steve Demeter and Trism at the App Store launch, and continuing to this day with titles like Tiny Wings by Andreas Illiger.
1 minute
Here is how I used to create new passwords: I picked a starting idea, free associated from that about five times until I had something suitably random and about the right length (8-10 characters), converted some of the letters to leet, capitalized a letter, and reversed the characters. For example, I could start with “pillow”: “pillow” makes me think of “bed”, “bed” makes me think of “sheet”, and “sheet” makes me think of “sunlight”.
1 minute
The Worse Is Better philosophy is simply iterative design: lay the foundation, erect some walls, and you’ll worry about putting on the roof later. Apple is notorious for doing this. See the iPhone. The one thing I disagree with Richard about is the diamond-like jewel scenario: “To implement it to run fast is either impossible or beyond the capabilities of most implementors.” My intuition says that’s wrong; at least, it’s not right in some cases.
1 minute
The visual representation of the switch widget for iOS 1-4 was ambiguous because the width of the draggable knob was about half of the overall width of the widget. When you look at it, it isn’t immediately clear whether the blue part is meant to signify the knob. Its new design in iOS 5 appears to have resolved this ambiguity by making the knob much narrower, and circular rather than rectangular.
1 minute
May 2011
How To Write Unmaintainable Code
Insidious and hilarious stuff: Randomly capitalize the first letter of a syllable in the middle of a word. For example ComputeRasterHistoGram(). Wherever the rules of the language permit, give classes, constructors, methods, member variables, parameters and local variables the same names. For extra points, reuse local variable names inside {} blocks. The goal is to force the maintenance programmer to carefully examine the scope of every instance. In particular, in Java, make ordinary methods masquerade as constructors.
2 minutes
Paul Graham: Good people can fix bad ideas, but good ideas can’t save bad people. It’s very dangerous to let anyone fly under you. If you have the cheapest, easiest product, you’ll own the low end. And if you don’t, you’re in the crosshairs of whoever does. But negative lessons are just as valuable as positive ones. Perhaps even more valuable: it’s hard to repeat a brilliant performance, but it’s straightforward to avoid errors.
1 minute
A Review Of The 1977 Turing Award Lecture By John Backus
By Edsger W. Dijkstra. I’ve never seen shit talking in scholarly criticism before: If that indication is correct, his objection is less against von Neumann programs than against his own clumsy way of trying to understand them. Some of that classic Dijkstra charm.
1 minute