On May 31st, the legendary, wise and experienced Derek Kisman (aka SnapDragon) graciously answered dozens upon dozens of questions posted by passionate hackers via HackerRank Live for 6 hours! What’s more, he did the entire live cast and coding on his Microsoft Surface Pro!
Some call him the mythical man. With over 20 years of programming experience, and a reputation as a self-taught award-winning top coder for many years, SnapDragon revealed insight into solving the toughest challenges from both ICPC 2014 and ZenHacks! SnapDragon has been a judge several times for the prestigious intercollegiate coding competition. Plus, he ranked #2 in the recent ZenHacks competition. Many of you live streamers requested a link to his solutions. As promised, here it is!
SnapDragon also talked about general programming advice for coders who want to get better at their programming skills. Hundreds of folks tuned in at a time, and his livestream video recording has garnered over 6,000 views to date!
We had a chance to catch up with SnapDragon to talk about the highlights of the event. Here are just a few pearls of wisdom from legendary SnapDragon.
Let’s get right to it! What’s your advice on solving the infamous ‘G’ problem from ICPC-2014?
Only 1 team was able to solve it. Teams shouldn’t be afraid to think about a problem just because they don’t see other teams solving it. G isn’t very difficult by comparison to the so-called “stoppers” of previous years. (It has a very short solution). [4:30].
Top 5 tips for ranking at the top of the ZenHack leaderboard:
1. You don’t have to reproduce the judge’s intended solution, you just need a successful submission.
2. For Composite Numbers, I didn’t know about the Lehmer method for computing pi(n), so I just went nuts optimizing a dumber solution.
3. For Efficient Journey, I didn’t quite figure out that much of the path ended up constant, but I got close enough using an O(log N) skip list.
4. For Introduction to Algebra 2, I just proved what little I could, brute-forced a few more examples, then submitted and hoped I was done. And it worked.
5. For Travel Trouble, I ran out of contest time and couldn’t implement the O(N^2) solution… but O(N^3) with some clever heuristics squeaked by.
Your favorite question that someone asked you during the live event?
When someone asked about solving the Rubik’s Cube. 🙂 I tried to explain a nice trick for solving Rubik’s Cube based on group theory conjugation (like this one).
Advice on programming interviews:
You wouldn’t believe how many people we interview who just can’t code. If you go through HackerRank, you have to be able to think through problems, which is what companies want to see!
On creating a Mental Model when approaching problems:
I don’t think my mental model has much to do with what language I’m coding in. Granted, I’m always working in C++, but my mental model is basically mathematics, not programming. So, when I’m looking at a problem, I’m thinking: What does that look like mathematically? Then, programming is the art of transforming your mental model into something in a text file in a way that maps it as closely as possible.
What does it take to be a world champion coder?
Math is really important. But you don’t need to be a world champion in math to be a world champion at programming. I’m sort of the example of that. “Calculus isn’t TOO important in programming contests, but you need the basics. Like integrals.”
What’s the best strategy to practice and learn?
I don’t think I ever picked particular algorithms and studied them. Back when I was on Unviersity of Waterloo ACM team, we’d practice regional problems. We’d spend 4-5 hours and pretend it was an actual contest. Afterward, we’d figure out where our deficiencies are. Was it a new algorithm? Was it bugs? Sometimes there’s a sentence in the problem that you missed.
Is competitive programming necessary to crack companies’ coding interviews?
It does seem like companies like to ask algorithm-style questions in interviews. I’ve never seen questions that approach the complexity of some of these later ACM challenges. Because, companies aren’t really trying to see whether or not you’re an algorithm master. They want to see how you think. They give you problems that are hard enough so they can hear your thoughts as you solve it. Going through HackerRank problems is a really good way to prepare for interviews for companies like Zenefits and Google. You wouldn’t believe how many people come in for interviews who just can’t code. They can’t write a program, compile it and run it.
So, if you practice on HackerRank a lot, you’ll do really well in all those standard interview questions. You won’t need to memorize a list of questions beforehand…you’ll be able to think on the fly. They’re easier than the hard challenges you’ll find on HackerRank or elsewhere.
On Dynamic Programming:
The problem with Dynamic Programming is that it’s not just a single algorithm…it’s a concept. I learned DP a lot from experience. It’s more of a generalized approach to searching. It’s the sort of thing you have to pick up by experience. The experience is being able to recognize these states can look like. You need these to be not an exponential number. You need them to be as small as you can get them. (36:43).
On Network Flow:
Most programming contests seem to have Network Flow these days. It tends to be considered a hard problem. It’s sort of cheating in that you have an exponential search. Your path is important and you have to remember your path at all times, but you can erase it. (38:50).
How did competitive programming help you solve the logic puzzle that was unsolved for 30 years?
There was a puzzle called Panex for which the shortest known solution was something like 30,000 moves. For 30 years, it wasn’t proven. I was able to come in and apply a very hard, very advanced form of dynamic programming to solve it — to actually prove that the min was 30,000.
Favorite book recommendation for math?
- Godel Escher Bach (thinking about the world as a computer scientist)
- Martin Gardner’s articles in Scientific American