Are programming competitions a good use of time?

10 minutes remaining in the contest, but you’re still a few points short of advancing. Armed with your mighty coding powers, the first three problems fall quickly, but problem 4 is proving a tough nut to crack. After four incorrect attempts, your time is running short, and you’re searching desperately for an off-by-one error, an edge case you haven’t considered.

You read the problem statement one more time, and at last, you find it. An integer overflow bug. With a wide grin, you fix the bug with a few quick keystrokes. You upload the source code file…

1

Accepted! You sit back, feeling both relieved and elated. With the addition of 25 points, your advancement to the next round is now guaranteed.

It’s not hard to see why programming contests are so appealing — this is programming distilled to its essence. No need to figure out how to integrate an unfamiliar API, or refactor code to be unit testable, or make sense of vague business requirements. In competitive programming, each problem has a self-contained, algorithmic solution, and an automated judge instantly determines if it’s correct or not.

2Above: Programming contests contain the same types of problems as technical interviews at companies like Google.

Competitive programming promises even more glory. Win enough contests, and you get an interview at Facebook or Google, where they ask you… you guessed it… more algorithm coding questions!

By doing programming contests, you gain an intimate understanding of data structures and algorithms and their complexities. While your colleagues vaguely know the difference between a depth-first versus a breadst-first search, you develop a much deeper intuition. You will never forget that one contest where you used DFS instead of BFS, causing your solution to time out.

Unlike the real world, competitive programming offers an arena of pure meritocracy. As long as you solve difficult problems fast, you will surely rise through the ranks. In the Google Code Jam, thousands of programmers try their luck in the qualifying round, but this number is reduced to 3000 by Round 2, and 500 by Round 3. Then for the grand finale, the top 25 elite coders are flown in to compete on-site in the world finals.

3Above: 25 of the world’s best compete in the Google Code Jam world finals.

I used to look up in awe at red coders (the highest rated users have red usernames). By the time I solved the first problem, they would have not only solved it in 10 minutes, but also solved 2-3 even harder ones. What was it like to think at that level, to possess that much coding wizardry?

And for some time, I strove to be like them. I studied my dynamic programming and graph algorithms in my spare time, and practiced on SPOJ and Hackerrank and Codeforces. I competed in my university’s ACM tryouts, and three times failed to qualify for the ACM team. So it goes.

In the last few years, I got to talk to a lot of competitive programmers, most of whom were far better than myself. Perhaps I was searching for some magical quality that gave them coding superpowers, but none was to be found. Instead, the key to a high rating was simply many years of dedication and hard work.

It’s illuminating to read the answers on this Quora question: “How does it feel to finally be red at TopCoder after years of hard work?” The short answer: nothing much really.

4Above: Rating graph of Codeforces user netman. Getting to red takes years of practice.

Given the amount of time it takes to master competitive programming, one naturally wonders: is this really a good use of time? In a contest, you are ultimately solving problems that other people have solved already, so nothing new is being produced. Although solving a contest problem is satisfying, I find it a lot more rewarding to build projects or apps with my novel ideas.

Recently, Google found that being good at programming competitions is negatively correlated to being good at software engineering.

In the video, Peter Norvig notes that competitive programmers are “used to going really fast, cranking the answer out and moving to the next thing, but you do better if you’re more reflective and go slowly and get things right”.

Ironically, the same thing that makes programming contests so attractive is its own downfall. Contests focus on data structures and algorithms, which are just a small part of software engineering. Other skills like UI design, databases, network architecture, distributed systems, etc, are not touched in programming contests.

Even if you only look at algorithmic problems, competitive programming is still not representative of reality. Due to limitations in automated judging, contest problems are limited to exact, deterministic algorithms that have a single correct answer. This rules out entire classes of randomized and approximate algorithms. Algorithms now rely more and more on data and machine learning, and less on combinatorial approaches, which further renders competitive programming less relevant.

Now, are programming contests useful? Yes, but only up to a point. Solving contest problems is an excellent way to familiarize yourself with a programming language and its data structures, as well as get better at converting procedural ideas to code. These are very useful skills for a coding interview. However, even the most difficult Facebook/Google interview questions are maybe around a Codeforces Div2 C (or Div1 A) difficulty, which is a long way from the hardest contest problems.

5Above: Beyond a certain point, skills learned in programming contests are only useful for programming contests.

I would put the inflection point at about 1700 Codeforces rating (enough to solve Div2 A and B consistently). Beyond that, you continue to improve, but be aware that you’ll be studying things solely for contests that have little relevance anywhere else, for example, Fenwick trees, max flow algorithms, bitmask DP, and other increasingly obscure topics.

So far, I’ve been fairly critical of competitive programming, but rather than deride it as a waste of time, I think it’s best to view it as a sport. Like soccer or basketball, the function of sports in society is to inspire excellence, and above all, to have fun. Terry Tao wrote a similar article on math competitions; I’d agree with him.

My advice to you: do programming contests if you find them fun and you enjoy tackling hard problems. But don’t take it too seriously: it takes years of dedicated effort to get extremely good at it, dedication that very few people have. Unless you’re at or aiming to compete at the World Final level, you definitely shouldn’t be spending a significant amount of time getting better at contests. Your time is better spent studying machine learning, or statistics, or compilers, or distributed systems, or just about anything else in computer science.

I have accounts on Hackerrank and Codeforces if you want to follow me. As per my own advice, I’m no longer actively trying to get better, but I still do problems for fun occasionally.

Edit: This article has some interesting discussion on Reddit and Codeforces.

How to succeed in your first tech internship

Congratulations, you’ve just landed your first software engineer internship! You’ve passed a round or two of interviews, signed an offer letter, and you’re slated to start next month. What now? You might be a bit excited, a bit apprehensive, wondering what the startup life is like, are you even smart enough to do the work they give you…

I felt all these things when I started my first internship three years ago. Now, I’ve completed four internships and I’m halfway through my fifth one; I’m sort of a veteran intern by now. In these five internships, I’ve learned a good deal about what it takes to succeed in an internship, things that are not obvious to those just starting out. Hopefully by sharing this, others can avoid some of the mistakes I made.

Your first week at [startup]

Chances are that you’ve coded in assignments for schoolwork, and maybe you’ve coded a few side projects for fun. Work is a bit different: you’re working with a massive codebase that you didn’t write, and probably no single engineer in the company understands it all. Facing a codebase of this complexity, you might feel overwhelmed, struggling to find the right file to start. You feel uneasy that a small change is taking you hours, afraid that your boss thinks you’re underperforming.

Relax, you’re doing fine. If you got the job, it means they have faith in your abilities to learn and to succeed. I’ve talked to hundreds of Waterloo interns, and I’ve never heard of anyone getting dismissed for underperforming. The first few weeks will be rough as you come to terms with the codebase and technology stack, but trust me, it gets much, much easier afterwards.

Asking for help

As an intern, you’re not expected to know everything, and often you will be asking for help from more experienced, full-time engineers.

Before asking for help, you should spend a minute or so searching Google, or Stack Overflow, or the company wiki. Most general questions (not relating to company specific code) can be answered with Google, and you save everyone’s time this way.

When you do ask for help, be aware that they might be working on a completely different project, so they don’t have the same mental context as you. Rather than jump straight into the intricate technical details of your problem, you should describe at a high level what you’re trying to accomplish, and what you tried, and only then delve into the exact technical details.

An example of a poorly phrased question would be: “hey, how do I invalidate a FooBarWindow object if its parent is not visible?” You’re likely to get some confused stares — this might make perfect sense to you, but they’re wondering what is FooBarWindow and why are you trying to invalidate it at all.

A better way to phrase it would be something like: “hey, I’m working on X feature, and I’m encountering a problem where the buttons stop working after you press the back button. After looking a bit, I discovered my component should have been invalidated when its parent is no longer visible, but that’s not happening…” This time, you’ve done a much better job of describing your problem.

It’s always helpful to take notes, so you never ask the same question again. How do you commit your code to Git? How do you deploy the app to stage? If you don’t write it down, you’re going to forget.

At the start, you’re going to be asking 5 questions an hour, which is okay. Soon you will find yourself needing to ask less and less, and eventually you’ll only ask a handful per day.

Taking charge of your own learning

Like it or not, software engineering is a rapidly shifting field, where a new Javascript framework comes out every six months. You have to be continuously learning things, or your skills will become obsolete. Learning is even more important when you’re an intern, still learning the ropes. Fortunately, a tech internship is a great opportunity to learn quickly.

Not all software engineers are equal — at some point, you get to choose what you want to do: frontend, backend, or full stack? Web, iOS, or Android? Become an expert in Django or Ruby on Rails? Depending on the company, you often get considerable say on what team you’re on, and what project you work on within your team. Use this as an opportunity to get paid to learn new, interesting stuff!

Good technologies to learn should satisfy two criteria: it should be something you’re interested in, and it should also be widely used in the industry. That is to say, it’s more useful to know a popular web framework than an internal company-specific framework that does the same thing.

When you get to pick what project to take next, it might be tempting to pick something familiar, where you already know how to do everything. But you learn a lot more by working on something new; in my experience, employers have always been accommodating to my desire to work on a variety of different things.

You will overhear people talk passionately, with phrases like, “oh, it’s running Nginx inside Docker and fetches the data from a Cassandra cluster…” If you’ve never heard of these technologies, this sentence would be nonsensical to you. It’s well worth the time to spend 10 minutes reading about each technology that you hear mentioned, not to become an expert, but just to have a passing understanding of what each of these things do. With a few minutes of research, you’d be able to answer: “when should you use Cassandra over MySQL?

Learning is valuable even when it’s not immediately relevant to you. Occasionally, you’ll find yourself in meetings where you don’t have a clue what’s going on, say with business managers or projects you’re not involved in. Rather than zone out and browse Reddit for the duration of the meeting, listen in and learn as much as you can, and take notes if you begin to fall asleep! The human brain has near infinite capacity for learning new things, and at no point will it reach “capacity” like a hard drive.

Take responsibility and deliver results

A common misconception is programmers are paid to write code. Wrong: as a programmer, your job is to deliver results and provide value to your company; part of this job involves writing code, but a lot of the work is communicating with managers, designers, and other engineers to figure out what code to write.

When you’re assigned a project, you own it and you’re in charge of any tasks required to push it through to completion. What if something is broken in an API owned by another team? You might be tempted to hand in your code and proclaim, “my code works fine, so my job here is done, I can show you that their API is broken, so it’s their fault.” No, if your feature is broken then you need to fix it one way or another. So go and ping the engineer responsible, schedule a meeting with him, anything to get your project completed.

Sometimes you run into problems that seem insurmountable, so complex that you feel compelled to put down your sword and give up, and tell yourself, “this is too hard for an intern“. This is a bad idea, you should never expect a full-time engineer to come in, take over, and bail you out of the situation. Your mentors are not superhuman — it’s not like they can instantly conjure a solution, no, they have to work through the problem one piece at a time, just like you. There’s no reason you can’t do the same.

The product you deliver is what ultimately matters, so don’t worry about secondary measures of productivity, like how many lines of code you commit, or how many story points you rack up on Jira. There’s an apocryphal tale of a programmer who disagreed with management measuring productivity by lines of code, and writing “-2000” because he made the code simpler. Likewise, you aren’t being judged if you come in 30 minutes after your manager does, or if you leave 30 minutes before he does, or if you just feel like taking a mid-day stroll in the park, as long as you’re consistently delivering quality features.

Many interns suffer from “intern mentality” and consider themselves fundamentally different from full-times in some way. This is an irrational belief — your skills are probably on par with those of a junior engineer (or will be in a few weeks). This means you should behave like any other full-time engineer (albeit minus interview and on-call duties); the only difference is you’re leaving in a few months. Don’t be afraid to contribute your insights and ideas and consider them less valuable because you’re “just an intern”.

Other tips

What should you learn to prepare for an internship if you have spare time? Learn Git! Git is a version control system used in most companies, and is both non-trivial to pick up, and used more or less the same way everywhere. Other stuff is less useful to pre-learn because they’re either easy to pick up, or can be used in lots of different ways so it’s more efficient to learn on the job.

Internships are a great way to travel places, if that interests you. I picked 5 internships in 4 different cities for this reason. Unlike school, you don’t have to think about work during weekends, which leaves you lots of time to travel to nearby destinations.

I’ve only talked about what happens during work. If your internship is in the USA, the Unofficial Waterloo USA Intern Guide was super helpful in answering all my logistical questions. Also, some of my friends have written about crafting a resume, and how to ace the coding interview.

Four life lessons learned by playing Hearthstone

I’ve played Hearthstone on and off for a few years, since it first came out. As I played more and more, I began to notice parallels between my decision making processes in Hearthstone and in real life. This is a self-reflective post, and probably my first serious attempt to describe the core features of my mentality and decision making process. Although I wanted to write this for a long time, I found it difficult to put my ideas into words because they have been part of my personality for so long.

Why is Hearthstone a good representation of real life? Two reasons:

  • First, it’s a game of imperfect information and chance, so you must take risks and deal with uncertainty. Real life situations are usually like this. Games of perfect information (like chess) lack this probabilistic aspect and behave very differently.
  • Second, Hearthstone is a game about decision making skills, rather than mechanics. Every game has some element of decision making, but many games require doing some mechanical action (eg. last hitting) better than your opponent. Mechanical skills are confined to the specific game and are less likely to be relevant in real life.

By playing Hearthstone, I developed a general internal model for making decisions in uncertain situations. This is a broad criterion and covers many situations in day-to-day life.

Lesson 1: There is always a correct decision, and it’s your job to find it

The goal in Hearthstone is to reduce your opponent’s life to zero. How do you accomplish this? You make a plan, perhaps flooding the board with minions, perhaps unleashing a deadly combination of spells.

For our purposes, it doesn’t matter what your strategy is. At the start of the turn, you look at the cards in your hand, the state of the board, what cards your opponent played before. Call this information the game state. You ponder for a bit and come up with an action that best improves your position.

You execute your action on the board, but you still don’t know what happens next with certainty. There are many things you cannot control, which I will call RNG. RNG is short for Random Number Generator, and I will use it to mean anything you don’t have control over.

I use the term RNG for lack of a better term, but I’m not just talking about random game mechanics. RNG includes any state hidden from you, like your opponent’s hand and strategy.  Think of it as a random variable with a known distribution (eg. you play a card that destroys a random minion, which minion will it hit?) or with an unknown distribution (eg. what is the probability your opponent has two flamestrikes in his deck?). Even if the information is known to your opponent, it’s simpler to treat it as a random variable.

Here’s the model summarized in a diagram:

In any game state, there must be one “correct” action that gives you the highest chance of winning the game. The decision-making player aims to consider all possible actions and choose the best, “correct” one.

As a corollary, decision making should be perfectly rational. Otherwise, if my decision engine generates two different actions depending on my emotional state of mind, they cannot both be correct.

A second corollary is actions should always be justifiable through fundamental values. It’s unacceptable to do things by habit, or because other people are doing it — everything I do should have a positive expected value on the things I want to accomplish.

For me, one of my “meta” goals in life is to make correct decisions as much as possible. This is not to say that I behave like a robot — I still experience emotions like everyone else — but I try to eliminate emotions from my decision making process.

In Hearthstone, doing so gives you the highest chance of winning the game. It makes sense then, by extrapolation, that correct decision making gives you the best shot of getting what you want out of life.

Lesson 2: Information is valuable, treat information gathering as a subgoal

One rule of thumb in Hearthstone is “RNG first”. If you are going to play a sequence of cards, one of which has a random effect, it’s better to play the random effect first. This way you extract information out of the RNG pool of unknowns, and with this extra information you might be able to make a better play.

Another useful thing is to keep track of enemy secrets. Imagine you have this on the board:

You want to play a giant, but you’re worried that the secret is “mirror entity”, which summons a copy of the next minion you play.

Without any other information, you’re in a tough spot. But what if you played a minion last turn and the secret did not activate? Then you know that the secret isn’t mirror entity, and confidently play the giant.

Alternatively, suppose that you don’t have this information handy. One tactic is you can “test out” the secret by playing a small minion, and seeing whether the secret activates. You are paying a price with a normally inferior move, but the information you obtain is valuable for future decisions.

A similar concept occurring in real life is flirting. You’re at a party and you see a cute girl walk by. At first, you make a few playful comments, and observe her reaction and assess if she is interested in you. Flirting isn’t just an arbitrary social custom; it makes sense logically as a way of gathering information.

While information isn’t the final end-goal by itself, even a little information can greatly improve decision making, by eliminating vast swathes of possibilities that no longer need to be considered. Whether it be playing a giant, making a big purchase, or asking someone out on a date, gathering information is a useful subgoal.

Lesson 3: Focus on things you have control over, RNG evens out in the long run

Often in Hearthstone, luck is just not on your side. Have you ever seen your opponent topdeck the pyroblast and instantly win the game? Or that mad bomber that hits you three times in the face? How do you feel?

It’s natural to feel angry when this happens to you, especially if it ends up losing you the game. But eventually I realized how pointless it was to get upset at unlucky RNG. What’s the use of worrying about things you have no control over?

I see this all the time — people getting visibly upset when the bus is late, or when a player on your team goes AFK in a game of league. I try to adopt the opposite mindset: worry about my own decision making and simply accept random events beyond my control.

Let me give you an example. Last term, during an important phone interview, my phone stopped working during the middle of the interview. Calmly I got up and notified the CECA front desk, and waited as they spent the next 20 minutes troubleshooting the problem. Most people would be stressed out at this point, but I didn’t feel stressed at all. Rather than getting upset, my mind was relaxed, because I took comfort in knowing that I did everything that could be done; whatever happens next was out of my control.

The law of large numbers says that when you repeat a random event many times, the average outcome will surely converge to the expected value. Hearthstone is so random that a legend player will beat a rank 5 player no more than 55% of the time. Any single game is close to a coin flip, just marginally in favor of the stronger player. But over the long run, it’s a mathematical guarantee that the better player will end up on top.

Lesson 4: Separate the outcome of a decision from the decision itself

In real life and in Hearthstone, you can’t directly tell if a decision was good or not. You only know the outcome, and you can decide if the outcome is good or bad. But the outcome is a function of the decision and RNG, which adds noise to the process.

In other words, the correct decision does not always produce a good outcome, and sometimes a bad decision produces a good outcome. It would be a mistake to retroactively label a decision as “correct” simply because you got lucky.

Here’s a Hearthstone example:

Your opponent is a mage, and on turn 6 you flood the board with a lot of small minions. If he has flamestrike, playing it deals 4 damage to each of your minions, instantly killing your whole board.

Turn 7 comes and it turns out he doesn’t have flamestrike, so you win the game easily. You conclude that playing all your minions was a great idea because he didn’t have flamestrike.

This logic is fallacious: it fails to separate decision from outcome. A correct action is the one that maximizes the win probability, given the information available at the time. Therefore it makes no sense to look at the outcome and retroactively judge the correctness of the initial decision.

So in this example, playing all these minions was a mistake because there’s a high chance the mage has flamestrike. It doesn’t matter if he actually has flamestrike or not, the mistake is equally bad. (A better play would be to play fewer minions, thus mitigating the risk).

Now here’s a real life example. Last term, I had multiple job offers for software engineering internships and I had trouble deciding which one to accept. So I tried to negotiate: I picked one of the companies, told them about my other offers, and asked for a 20% raise in salary. My request was denied.

Does this mean that negotiating was a waste of time? Absolutely not. I know friends who successfully negotiated a higher salary by doing something similar. My particular outcome was not successful, but this doesn’t indicate my attempt was a mistake; if I found myself again with multiple offers, I would do the same thing.

Alfred Tennyson wrote the following about romance:

‘Tis better to have loved and lost

Than never to have loved at all

There are many ways to interpret this quote, here’s mine. Even if the outcome of a romantic encounter is unfavorable (to have loved and lost), it does not mean the decision to pursue the relationship was a mistake.

Why I still do stupid things

Alas, despite my best efforts, I still find myself doing stupid things — quite frequently even. Mistakes happen for a variety of reasons, but after analyzing some, I group them into three broad categories.

The first type of mistake happens when the situation is complicated, and the amount of data available exceeds my brain’s capacity to process it. In theory, I should never lose at chess — all the information is known. Of course, the number of positions explodes combinatorially and in reality I’m a mediocre chess player. Chess grandmasters group information in “chunks” and can reason about positions more efficiently — but this requires experience. In general, humans are prone to making mistakes in complicated situations.

The second category of mistake is having an incorrect model of the world. When we evaluate possible actions, we “simulate” the effects with a simplified version of the world. Problems arise when there is a discrepancy between the model in our heads and the real world.

This discrepancy can manifest itself in several related ways. We may incorrectly value subgoals, for example, a newbie Hearthstone player, knowing the objective is to reduce the enemy’s health to zero, thus decides to deal the maximum damage to the enemy’s hero every turn and ignoring everything else. We may overlook important factors, for example, leaving a Gadgetzan Auctioneer on the board, not realizing its potential, and being surprised next turn when your opponent draws 10 spells using its special ability. Or we may simply miss a possible play that never even occurred to us.

This type of mistake is the most common, but fortunately the most fixable of the three. As you gain more experience with the domain, your model of the world becomes a more accurate representation of the real thing. Then you learn to correctly assign values to things, and generate the full set of possibilities for a situation. For me, this gradual process of learning and self-improvement is one of the most satisfying things in life.

The third and final category of mistake is making decisions without thinking, thereby short-circuiting the entire decision making process. This could be when you’re stressed, emotional, or just tired. An example of this is when you casually trade some minions in Hearthstone, then realizing you had lethal. If only you thought more carefully, you would have easily found the correct play.

It’s not necessarily bad to do things without thinking too hard: it would be silly to invoke the full mechanism to choose between a burrito or a sandwich for lunch. It’s important, however, to realize when a decision is likely to have far-reaching consequences. In that case, it’s wise to defer making the decision until you had time to think things through.

There’s a lot more I could talk about, but this post is getting quite long so I’ll stop here. Whether you agree or disagree with my view of the world, please leave a comment!