Blog
Will Faught
January 2013
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
October 2012
While I worked at Microsoft, I heard that this video was made by someone who had worked for Microsoft. I haven’t verified that, though.
1 minute
Marco Arment: Personally, I’ve stopped buying extended warranties on almost everything, with the rationale that if I ever actually need to repair something out of warranty and it costs me a much larger amount of money than I would have been spending on extended warranties, I’ll start buying them from that point forward. Makes sense to me.
1 minute
The Name Of The New Small IPad
The name of the current big iPad suggests that the name of the new small iPad, rumored to be unveiled tomorrow, will be just iPad, not iPad Nano, iPad Air, iPad Mini, or iPad Junior. If Apple had named “the new iPad” iPad 3, then the new small iPad would have to be named something like iPad Something, iPad 3 Something, or iPad 4 to differentiate it; but they didn’t. What seems more probable is that Apple will adopt the naming convention of some of their other products, namely iPod, iMac, MacBook Air, and MacBook Pro, in which a family of related products all share the same name and are differentiated by a simple yet obvious characteristic like storage capacity or screen size: iPod touch 32/64 GB, iMac 24/27", MacBook Air 11/13", and MacBook Pro 13/15".
1 minute
Good lord: Password Length Minimum of 8 characters Maximum length of 40 characters What It Must Contain It must contain at least one character from three of the following lists: Uppercase Alphabetic (A-Z) Numbers (0-9) Lower case Alphabetic (a-z) These Special Characters are allowed: ! $ % & , ( ) - + - . / ; : < = > ? [ \ ] ^ _ { | } ~
1 minute
How To Download All ITunes Match Music Onto An IPhone With IOS 6
There’s no easy and obvious way that I could find to download all the songs in iTunes Match (previously purchased, matched, and uploaded) onto an iPhone with iOS 6. (The iTunes app can download only previously purchased songs. This may also apply to iPads.) The way to do it is to create a playlist of all your music, then scroll to the bottom and tap the download button. Simple, but not discoverable.
1 minute
April 2012
I stayed at the Chocolate Box Backpackers hostel for five more days. I was so tired and burned out that I kept mostly to myself and stayed inside. The weather was still wet and dreary, so I wasn’t missing out on much outside. I read the web, watched some movies, and otherwise relaxed. On Friday, March 2, I flew from Taipei to Seoul, and then a couple hours later I flew to Seattle, Washington.
grass valley sacramento seattle seoul south korea taipei taiwan travel usa
2 minutes
February 2012
Let myself sleep in until 1:30 PM. Went for lunch at Modern Toilet with the others in my dorm room at about 4:30 PM. Returned to my hostel to do laundry. Ate a late dinner at McDonald’s again. Played on my computer.
1 minute
Rode a tuk tuk from my hostel to the airport. Flew to Taipei with a layover in Kuala Lumpur. Rode a bus to Taipei Main Station. Rode the MRT to Guting station. Walked to my hostel and arrived around 9:30 PM. Ate dinner at a nearby McDonald’s (sorry, Tess). Met the others in my dorm room, English teachers from south of Taipei visiting for a long weekend. Played on my computer, then went to bed.
cambodia phnom penh taipei taiwan travel
1 minute
Called Tess to plan my flight to Seattle. Ate lunch at my hostel. Walked to a nearby ATM. Rode a motorbike taxi to the S-21 museum where thousands were detained and tortured for confessions by the Khmer Rouge. Afterward, rode a motorbike taxi to the killing fields just outside of town where thousands were murdered. It was so very sad. Rode a motorbike taxi back to my hostel. Bought a flight ticket to Taipei for the next day and booked a hostel I’d stayed at before, Chocolate Box.
1 minute
Checked out of my hostel. Wanted to call Tess, but my ride to the bus terminal was early. Rode a bus to Phnom Penh for six hours. Rode a tuk tuk to my hostel and checked in. Walked around the neighborhood a little, but there was little to see. Ate dinner at my hostel.
cambodia phnom penh siem reap travel
1 minute
Jake drove me to some of the smaller temples. I can’t recall which ones, but aside from small features, they were very similar. After seeing temples for two days under a blistering sun, they all started to look alike and I grew weary of it. Returned to the hostel and arranged for a six-hour bus ride to Phnom Penh the next morning.
1 minute
Ate breakfast at the hostel. Jake drove me in a tuk tuk to Angkor Wat, Banteay Kdei, Ta Prohm, The Bayon in Angkor Thom, and Phnom Bakheng, to the top of which I hiked for a sunset view. Needless to say, the temples there are exquisite and exciting to explore. My favorite was Angkor Wat, but The Bayon was a close second. I ate dinner at the same street place as the day before.
1 minute
Woke up at 4:30 AM. Flew to Siem Reap, Cambodia. Jake, from my hostel, picked me up at the airport. Checked in, showered, and ate lunch. Arranged a private tuk tuk for seeing the ruins the next day with Jake as my driver. Spent the rest of the day napping and relaxing. Ate dinner with another guy from my dorm named Robin (from Germany). Went to bed early to get up early the next day.
cambodia laos siem reap travel vientiane
1 minute
Saturday & Sunday, February 18–19, 2012
Didn’t do much. Again, I felt tired, and mostly remained inside and ate at nearby restaurants. One evening I walked to the Mekong River’s edge to see the night market there and watch the local people. Ran into a few more people from the group I was with at the river near Vang Vieng. Met a girl in my hostel that I’d met before at my hostel in Luang Prabang. Feeling the bandaid on my face was a constant reminder of the river, and I think it put me in a bad mood.
1 minute
Rode a bus to Vientiane at 10 AM. Walked around with a couple looking for a guesthouse or hostel. Checked into a hostel called Asian World. Ate a croissant for a late lunch and drank a couple Cokes to cool down. Read my guidebook about the city. Ate dinner at a pizza place and ran into a couple from the group I had hung out with at the river at Vang Vieng.
laos travel vang vieng vientiane
1 minute
Ate lunch at a Friends restaurant. Went to the inner tube shop, then rode a tuk tuk with a group of others, including two girls I’d met at my hostel in Chiang Mai, to the river. Hung out with that group there for an hour or so, drinking a beer. I’d heard stories about how dangerous it was inner tubing there, how people had died falling on rocks while riding zip lines over the river, or how inner tube riders had been hit by bottles attached to ropes that locals working at riverside bars throw at them to reel them in.
5 minutes
Still felt tired, so I stayed inside mostly and kept to myself. Ate lunch and dinner at restaurants that played Friends. I’d forgotten how funny Friends is.
1 minute
Moved my things to a private room at the Chilllaos hostel about a block away. Ate lunch at one of the restaurants playing the TV show Friends. Felt very tired, so I stayed in my room all day by myself. Ate dinner at the same place.
1 minute
The tour started at 11 AM. All four of us rode a private minibus to the three Plain of Jars sites. “Plain” is an exaggeration; “fields” is perhaps more fitting. The first site (called Site 3) was a five minute hike from a parking lot through some dry rice fields and rolling hills. Fortunately, the area had been cleared of land mines. I’d seen all I wanted to see after about five minutes.
laos phonsavan travel vang vieng
2 minutes
Rode a minibus to Phonsavan for six hours. Stopped at a small town on the way for lunch and ate with another guy from the minibus named Vincent. Shared a tuk tuk with Vincent and two girls from the Phonsavan bus terminal to the center of town where all the guesthouses are. Vincent and I shared a room with two twin beds. It was cheap, but the wifi sucked. We looked around at a couple of tourist agencies and all four of us finally booked a tour of the three Plain of Jars sites for the next day.
1 minute
Woke up earlier than I expected, at about 8:30 AM. Read my Laos guidebook about the northern area to plan where to go next. Decided to go to the Plain of Jars next, and then to the wild debauchery of Vang Vieng. Walked around town with my guidebook and saw all the temples that I had missed the day before. Met a couple novice monks, Joy and Sing, and talked with them for about an hour.
1 minute
My birthday! Let myself sleep in. Tried to call my parents, but the wifi wasn’t working. Walked into downtown and rented a bicycle for 10,000 kip. Rode around town looking at some temples. Stopped at a cafe for a Coke to cool off and use their wifi to call my parents and Tess. Continued riding around town and saw a a couple more temples. Returned the bicycle and ran into Matteo.
2 minutes
Rode a minibus with Aimee, Glenn, Nic, Sara, Dan, Sylvia, Michelle, and Ingo to the gorgeous Kuang Si waterfalls. Took lots of pictures, swam, swung on a rope and jumped off a small cliff into the icy blue water. Hiked up to all the different pools and falls. Got lost coming down the other side of the falls and ended up taking the long way back to the bottom of the falls.
1 minute
Ate another American breakfast and got a sandwich to go for lunch on the slow boat. Boarded at 8:30 AM and sat and waited for the stragglers to arrive. Departed around 9:30 AM. Sat with Aimee (from Austin, Texas) and we chatted for a while. I also read and listened to a couple podcasts and some music. The scenery was again very beautiful. This time my seat was much more cramped, but still the time passed quickly enough.
laos luang prabang pakbeng travel
2 minutes
No hot water for my shower, and there was a breeze from a fan when I turned on the shower light, so I skipped the shower except for a light rinse. Ate an American breakfast at the hotel’s restaurant. Shared a tuk tuk to the river boat pier at 9:30 AM. Boarded around 10 AM and sat waiting to depart for an hour or two as others trickled on board. Listened to podcasts the whole time and watched the beautiful landscape roll by.
1 minute
Awoke still sick with a bad back. Ate a cheap lunch at a local restaurant. Rode the bus to Chiang Khong at the Thailand–Laos border. Shared a tuk tuk with a guy to the Mekong river shore and exited Thailand. Bought passage across the river and landed on the Laos shore. Paid the fee and entered the town of Huay Xai in Laos. Walked up the hill and looked at a few places and chose to stay at a nice hotel with wifi and air con.
chiang rai huay xai laos thailand travel
1 minute
Woke up still feeling sick, and also felt like I had thrown my back out (the “mattresses” were really stiff). Showered, ate lunch, stayed in all day watching BSG, bought a bus ticket to Chiang Khong at the Thailand–Laos border, went out again for dinner, then returned to the hostel.
1 minute
Still sick and miserable. Slept in, showered, ate lunch, returned to my hostel and stayed inside all day, lying on my back watching Battlestar Galactica with my head angled up to reduce the running of my nose. Ate an expensive dinner at a pizza place nearby to try to cheer myself up.
1 minute
Awoke feeling sick again. Returned the scooter I had rented the day before. Checked out and rode a taxi truck to the Arcade bus terminal. Rode the bus to Chiang Rai for a few hours and listened to podcasts. Arrived and wandered around for ten minutes looking for my hostel. Checked in, ate lunch, then returned to my hostel and stayed inside on my bed the rest of the day feeling too sick to do anything.
chiang mai chiang rai thailand travel
1 minute
Rented a scooter and rode it to Doi Suthep. On my way back, I came across a scooter accident that had just happened. The driver was a man from Nebraska named Paul. He was in really bad shape. All the skin on his right knee cap had been scraped off and he was bleeding heavily from his right arm. He took an antibacterial wipe and a clotting pad from my first aid kit and some toilet paper I had to soak up the blood from his arm.
1 minute
Went to the Elephant Nature Park and fed and washed elephants all day. I didn’t realize the way elephants are trained to be ridden and do tricks is so brutal and inhumane. Returned to the hostel and planned my next few days. Craved McDonalds, so I ate dinner there. Watched some Battlestar Galactica.
1 minute
Rented a bicycle and headed for the interior of the old quarter. Stopped to east some street food for lunch. Saw several temples. Rode to a neighborhood outside the old quarter that supposedly was a nice place to shop, but was sorely disappointed. Returned to the hostel for a couple hours. Ate dinner nearby. Rode my bicycle to the night market a few blocks away and browsed the stalls there for an hour or so.
1 minute
Ate an American breakfast at a restaurant across the street. Rode the minibus to the Ko Phuket airport and arrived at 1:30 PM. Ate lunch at Burger King and then had four or so hours to kill. Drank some beers in a bar to use their free wifi. Flew to Chiang Mai at about 7:30 PM and arrived at about 9:30 PM. Rode a taxi to my hostel, A Little Bird Guesthouse, in the old quarter of the city.
chiang mai ko phuket krabi thailand travel
1 minute
Bought some lunch to go and put it in my day pack. Rode a long tail boat from Krabi to Railay East. Climbed to the vista point overlooking the Railay area. Ate my lunch while admiring the view. Tried to hike to a nearby lagoon, but it was too muddy. Walked to Railay West and went for a quick dip in the ocean and then laid on the sand and read for an hour or so.
1 minute
Rode the ferry in the morning to Krabi. Met a girl my age from England named Louisa who had been teaching English in South Korea. We were both going to the same hostel. Checked in. Planned what to do the next day. Walked to see a nearby temple. Walked from the temple to a nearby night street market for a delicious dinner of street food. Returned to the hostel for some quality computer time.
1 minute
Got up early and had the showers to myself. Walked to the travel agency where I’d booked the boat tour and bought some bananas on the way. Was led to the boat tour company office, then to the pier, then to the boat itself and boarded. The tour wasn’t organized as well as the Angthong Marine Park one, so we didn’t really know where the next stop was, or how they would signal us that the boat was leaving when everyone was snorkeling.
2 minutes