Sorry your browser is not supported!

So I came across a programming test to get a job as a game programmer. Now just to clarify I am not going to turn this in to try and get a job, I am posting some of these question so I can further my knowledge and for anyone else that may be interested in what some one may ask you. Now of course every studio is going to ask different questions but still this was the first time I saw any kind of programming test. Anyway this isn't the full test just some question that I didn't know and would like to get a better understanding of.

This first one was about optimization with the bit operators but I have never used them and had no idea how to optimize these:




These next two were coding questions that I didn't really know that I think I should have known:






Now there were some 3d math coding question but I don't want this post to be to long so if anyone is interested in seeing those and helping me out with them I will gladly post them.

Any help will be greatly appreciated.

I'll give the first part a try. Multiplication and division can be substituted with shifting bits left and right. Shifting with 1 bit left means multiply with 2, shifting by 2 bits is multiply by 4, then 8, 16, 32 and so on.

Modulus can be substituted by "and"-ing the number with one less than the divisor (or something like that), which will get the lower bits out of the number. However, this doesn't really work if the number happens to be negative. Also, I don't think we can optimize modulus calculation any more than the compiler already does. So I didn't change anything on the modulus signs.

Therefore, my guesses are:

a. int a = b * 4 = b << 2;
b. int a = b * 72 = b * 64 + b * 8 = (b << 6) + (b << 3);
c. int a = b % 1 = 0;
d. int a = b % 16; (no change)
e. int a = (b + c) / 2 = (b + c) >> 1;
f. int a = (b * 3) / 8 = (b + b + b) >> 3;
g. int a = (b % 8) * 4 = (b % 8) << 2;

In (b) you need to cut up the shifting into two parts because 72 cannot be achieved in one step but 72 = 64 + 8.

In (c) the remainder of dividing something with 1 is always zero.

In (f) I substituted b*3 with b+b+b because addition is supposed to be faster than multiplication and we're supposed to optimize but I'm not quite sure whether it's really faster.

I hope I didn't make some silly mistakes, it's late in the evening and I'm very sleepy but couldn't resist the challenge when I saw this. The rest of the tasks is interesting too but they will take longer to answer.

hey thanks for responding to this. I think I get how the the bit operators work now man thanks for that.



Yeah I didn't know how to do them and I only had 2 hours to take the test with a total of 26 questions, that optimization was only one question. If you want I can post the 3d questions they had, which that was some new territory for me but hopefully some one can shed some light on it if there interested.

A good exercise is always welcome. I'll have an attempt at writing those compression functions and post them later. You can also post the 3D questions, maybe we can learn something from them.

By the way, are you sure you are allowed to post this? I mean test administrators are usually not happy when the test questions become public.

I figure just as long as you guys don't know the company it can't hurt. Also I am leaving out a lot of questions so it should be okay. If I get blackballed from the gaming community for trying to learn then so be it.

Anyway here are some 3d questions.












So here are just a few of the ones that I had no idea about and would really like to know how to solve them.

Again thanks for the response and hopefully both of us will learn a lot from it.

OK here are my solutions to your compression functions. First, the string compression. This one is pretty easy, there are only two tricky questions: 1. being able to write the function in one loop without special "start string" and "end string" conditions, and 2. how you convert the counted number of characters from integer to string.

To fulfil (1.) I had to make the function parameter a char* instead of string, because I need to process the null terminator and std::string does not necessarily provide it. Using c_str when you call the function is easy anyway.

To solve (2.) I applied a trick to convert a number to string based on ASCII character. If you don't do this, then you need either string stream or sprintf and both of those would be much slower and longer to code. The ASCII solution makes not only the compress function more efficient, but also the uncompress function will be easier and faster. The price is that, if there are more than 9 of the same character in a row, it will be cut up into several 9-character runs, so for example 16A will become 9A7A. We gain on speed in return for a little loss on compression efficiency.

After this much explanation, here is the program:



Continued in next post.

The next one is the colour conversion. This is tricky because in any case, you will lose data. If a colour is expressed on 8 bits, it can have 256 different values. On 5 or 6 bits, it can have much less distinct values. You need to calculate a kind of "percentage" ratio to convert from one to the other.

There is a mathematical formula to do it, but floating point calculation is slow. You can fasten the function by approximating the conversion with bit shifting operations. (Data is lost anyway, so a little more approximation won't hurt in exchange for speed.) The function below contains both solutions, the floating point formula is commented out. The comments explain the rest. I tested the function with several values and checked the result with the Windows calculator in binary mode, to make sure that it works correctly. I didn't do a very thorough testing but I hope there is no big bug left in it. Here's the code.



A final remark: you said you had two hours for 26 questions, that's about four and a half minute per question. Impossible... I may be able to throw together the first skeleton of the functions in that much time, because I had a pretty good idea at first sight how I want to implement them. So the test administrator would have seen that I have some familiarity with the subject, but the function won't be correct on the first try. I spent about half an hour on the first and even more on the second, together with testing (make sure I don't give you something rubbish) and debugging (because at first I missed the parentheses and the operator precedence messed up the result). I think the test is mainly to see if you know in which direction you have to start, but I don't think you can write a fully correct result in less than 5 minutes, under exam stress.

I'll have a look at the 3D questions too but they seem much more difficult.

Yeah I was kind of hoping that was true because I had to leave a lot of things blank and I was thinking wow was I supposed to be able to answer all of these in 2 hours. But anyway really appreciate you taking your time and going through these question its already really helping me. I have a question though where did you learn all of this? For me all of my learning comes from projects that I work on so stuff like compressing a string or compressing a color is just something I would have never of come across. Are there any resources that you use that you could share that you think will help me in learning more about game programming? The test was broken into sections General C++, optimization, coding and 3d. The general c++ was easy so I think I have a good understanding of c++ but I think what I lack about programming is whats going on under the hood and the 3d math is something I am still learning. So any advice on where to get into more advanced features of c++ like books you have read or anything.

Again thanks for the help really appreciate it.

I've had a look at the other questions but there is only one, to which I know the answer:

What is the classic problem with Euler angles? - Gimbal lock.
Solution? - Quaternions.

Don't ask me to explain, I'm not clear about the maths either but for example here is a reference: http://en.wikipedia.org/wiki/Gimbal_lock

The rest of the questions all deal with OpenGL and I haven't a clue about that, sorry. Regarding the last question about floor tiles, I have a vague suspicion that the cracks may be caused by rounding incorrectness (from floating point to pixels after positioning and scaling) or by the fact that we are rendering quads and not triangles. But I'm not sure and don't know the solution either.

Regarding the "where did you learn all this" question: I'm afraid I can't point you towards one universal source of wisdom. I've been programming computers for about 20 years, in different languages. I have completed a post-graduate training course ending with a degree in software engineering, I have read - or at least looked into - numerous books and I've completed several big projects and many small exercises. I picked up knowledge and practice along the way. I still don't consider myself an expert in C++ but I'm doing everything I can to become one.

I have also learned a lot from projects that I've been doing and several times I learned the language itself while working on a project. I assure you, this was the first time I've compressed a string or a colour like that (EDIT: but I did program image compression with run-length encoding which is basically the same thing as this string compression). Still, if you do a lot of different things and study several books, you develop not only the theoretical background but a general "way of thinking", e.g. how to go about processing an array (string), or calculating a percentage to convert a set of values to another set. Believe it or not, I modelled the colour conversion on the theory of converting world coordinates to screen coordinates which is very similar. (Just to be safe, I even made a Google search before I posted it, to confirm that others suggest the same procedure, although I knew it would work.)

The theory of bit shifting and manipulating bit patterns I learned at secondary school, at the programming course and also read about it in books dealing with computer graphics.

As for game programming, I've read several books about that topic, but most of the knowledge in them is not applicable any more because they were written for old operating systems. (You won't care today about how to speed up DOS programs with direct screen memory handling in assembly, or how to cram several variables into one integer because you only have 64K memory for your Basic program, but it was a good practice in using resources effectively.) Part of the theory is still valid though, for example 3D maths which I studied once and then forgot most of it, unfortunately. I should re-learn.

As for general C++ knowledge, I've learned from several books, starting with "teach yourself C++ in 24 hours", "let's program in C", the Stroustrup language reference book, "more effective C++", "the C++ standard library" and "effective STL". But these are more references than coursebooks, although they do have some exercises, and they are high-level. I learned more about the theory of programming algorythms (e.g. sorting, searching, merging data) from Pascal and even Basic coursebooks or from general algorythm descriptions that I've come across.

Then there is always the internet... I don't read any programming sites regularly but in case of problem, someone must surely have posted the solution somewhere, the only problem is to find it... You see, it's bits and pieces from everywhere. You don't need to know everything, the main thing is that you should be able to solve the current task that you are working on at the moment.

Great response! I have been programming for probably about 2 years now and I can understand what you are saying about how there isn't one main source of information out there. I have many different books on c++ and some for 3d math and then of course any internet source I can find that will help me. To me though forums have been the biggest help, I learn best from doing not just reading so you giving those examples will allow me to pick them apart and break them down. I am very great full for your help and this is why I love forums because sharing knowledge is the best way for everyone to improve.

I want to show you something for interest. About 10-15 years ago, the pcx image format was as popular as png and jpg images are today. Practically all game programming books described the format because it was easy to read and write, and provided a good compression for images made up of large parts of the same colour. Have a look at the compression algorythm.

http://en.wikipedia.org/wiki/Run-length_encoding
and http://en.wikipedia.org/wiki/PCX ("image data" part)

Even cutting up long runs into several sequences (as I limited the count to 9) was present in the format, since there was an upper limit how many pixels the number can represent. This is just to show that the test exercise does have its practical uses.

Haha thats awesome really good find. Didn't really think that there was a "method to the madness" I guess you could say but that gives me a much better understanding as a reason as to why you would want to learn to do a compression function like that. Really cool.

Edit:

So kind of still on the topic of strings (and excuse me for such a vague question) but what are good examples of what a parser would be used for in games? I ask because it is a word I have heard been used quite a few times around game programmers but I haven't ever really come across a parser before.

Actually, the very first question is harder than it looks. Those are *ints*, they are signed! If b is negative, or large enough for the very first bit to be 1 when you shift it over in any of those statements, the whole number will be a weirdo negative thingy!!!

So optimizing this:
a. int a = b * 4;
might look like this: (I couldn't figure out how to do it in 1 like wihtout the ternary operator...)
a. int a =(b>>31)==1?((~b-1)<<2)|-2147483648:b<<2;

I do believe that works for positive and negative numbers, not counting overflow, but that's not rly a big whoop.

I think most of those conversions can be summed up as:
a. int a =(b>>31)==1?f(~b-1)|-2147483648:f(b);
where f(b) would be the operation on an unsigned number.

Also, for that color converter, couldn't you just take each eight bit color value, and bit shift it either three or two bits to the right, then shift each of those back over and "or" em together?


Also, for the modulus problems...
for an unsigned number, the following is true:
a % 2^b = (a<<(32-b))>>(32-b).




Also, just saying, the issue with the whole signed int only appears if the number has important bits close to the very first bit. For example:
01000000 00000000 00000000 00000000=2^30
2^30<<1=10000000 00000000 00000000 00000000
so, for a signed integer,
2^30<<1=-2^31 (waaa!)

Likewise, -2^31>>1=2^30.

[edit]

Of course, all of what i'm saying about signed and unsigned ints may be totally unimportant (except for the modulus ones) if the numbers stay pretty close to zero (since the highest bit shift is 6, the 7 leftmost bits should either be all 1s, or all 0s).

I must say that I don't entirely follow the operations you posted, but I suppose you are trying to preserve the sign bit. The point is that shifting is clever enough to preserve the sign, but the & operator (binary "and") doesn't. You can test it in the compiler (I did, to be sure): write a test program to shift a negative variable left and right and the result will still be negative because the processor "cycles back" the sign bit, as long as you don't have an overflow, it will be OK. But if you use & then the sign is lost. That's why I didn't worry about sign in the shifting operations but I worried about negative numbers in the modulus calculation.

If you want to employ binary operations to try to preserve the first bit, the problem is that you need to know how long the integer is and that will be different on different machines (16, 32, 64 bit?) so the code cannot be general.

For the colour converter: if you look at the function, what you say is exactly what I did in the end... I took a longer road to get there because I started from the principle that the ratio of the values in relation to the maximum value must be the same. But the final equation really just shifts the bits right by 2 or 3 places and then shifts them back.