I came across this interesting problem a few weeks ago, and I had a lot of fun thinking about it and solving it. In this post, I’ll cover:

  1. The problem statement
  2. Approaching the problem and coming to a solution
  3. Experimentally verifying the solution with an implementation
  4. A proof of the solution for theoretical verification
  5. Interesting things I found looking around after solving the problem

The Problem Statement

Write a function that returns a random node from a linked list of unknown length in O(1) space and O(n) time. (Finding a solution in O(1) time is not only algorithmically interesting, but is also realistic if the linked list is too large to fit in memory). You may only traverse through the linked list once (i.e. you can’t traverse it once to get the length of the list, then again to pick a node).

Read on →

I spend a lot of time thinking about how I can make the best use of my time, given my circumstances and where I am in life, and one of the most important things that I’ve had to think about is the division of time between school and entrepreneurship. Given that I’m passionate about entrepreneurship and deeply involved on campus, it would make sense for me to be spending much of my free time working on projects, generating ideas, and practicing entrepreneurship. After all, school is a wonderful time to work on a startup, because you don’t need to be making a salary, you have so many talented and ambitious peers, and in the worst case of your startup failing, you can always fall back to your schoolwork.

But this semester, I’ve made a deliberate effort to cut down on my projects and entrepreneurial activities in order to focus on schoolwork. I’ve thought a lot and there are many reasons why I’ve made this decision to focus more on schoolwork, and one of those reasons is that I believe entrepreneurship is nothing more than a means to an end, and not an end in itself, as many think.

Read on →