The Wisdom Of Cheng

There are roughly four styles of interview question that you might get, only three of which I'll help you out with:

0. Soft questions: you get asked about projects you've done before, what kind of programming languages you like, what you think about test driven development/Internet of Things/the latest JavaScript fad, ... These are (in my opinion) poor questions to ask, and if you do get asked may be indicative of a low-skill company, and/or management with a non-technical background. Even so it is definitely worth thinking a little about how you might answer these, but don't sweat it too much. I won't talk further about this.

1. Trivia / bookwork: you get asked an elementary (though maybe not easy) question about a fundamental part of computer science or computing. Things such as "implement a graph data structure then write a function to test whether node A is reachable from B", and "what's the time complexity required for sorting an array of 4-bit integers", and "what's the difference between TCP and UDP connections" fall into this category. Commonly asked especially for junior positions, or in the first round of the interview if there are multiple rounds.

2. Design and implement: you get asked a problem which is well defined and limited in scope, but doesn't have an "off the shelf" solution. You're expected to talk your thought process out loud whilst you consider how to tackle the problem. Then once you've got a solution that meets the requirements, you're (usually) expected to write it out explicitly as code -- either as pseudocode on a whiteboard, or as a live-coding exercise on a laptop.

3. Large-scale design: you get asked a fairly tough problem, which is either somewhat open-ended, or involves processing large amounts of data. Similarly to the above, the interviewers want to hear some solutions you can think of, and maybe if there are more than one obvious candidate, weighing up the benefits of each. The most they'll ask for is pseudocode. These are obviously somewhat more difficult to answer, but do give you the chance to show off some ingenuity/special data structures if you've done the prep work!

For 2 and 3, there are some things to be said that don't necessarily come naturally. Firstly, get into the habit of talking your thought process out loud. You should never spend a significant amount of time thinking in silence. The interviewers aren't looking for a right or wrong way to tackle the problems, they just want to make sure that they are on the same line as you, and it makes it much easier for them to give you a small hint/nudge if you get close to a valid solution.

Similarly, if you make a mistake at any stage the interviewers will usually correct you. Don't get flustered if this happens, this is not indicative of a failure. Take their advice gracefully, make the correction, and check that you haven't made the same mistake elsewhere. They want to see that you'd be able to form a good member of their team, and a big part of that is taking on suggestions/criticism well.

Once you've got a solution, explain it in detail -- why it works and how efficient it is. Don't expect the interviewer to just understand, even if you think it's obvious. The clearer your explanation is, the more convincing you'll be. Definitely jot down diagrams throughout your interview to aid your explanations, don't wait for your interviewers to ask you to do that.

Basically, all new interviewees fall into the trap of thinking that succeeding at an interview is all about getting the questions right. In reality, interviewers are looking for a mix of things: clarity of explanation, a solid grasp of the compsci fundamentals (nothing too advanced, don't worry), and clean and precise coding (they'll cut you some slack on this one considering your background). In fact, if you manage to solve a problem correctly, the interviewer will likely just give you an extension to the problem, because they actually care about seeing your problem solving process, not merely the fact that you managed to get something right.

As to how to prepare, there's two steps. Firstly, doing the background prep at home. Secondly, doing as many interviews as possible. It's only through the latter that you really get a feel for what they're looking for. Don't be afraid to apply to as many places as you can, to get as much experience under your belt as you need to feel comfortable.

But first, here's some pointers for background study.

Everyone says that *the* book to go for is Introduction to Algorithms (Cormen et al). This is a huge book full of good stuff, although it's probably better to treat it as a reference book as a lot of the content will definitely be outside the scope of even most technical interviews. I have to admit that I always found this book hard to chew through, though as a mathematician I'm sure you'll be able to make much better sense of the dense parts. I'm sure you can find it for free in a library/other places if you try :)

Another place that you might want to look is first year Cambridge compsci lecture notes (specifically "Foundations of Computer Science" and "Algorithms"), if not as a study guide more than anything else.

Here's the stuff you really definitely want to know about:

- Algorithmic complexity (big-O notation), both time and space complexity. Know a bit about how to analyse it for a given algorithm/data structure.

- Sorting (merge sort, quicksort). Definitely know how they work and what their complexity is, and their significant properties (e.g. quicksort has quadratic worst case (unless...), merge sort is stable). Definitely try implementing these once. It may or may not be useful to practice more than once in case they come up as a bookwork question.

- Binary search. Try implementing one correctly -- surprisingly hard as there are many edge cases to consider! Another possible bookwork style question.

- Data structures: arrays, linked lists, ring buffers, stacks/queues, trees, graphs, their representations in memory, basic operations and complexities. This stuff is all basic and can be found in The Book or online. In particular: know the special types of trees -- binary search trees (BST) and their complexities, binary heaps. BSTs come in non-self-balancing and self-balancing (e.g. red-black) varieties, you may be asked to implement the former, but definitely not the latter -- just know that they exist and what problem they solve. Binary heaps are easy to implement and very useful to know how to (allowing you to write e.g. heap sort). Know that graphs come in two main representations: adjacency list and adjacency matrix. There exist heaploads of graph algorithms, but at a minimum you need to know BFS/DFS (useful to know how the latter provides a topological sort), and would be helpful to know how to implement a minimum-spanning-tree algorithm and Dijkstra's algorithm. Make sure above all that you know what each data structure is used for, and their relative pros and cons.

- Problem solving paradigms: Greedy, dynamic programming, and to a lesser extent divide and conquer. After getting to grips with some motivating examples for each (e.g.: greedy -- finding a minimal spanning tree; dynamic programming -- calculating Fibonacci numbers; divide and conquer -- merge sort), the best way to learn these is to practice: find some problems, design an algorithm and code it up. Dynamic programming is especially important to learn, just because there is a ridiculously vast range of problems whose solutions are simply dynamic programming under the veil. A classic example: given a set S of coin denominations, what's the least number of coins required to make change for n pence?

There are many websites out there that provide example problems exercising these last two points that you can cut your teeth on. I've heard good things about HackerRank for instance, but never used it myself. Codeforces is another one which, although geared more towards competitive programming (think IOI and ACM-ICPC), has a vast collection of (tagged, IIRC) problems. Both allow you to submit a solution and judge it against a private set of test cases for correctness.

If you want some help on any specific topic, just let me know. It's much easier for me to help on specific things than anything in general :) Also, if you want some sample interview questions to try, I can try to think of some good ones for you. Especially dynamic programming. Interviewers love to use that as a proxy for "hard problem".

Good luck :D