code
Will Faught
September 2016
SQL Injection Can Compromise The OS
TIL that if your server has even one SQL injection vulnerability, the entire operating system can be compromised. Eye-opening!
code coding engineering hacking programming software sql
1 minute
August 2016
Go raised the bar for new language distributions: UTF-8 code Testing, benchmarking, and profiling built in Single command line tool Build tool that leaves code directories clean Package manager Package doc browser Standard code style and formatter Fast builds Language spec with grammar and thorough library documentation Uniform, batteries-included standard library Concurrency support and automatic parallelism, sync and atomic libs, race detector Interfaces, not inheritance Vendoring support Cross compilation Static linking only for simple deployments Tabs, not spaces No semicolon line terminators Trailing commas in lists to minimize diffs Static types Default values for uninitialized variables Built-in comparisons and hashing Safety (e.
code coding engineer engineering go program programming raise the bar software swift technology
1 minute
March 2013
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
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
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
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
January 2013
EPSBD is a mnemonic I use to remember five helpful approaches to solving algorithmic problems that I got from Cracking the Coding Interview by Gayle McDowell: Examplify: Derive rules from examples. To compute the angle between the hour and minute hands in a clock, first derive the rules for computing the angle of each hand separately, then derive the rule for computing the angle between the hands in terms of them.
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
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