How will I measure my life?
For one of our assignments in Strategy, we were asked to answer the question: How will you measure your life? Clay Christensen wrote about this topic in the HBR.
I don’t have a damn clue on how I would go about measuring my life in any concrete fashion because I’m just not sure what a right measure would be, and even if realized, what the practical steps would be in living up to that measure. Will it be meditating ten minutes a day? Converting to a particular faith? Contributing to charity? Falling and staying in love? Right now, I just don’t know. But I do have some sense of how I don’t want to measure my life.
I used to tell myself that I won’t do something just for money, because that’s the advice I got from older people. But nobody ever does something just for money. Bob doesn’t work an extra 20 hours a week for that raise just so he can roll around in wads of cash – it’s probably because he wants to buy more stuff. Maybe a car, a TV, or a house. So I have nothing against money, and I find nothing wrong with making a lot of money. In many cases, it’s a good thing when people are willing to pay you for what you do. I just think I’ve found a better word than money: stuff.I see “stuff” as the set of all material things, including money. I don’t want my life to be measured based on my stuff. I don’t want my obituary to read, “Nobody liked him…but he did own a G6”. I don’t want others to value me based on what I own, and I don’t want to perceive myself to be any better or worse a human being based on what I have, whether it be a car, a job, or a degree. But at a more fundamental level, it’s not even about stuff. So perhaps its still not good enough of a definition. The love for stuff is a symptom, because even when a person is materially poor, she can still have a big ego.
The ego loves to create separation. It’s a constant I versus them, and I don’t want to measure my life based on how much better I am than everybody else. It’s difficult, especially growing up in a generation and society that treats so many things – school, sports, career – as a race. This practice of treating every activity as a competition and pegging every milestone with a certificate of achievement began very early. In first grade, back when I was in China, I remember feeling ashamed after scoring 99 on a math exam. Why? Because I assumed that everyone else got 100 (fairly common).
Even today, I know I’m constantly being evaluated and measured against others. The feeling of being just a number is especially strong in places where I don’t stand out and my ego is under threat. When neither my stuff nor my intellect differentiates me from everyone else. Sometimes I wonder if that makes me anti-capitalist. I don’t think so – at least not intellectually, because I value the benefits of competition. But emotionally, I’m like a socialist. I don’t want to be treated differently simply because I don’t make top ten in everything I do, and I don’t want derive happiness from thinking that I’m better than everyone else. I don’t just want to be humbled by people I perceive to be better than I am, because that’s easy. Cultivating humility is harder.
Boston Marathon
I strolled out in my flip flops that afternoon and heard cheers from flocks of students rooting at the twenty first mile mark of the marathon – Boston College. I really wanted to watch the marathon, so after having lunch with my friend Sam, we headed toward heartbreak hill. A while later, Sam suggested that we take the B-Line down into Boston and watch the race from the finish line. Why not? A more exciting view. Besides, I’ve never watched the marathon from downtown in my four years here, and I’ll be graduating this may. So what if I have homework due tomorrow? You have to live a little.
It was around 12:15 by the time we boarded the T, and nothing indicated anything out of the ordinary. Just under an hour later, we got off at Arlington, a couple of blocks from the finish line near Copley Square. Proud finishers, wrapped in Adidas foil covers, packed the station and were beaming ecstatically. Most of them were young, maybe in their twenties or thirties and looked European. We smiled and congratulated them as we squirmed our way toward the exit. Once we were out, Sam turns to me and says “Dude, I really need to use the bathroom”. He holds up his empty forty ounce cup. Great, I thought, more delay. We searched the area and chose to relieve ourselves at the Park Plaza Hotel, where we stayed for the next ten minutes. Little did we know, those minutes likely spared us from the tragedy that would unfold.
The moment we left the hotel, we spotted a female runner huddled by the entrance, yelling hysterically into her cell phone. “There were explosions”, she cried. “I think two. They just closed off the entire area”. My initial reaction was that she was crazy. I mean, we got here just a few minutes ago and the atmosphere was nothing but festive. Then I saw another runner walk by, head down and teary eyed. Another man was consoling a woman. That’s when we knew something was wrong. What the hell is going on? We scurried around asking people for information, but most of them were as clueless as we were. From the expressions on the faces of the runners who were just arriving, whatever just happened seemed grim. We stopped a couple of them, and learned that some accident had occurred near the finish line and that there were indeed explosions.
We spent the rest of the afternoon wandering around the perimeter of the area where the explosions took place. Most of Copley was closed off for investigation. Some suspected foul play, but at that point nothing was certain. What was certain was that some people were badly hurt. We decided to go back to the Park Plaza, where we found runners just loitering or checking in. In the lobby, People congregated around two large television sets that were broadcasting the aftermath of the incident. Two killed, over sixteen injured. Shit – it was worst than I thought. We started hearing all sorts of bad news from people around us – more bombs being diffused, the city being evacuated. This was clearly an attack. I’d be lying if I said I wasn’t scared.
The T was suspended, and taxi’s were nowhere in sight. I had no intention of spending the night at the hotel lobby, so we decided to return to campus on foot. It was going to be a long walk, but it was the only option. Two miles later, our stomachs were rumbling, so we stopped at a restaurant near Boston University to eat and recollect. Sam was still in disbelief, and kept repeating, “Man, I can’t believe this happened. We were so close”. Yeah, neither could I. The other time I’ve been near so much disarray was in New York on 9/11. I was in fourth grade then, so I didn’t know much. Things just seemed frantic. And for the most of my life, I’ve only been exposed to these tragedies through the news, many of which take place overseas. It never felt urgent, or even real.
As we were about to leave the restaurant, our waitress informed us that somebody reported another explosion at Kenmore station. Wait, what? We just passed Kenmore station. It was a block away. Are we in more danger? My mind was racing again. Luckily, it was just a rumor – just another one of many pieces of misinformation that got passed around that day. Thank goodness. When we stepped back out, we both saw an inbound train go by. It was around 7PM, and the T was back in service. There were only a few passengers when we got on, which was uncommon for that time of the day, and especially on marathon Monday. But we were finally going back home. Back to safety.
Tree Traversal Terminology
I was first introduced to trees in my data structures course two years ago, and to this day the definitions of the tree traversal methods still slip my memory. Why? I never bothered to understand the reason behind the terminology. After revisiting tree traversal, I’ve finally gotten that “aha” moment.
Preorder and Postorder
These apply to any kind of rooted tree, and the key to understanding the prefixes pre and post is knowing that they represent when the current node is visited. Is it before, or after?
In Preorder, we visit the current node before we visit its children. Think preview. Or pregame. You evaluate the one you’re looking at before recursing on its descendents. In Postorder, we visit the current node after we visit its children.
I propose that we refer to them as Prechildren and Postchildren.
Inorder
Inorder traversal only applies to binary trees. This is more intuitive than preorder and postorder because we’re simply visiting everyone in order, from left to right. We visit the left subtree, then the current node, and then the right subtree. Perfectly in order.
From an implementation side, each of the algorithms for inorder, postorder, and preorder would simply be different permutations of one another.
Levelorder
Levelorder is also fairly intuitive. We simply visit each level of the tree at a time. This means we start with the first generation, and then visit its children. And then its grandchildren. In graph structures, this kind of traversal is also known as breadth first traversal.
Cheers.
Near Impossible Projects
At the 2012 PyCon, Paul Graham presents a list of gigantic start up ideas, and posits the question “Why are most people afraid of starting projects that seem near impossible?” (rephrased). Sanity is the reason, he says. I agree, humans are risk averse. Near impossible just sounds terrifying. But the question seems to distort the reality of how big projects come about; building the next Apple sounds near impossible, but Apple didn’t start as Apple. Of course, Paul Graham understands this better than anyone – I just disagree with the question choice.
Although there’s definitely a fear of starting huge projects, there’s also a dearth of individuals with the right vision and experience to execute on small ideas with big potential. Heck, even if you simplified the problem domain of a great idea for me and handed it to me on a silver platter, I may still be blind to the opportunities. We can all nod our heads and agree that getting a billion people to join a social network is a near impossible, albeit lucrative idea. But if I was in college in 2004, and someone told me to build a better social network for my school, I don’t know if I would’ve done it. I mean, everyone used Myspace.
SimpleDB Checkpointing Schemes
SimpleDB uses one of two checkpointing schemes for recovery management: quiescent and non-quiescent checkpointing. In this post I’m going to talk about the advantages and disadvantages of both, and how we can do better. If you’re not familiar with checkpointing, here’s Microsoft’s definition:
A checkpoint creates a known good point from which the SQL Server Database Engine can start applying changes contained in the log during recovery after an unexpected shutdown or crash.
Although I’m not using a commercial database system here, I believe we can extract general principles from the SimpleDB implementations that are also applicable to large scale databases. Here are the two algorithms for the two methods from my professors awesome database book.
Quiescent Checkpointing
1. Stop accepting new transactions
2. Wait for existing transactions to commit
3. Flush all modified buffers
4. Append a quiescent checkpoint record to the log and flush it to disk
5. Start accepting new transactions
Nonquiescent Checkpointing
1. Stop accepting new transactions
2. Let T1,…,Tk be the currently running transactions
3. Flush all modified buffers
4. Write the record <NQCKPT, T1, …, Tk> into the log
5. Start accepting new transactions
The difference between the two schemes is that in quiescent checkpointing, the database has to wait for all existing transactions to finish. Hence the word “quiescent”, since this forces the system into a dormant state. This is wasteful, and therefore unscalable. Nonquiescent checkpointing does slightly better. Instead of waiting, it creates a list of all active transactions. This way, it only needs to recover up to the last uncommited transaction during recovery.
But wait, they’re both still not very efficient because they both have to stop accepting new transactions!
That sucks. Why is that necessary?
In quiescent checkpointing, if they didn’t stop accepting new transactions, the checkpoint may never be written. Many transactions could be running, and if the database has to wait for every transaction to complete (which could be a long time), it really defeats the purpose of checkpointing.
For the nonquiescent checkpointing scheme, it’s a little less obvious why the database needs to refuse new transactions and it took me a little longer to figure out the reason. The problem arises when a new transaction does not wound up in our list of active transactions during the checkpointing process. Lets look at what happens.
1. Start checkpoint. Assume TX’s 1, 2, and 3 are our list of active transactions.
2. TX 4 starts (new transaction) and makes changes. Does not end up in list.
3. TXs 1, 2, and 3 commits.
4. Buffers are flushed and our checkpoint record is finally written to the log and flushed to disk. Keep in mind that the checkpoint does not contain TX 4.
5. System crashes and TX 4 does not commit.
What are the consequences of this? The recovery will simply halt at our checkpoint record because it will be empty because it knows that all the active transactions listed in the checkpoint have already committed. This means TX 4, which comes before the checkpoint record, will not be undone, hence leaving the database in an inconsistent state.
But there is a way to solve this issue without having to settle with refusing new transactions. The solution is surprisingly simple, and only requires one small change. When starting the checkpointing process, immediately write a checkpoint BEGIN record. And during recovery, undo up to the BEGIN record regardless of what the last uncommitted transaction is. How does this solve our problem? If a new transactions starts during the checkpoint process, it will come after the BEGIN record. But since the database recovers up to the BEGIN record no matter what, the new transaction will be accounted for!
Implementing Min-Heap Sink Method
One of the great things about software is that it is constantly evolving. Recently I had the pleasure of seeing a section of my binary heap (min-heap) implementation change and improve with each refactoring. I find the sink() method of a binary heap to be the most difficult part to implement, because although it’s simple conceptually, it’s easy to make small mistakes such as failing to check for null cases. Here was my first stab at it (NSFW).
int lk = k * 2 + 1, rk = lk + 1;
MyKey lv = null, rv = null;
if(lk < size) lv = heap[lk];
if(rk < size) rv = heap[rk];
while((heap[k].compareTo(lv) != -1 || heap[k].compareTo(rv) != -1) && (lv != null || rv != null)){
if(lv != null){
if(lv.compareTo(rv) == -1 || rv == null){
swap(k, lk);
k = lk;
}else{
swap(k, rk);
k = rk;
}
}else{
swap(k, rk);
k = rk;
}
lv = null;
rv = null;
lk = k * 2 + 1;
rk = lk + 1;
if(lk < size) lv = heap[lk];
if(rk < size) rv = heap[rk];
}
The code is filled with null and boundary checking because
1) If we reach a leaf that is towards the end of our heap, trying to get its children will result in null pointer exceptions
2) We can’t stop the iteration until we know that we are at a leaf node (no children).
It didn’t occur to me until much later that both problems could be solved simply by realizing that the binary heap adds nodes in a level-order manner. And we never need to visit the leaf nodes anyway, because the farthest we need to sink is to the last parent of the leafs. This resulted in the following:
while(k < size/2){
int c1 = 2*k + 1;
int c2 = c1 + 1;
if(less(c1,c2)){
if(heap[k].compareTo(heap[c1]) == -1)
break;
else{
swap(k, c1);
k = c1;
}
}else{
if(heap[k].compareTo(heap[c2]) == -1)
break;
else {
swap(k, c2);
k = c2;
}
}
}
Okay, that’s much better. But there’s still a lot of code duplication. In both the IF and the ELSE, I’m checking if the parent is smaller than the child (if so, we break). But this can be avoided if we simply set the child first.
while(k < size/2){
int j = 2*k + 1;
if(!less(j, j+1)) j++;
if(heap[k].compareTo(heap[j]) == -1) break;
swap(k, j);
k = j;
}
Pretty nice. We set j to be the index of the first child – and if it’s not less than the second child, we increment j. This way, the comparison can just be applied to j.
Cracking the Coding Interview: Improvements to Problem 11.3
I completed another sorting question in Gayle’s book, Cracking the Coding Interview. In this post I’m going to walk through my initial solution to the question, and then show you Gayle’s solution as well as an improved version of the solution.
Here’s the question:
Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.
If you’ve read the book before, then you might be reminded of question 1.8 in chapter 1. If it does, then you’ll know exactly what rotation means. Otherwise, you’ll probably need to mess around with a few examples before it clicks.
When I first read this question, I thought about binary search. Although that was the right direction, I struggled on how to exactly implement binary search on an array that wasn’t completely ordered. So I started by applying binary search to some examples in order to glean some insight on how I could modify it to work.
First I made an ordered array
[1, 3, 5, 7, 8, 24, 31, 33, 50]
Then I made several rotations of it.
a: [33, 50, 1, 3, 5, 7, 8, 24, 31]
b: [7, 8, 24, 31, 33, 50, 1, 3, 5]
c: [33, 50, 1, 3, 5, 7, 8, 24, 31]
A couple of key realizations emerged after doing this exercise:
1) No matter how the array is rotated, there are always two sides with a minimum and a maximum.
For example, in rotation a, the sides are:
[33, 50] and [1, 3, 5, 7, 8, 24, 31]
Now, rotating it will simply increase one side and decrease the other. The numbers will always be sorted on both sides.
2) By applying binary search, I can guarantee that an element is on one side if I’m lucky enough to pick a left and a middle element that are within the bounds of that side.
For example, using rotation b. My left most element will be 7, and my middle element will be 33. This means if the number I’m searching for is in between 7 and 33, I just have to search the left side. Otherwise, I must search the right.
This led to my next insight, which is that if that middle element is smaller than the left most element, then we can check if our target is within the bounds of the right side! If you look at rotation c, the left most element is 33 and our middle element is 5. That means any element before five is either smaller than 5 or greater than 33. Doesn’t tell us much. On the other hand, any element after five MUST be smaller than 33. Therefore, we can check the right – and if it’s not there, then it must be on the left.
There is one more case that I got wrong in my initial solution – the case of duplicates. Gayle does a nice job explaining this special case, so I won’t go into it.
Here was my initial, (somewhat) janky solution:
Issue # 1: As you’ll probably notice, I have extra if statements like if(x == a[l]) to avoid having to recurse if our element happens to match either one of the sides. This might reduce the number of recursive calls but it’s unnecessary because line 5 is essentially the base case, and it makes the code much more unreadable. If I was really concerned with these pre-checks, I might as well hard-code in checks for left, center, and right at the very top.
Issue # 2: The case for duplicate elements is actually broken. I made the assumption that if the center element is the same as the left most element, then the entire left side must be the same. Wrong. That is only true IF the center element is also different from the right most element. Why? Because that means numbers must be increasing on the right up to the value of the left most element (at most). Otherwise, we’re not really sure which side to visit. Heck, the value could be hanging out on either the left or right side. Gayle’s solution take’s care of this.
This is the correct solution, but the biggest issue with this code is redundancy. For example, the IF statement on line 21 is unnecessary.
if(a[mid] != a[right])
return search(a, mid + 1, right , x);
Regardless of whether the middle is the same as the right, we will need to search the right side. This can be expressed if just one IF, which checks if the right returns -1. And if so, we’ll check the left.
Here is the improved version of the code:
Java Sorting by Extending Comparator
I’m doing problems in the sorting chapter, and I came across a very neat technique for applying a custom comparison while using any standard sorting algorithm.
Here’s the question:
Write a method to sort an array of strings so that all the anagrams are next to each other.
My initial solution was to used a modified version of bucket sort by first sorting the individual strings (keys), and mapping them to their unsorted values. This takes O(n) time and space.
I also thought about applying a modified quicksort to the problem – but I ended up not pursuing that route because I assumed that would involve writing quicksort and then replacing the comparisons with String.compare()’s, and I wasn’t too pumped to write quicksort. Furthermore, the sort is at best O(n log n) time.
Little did I know, I had completely forgotten about Java’s Comparator interface, which could be accepted as an argument in the sorting implementation of the Arrays utility class.
sort(T[] a, Comparator<? super T> c)
Sorts the specified array of objects according to the order induced by the specified comparator.
More about the sorting implementation :
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance.
Here’s my solution to the bucket sort approach.
More Dynamic Programming Awesomeness
So I just did another dynamic programming question in Gayle’s book that I think is worth sharing. Here’s the question:
A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.
Initially, I took a bottom up approach to this question by drawing a tree of all the possible steps.
(1 2 3)
(1 2 3) (1 2 3) (1 2 3)
(1 2 3) 1 …
My initial recursive function, in pseudo code, was this:
fun(array, sum){
if(sum > target) return 0;
if (sum == target) return 1;
return fun(array, sum + 1) + fun(array, sum + 2) + fun(array, sum + 3);
}
The problem with this was that I had no clue how to implement dynamic programming to improve the algorithm. By using a base-case and build (bottom up) approach, I couldn’t make use of caching because the paths associated with each value constantly change depending on where they are in the call stack. And without dynamic programming, the run time is just too slow.
The other alternative is to take a top-down approach, which involves breaking a larger case into sub-cases so that the solutions for the smaller cases. This is the right approach, because the smaller cases can be cached for subsequent calls.
Here’s my pseudo code.
fun(target){
if(target < 0) return 0;
if(target == 0) return 1;
return fun(target - 1) + fun(target - 2) + fun(target - 3);
}
Sadly, this also runs in exponential time. But because this is a top-down recursive function, I can use dynamic programming. Notice how it looks nearly identical to the inefficient fibonacci function from my last dynamic programming post, which is no surprise given that by solving for N-1, you’ve essentially solved for N-2 as well as N-3.
Next is to make use of caching so the function doesn’t create duplicate call stacks for its second and third recursive calls. There were a few things I did that helped me arrive at the solution:
1) Drawing out the call stack. This helped me visualize how the values were changing throughout the function life time.
2) Asking the question – How do I avoid having to recurse on the same value? Answer: If I know the total number of paths associated with the value.
3) Naturally, following question #2, I tried figuring out a way to cache the first base-case result, which is when our target value reaches 0. This means that when target = 1, there is exactly one path to the top of the stair case. What about when target = 2? Oh, well, then we can use 1′s cached value. The solution becomes pretty clear at this point.
Here’s the final algorithm in pseudo code:
fun(target){
if(target < 0) return 0;
if(target == 0) return 1;
if(cached target) return cached target value;
cached target = fun(target - 1) + fun(target - 2) + fun(target - 3);
return cached target;
}
Speeding up Fibonacci runtime using Dynamic Programming
I recently came across a great example of using dynamic programming to speed up an unnecessarily inefficient recursive solution in the book Cracking the Coding Interview. I’d thought I share it because it involves a common programming example and the modification yielded a significant improvement.
Gayle presents an example of a simple fibonacci function – probably the least efficient one.
int fibonacci(int i) {
if (i == 0) return 0;
if(i == 1) return 1;
return fibonacci(i - 1) + fibonacci(i - 2);
}
Problem with this is that once fibonacci(i-1) returns with the result, fibonacci(i-2) is going to execute and create an identical call stack.
For example:
Let i = 6
Our call LEFT call stack will look like this:
(6)
(5 4)
(4 3) (3 2)
(3 2) (2 1) (2 1) (1 0)
In other words, in this implementation, for each value in N that recurses on the left, N-1 will recurse on the right. Now, the same thing happens on the RIGHT side with i = 5. This means we’re essentially duplicating the same calls twice on each side. Which also means if I increase i by 1, we’re doubling our call stack. Hence the time and space complexity of this function is O(2^n).
Before I reveal Gayle’s solution, could you think of a way to improve this algorithm? Hint: caching.
The two key things to recognize here are
1) Calls are getting repeated
2) Left sided calls are repeated by the right
From this, we can devise a general algorithm using dynamic programming. In pseudo code,
fib ( i ) {
if (i has been called)
return the cached result
else
calculate and cache the result
return the result
}
Lets test this using i = 6.
(6)
(5 4)
(4 3) (3 2)
(3 2) (2 1) (2 1) (1 0)
(2)
(1 0)
The black denotes the call stack from the left recursion. The blue represents the base case values. As you can probably tell, for each value that gets visited on the left, the result is cached. Hence, all the subsequent calls from the left (gray) simply return the cached value. This makes the time and space complexity O(n).
#winning