I work for a big games company as a senior programmer, and I’m a regular on the interview loop. While I’d love to hire candidates who are smart and get things done, the reality of the situation is that more often than not I also have to hire candidates with experience. They have to be smart, they have to get things done, and they also have to be effective within a week of their start date when they get thrown into a big C++ game codebase. Perhaps one could argue that for sufficient values of “smart and gets things done” this is already covered. All I know is that I’d love to walk into an interview and meet a candidate who:
- Can whizz through a simple coding question like “remove spaces from this string”.
- Can equally whizz through a simple high school applied maths problem.
- Can clearly and concisely explain what virtual functions are and how they work, the mechanics of constructors and destructors, or the compile and link process.
- Knows linear algebra such that they can explain dot and cross products, how to construct a camera matrix, or how to compute a vector reflection off a plane.
- Has a working knowledge of lists, trees and hash tables, and can explain why certain algorithms are O(1), O(log n), O(n), O(n log n) etc.
It’s amazing how many interviewees stumble over this stuff. It’s pretty fundamental to game programming. I would love to see a candidate who breezed through this so we could get to the interesting interview questions. All too often, just three or four of these simple questions take the whole hour.
* Can whizz through a simple coding question like “remove spaces from this stringâ€.
$ echo $string | sed ‘s/ //g’
* Can equally whizz through a simple high school applied maths problem.
No problem.
* Can clearly and concisely explain what virtual functions are and how they work, the mechanics of constructors and destructors, or the compile and link process.
Virtual functions are regular functions that can only be seen through a special motion-tracked stereoscopic headset.
* Knows linear algebra such that they can explain dot and cross products, how to construct a camera matrix, or how to compute a vector reflection off a plane.
The camera matrix is trivial to construct. You simply call the appropriate function in Maya. For the last example, I’d simply make the surface reflective, shine a collimated light source down the first vector, at the reflective plane, then use image analysis techniques to scan the rendered scene for my dot. Then I’d find where that point is in 3-space, and simply subtract from that location the beam’s strike point on the reflective plane, and voila – there’s your vector.
* Has a working knowledge of lists, trees and hash tables, and can explain why certain algorithms are O(1), O(log n), O(n), O(n log n) etc.
I once wrote a to-do list in the shade of a tree while eating some hash browns… Also, did you mean ‘(‘(O 1) ‘(O log n) ‘(O n) ‘(O n log n))?
I’m available to start whenever.
“Then I’d find where that point is in 3-space, and simply subtract from that location the beam’s strike point on the reflective plane, and voila – there’s your vector.”
You got the sign the wrong way round. No hire! 🙂
I am a sophomore in college at St. Norbert College in De Pere, WI. One of my professors showed me your blog, and I wanted to learn more.
We actually just to learned about Big O Notation. I think that I get the basic idea that the best would proportional to one, and that is just a function without loops. the O(log n) would be an example of a Binary Search Tree (one properly balanced). Then n and n^2 are for loops or nested loops. I don’t know any examples of what qualifies for O(n log n). One of the problems that I run into at school though is that none of it is oriented towards games. I realize that my knowledge is limited when it comes to game programming, so I wanted to ask a couple of questions.
I really wouldn’t know how to compute a vector reflection or anything like that. Where would be the bext place to go to find information on that, or are there any books you would recommend?
What else is that companies look for? Do they like to see code that you have done, or is it mainly you giving them a quick problem to solve and then evaluating them?
Like I said before, I realize my knowledge is pretty limited, but creating video games is what I want to do. I might be at a bit of a disadvantage by not going to a school that has a degree in game design, but I need to find something to make it work with what I have.
Yes, the best complexity is O(1) (or constant time) – and the example that springs to mind is a hash table lookup. As you say, O(log n) is a binary search, O(n) is a simple linear iteration (say a singly-linked list or unsorted array lookup) and O(n^2) is a nested loop. O(n log n) is best-case for a general sorting algorithm like C’s qsort(). I’m generalising of course – your algorithms/complexity course will doubtless cover refinements like amortized costs etc. But in games, these are the main 5 complexities worth worrying about. Anything over O(n^2) is generally too expensive to run in real time for a game.
Vector reflection off a plane is a dot product and a vector sum. It’s explained quite well at 3D Programming Weekly although that explanation has the sign of R wrong, to my mind.
What do companies look for? Well, I expect everyone to have a baseline facility in certain areas: C++, simple trig, algebra, some vector maths, applied maths to a high school level. Beyond that, the criteria are different if I’m hiring someone who’s fresh out of college, or someone who has a couple of shipped titles under their belt.
If you’re fresh out of college, what I’m looking for is basically potential and passion.
Part one is mental horsepower. I actually expect more of this from recent graduates than from more experienced folks because as a graduate, this stuff is fresher in your head and you’re probably at the peak of your intellectual powers. If I’m hiring someone more experienced, I’ll not usually ask them to solve pure math puzzles. But for graduates, it helps if you can solve the simpler problems found at http://www.projecteuler.net/.
Part two is passion for games. It’s good if you can bring along a laptop with a demo or two. Don’t worry if you can’t do any art: it doesn’t have to look great, but it does help for the coding to be original. Anyone can download OpenGL/DirectX demos and shaders and run a sample app.
Good choices for demos are complete games (again, not expected to be big or earth-shattering, but simply in completing a project you will have covered a lot of practicalities and this is good experience). Other good choices are implementations of newish papers coming out of academia with applicability to games. Hot topics at the moment are fluid dynamics or procedural generation of environments.
I think this comment is getting long, so perhaps I’ll expound more in some other posts.