Get Into GameDev or
​"Cracking the GameDev Coding Interview"

This book will cover: how to get an interview, pass the interview, and ultimately break into the video game development industry!

This book is a WORK IN PROGRESS it is presently being ported from a word document. View the full document here: tinyurl.com/gamedevStudySheet
Picture
Half-Life enthusiast breaking into the video game industry

Introduction

Table of Contents
  • ​Passing an Interview: Part 2
    • General Computer Science Topics
      • Data Structures​
      • Multi-threading​
      • Common Algorithms​
    • ​General Software Engineering Topics
      • Programming Patterns​
      • ​Programming Design Questions​
    • ​Maths
      • ​Matrices
      • Rotations
      • Dot Product
      • Etc.
    • ​Personal Questions
  • ​After an Interview
    • ​TODO
  • During the Job
    • ​TODO​
Vertical Divider

About The Guide / Author

This guide is fool-proof! I would know, because it worked for me and I am often-times foolish. I wrote this guide over many years of many job interviews for Gameplay Engineer positions. After each interview, whether it went well or not-so-well, I amended this guide to include everything that I needed to know to pass that interview. It’s still a work-in-progress, and probably will be forever, as I continue to learn! Please let me know where I can improve it.

Note: This was not originally imagined as a beginner’s guide. It was written as a reference sheet to have during a workday or interview for folks who already knew the content. So if you come across something you don’t understand, you may need to Google the topic. I am presently expanding it to be more instructive. Thank you for your patience.

This book was inspired by Cracking the Coding Interview, an excellent book for general computer science interview questions. I highly recommend reading that book prior to this one if you are new to coding.
Picture
WIP book-cover design

Bitwise Operators

It seemed to me that the best place to start this guide would be with the very building blocks of all data: bits. Bits are our smallest unit of data and are used to compose all of the larger data types we will discuss later on. A bit is a single number: 0 or 1 aka "off" or "on". Usually when we need a two-state variable we will use a bool (more about those later) but they are 8 bits! So to save space, it is common to instead discretize our bits so that each bit in an 8-bit structure can represent a different parameter's on/off state. When we treat each bit in a data type as its own value, that's called a Bit Field. Now, instead of only two states, we can represent 8*2 states within the same 8-bit structure! And if we consider several bits within a bit field instead of just one at a time ( a process called Bit-Masking ) we can represent many more combinations!

To manipulate a single bit within a bit field, we can use the following operators:
  • & “AND” is 1 only if both bits are 1
  • | “OR” is 1 if any of the two bits is 1
  • ~Takes one # and inverts all bits
  • ^ “XOR” is 1 if the two bits are different. “One or the other is 1, but not both”
  • << “left shift” bits of the 1st operand, 2nd operand is the # of places to shift
  • >> “right shift” bits of the 1st operand, 2nd operand is the # of places to shift

Bitwise Operations

Let's crack straight into it by putting these bitwise operators into practice! Below are the most common operations which we may need to perform upon a bitfield.
  • Setting a bit: Set the nth bit to “on” aka “1”. If n=0 then you are setting the LSB.
    • number |= 1UL << n;   ( UL means “unsigned long” )
  • Clearing a bit: Clear the nth bit to “off” aka “0”. If n=0 then you are setting the LSB.
    • number &= ~( 1UL << n );
  • Toggling a bit: Flip the nth bit between values of 0 and 1.
    • number ^= 1UL << n;
  • Checking a bit: Returns 1 if the bit was one and 0 if the bit was off. Extracts a value.
    • bit = ( number >> n ) & 1UL;
  • Checking a mask: Returns true if the number is the same as the mask.
    • wasMaskOn = ( ( number & mask ) == mask );
Picture
Several bits socializing together
Practice Question: What's the fastest way to tell if 2 signed floats are the same polarity?

Binary / Hexadecimal Numbers

The bits we discussed above have two states ( 0 or 1 )  a number described in bits is called binary ( "bi" meaning two, as in two states ). But you (assuming you are also human) are probably used to numbers in decimal format ( 10 states ). Binary numbers are simply another way of representing decimal numbers and they're specifically an easier format for the computer (composed of binary switches). Another common format is Hexadecimal ( 16 states ), its compactness makes it easier for humans to read. As a video game programmer you will be expected to translate numbers between these formats. You should be very familiar with the following powers of two.
As a pneumonic, I have memorized that "2 to the 6 is 64", which helps me jump to adjacent powers such as 2^5 with a simple 64/2. The most important one is 2^8 which you should have memorized as 256. This is an incredibly important number because it is the total number of possible numbers which we can represent with an 8-bit value. This is why an unsigned int-8's maximum value is 255 (it would be 256 if we did not also need to represent 0). Using this understanding we can easily calculate the maximum value of an arbitrarily sized integer, let's give it a try!
20 = 1 | 21 = 2 | 22 = 4 | 23 = 8 | 24 = 16 | 25 = 32 | 26 = 64 | 27 = 128 | 28 = 256
Practice Question: What is the maximum value of a signed int-32?

You may have noticed that I tried to trick you by asking for the signed max instead of the unsigned max. Since we are representing a signed number, we need to divide all possible permutations of our 32 bits into  three categories: positives, negatives, and zero. With three categories we cannot evenly divide the permutations. The result is that the absolute value of Int32.MinValue is not equal to the absolute value of Int32.MaxValue. Hopefully this provides a small a hint to address the next practice question. 
Practice Question: What is the minimum value of a signed int-32?

We are about to jump into Two's Complement which is the way fixed-point numbers (such as ints and longs) are represented. We will cover binary and hexadecimal approaches but before we do, I want to provide you with this useful list to remind you of how two digit numbers are represented in Hex (this will come in handy very soon!).

Decimal:    0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  10  |  11  |  12  |  13  |  14  |  15
Hex:           0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |   A   |   B   |   C   |   D   |   E   |  F

Positive numbers in binary:
Representing numbers in binary or hex is a simple process of first understanding what exponent each column of the number represents and then calculating the total value in each column. I explain this in detail within the following video. 
Two's Complement:
On an interview, it is more likely you will be asked to represent a negative number because that process requires you to understand the positive representation in addition to two more steps. In total, the three steps to writing a negative number in binary or hex are:
- Write the number
- Take the 1's complement
- Add 1
Here are two simple examples that break down the process into those simple steps.
“Please write -5 in binary”
Step 1: write 5 (as an int8)
0000 0101
Step 2: take 1’s complement (invert bits)
If binary just swap 1’s with 0’s and vice-versa
1111 1010
Step 3: Add 1 (so it’s 2’s complement)
​1111 1011
“Please write -2 in hex”
Step 1: write 2 (as an int8)
02
Step 2: take 1’s complement
For hex, just do |# - 15| or (# + 15)%16 ( ex. the 0’s become F’s)
FD  (or 1111 1101 in binary)
Step 3: Add 1 (so it’s 2’s complement)
FE
Step 2 for hex numbers is normally the hardest part for students because they learn it in the binary example as "simply swap the 1's and 0's" and suddenly that simplification does not apply for hex examples. It may be easier to think of the 1's complement as |#-Max| where # is the current digit and Max is the largest value that digit can hold. This approach works in both cases.
- For example, in binary the Max is 1, so this applied to a 0 will yield: |0-1| --> |-1| --> 1
- And in hex, the max is 15 or "F" (shown in our list above), so this applied to 0 will yield: |0-15| --> |-15| --> 15 or "F"
This approach will always work, whether it's binary, hex, or maybe even octal that we need to convert.

Additional Binary & Hex Notes:
- If asked for HEX_1 - HEX_2, instead do... HEX_1 + ( 2’s complement of HEX_2)
- 0b10000 will declare 16 in binary, the b means binary
- 0x00000010 will declare 16 in hex, the x means hex
- Each hex number is represented using 4 binary bits, hex notation is simple an abbreviation

Misc Numbers Info:
You should be familiar with the ASCII table. Know that it has 127 entries, and know that A is 065
Endianness: this term refers to the order in which a number's bits are stored.
----- Big-Endian = stored starting with most-significant-bytes
---- Little-Endian = stored starting with least-significant-bytes.
---- Note: Little-Endian is the widespread default.
For storage, you should prefer data types that express the exact size such as int_8 instead of the generic int.

In the next section we will discuss an alternative way to represent numbers that will allow for decimal values.
Practice Question: ​How would you write -42 in hex?

Floating-Point Numbers

We just explored how Fixed-Point numbers are represented at the bit level. Fixed-Point is great for whole numbers, but when we need to express decimal numbers we use Floating-Point numbers. Floating point numbers have an interesting tradeoff, they can express very large numbers (both negative and positive) but as the magnitude of the numbers increases, it decreases its precision. Here is how a float is laid out in memory:

 1 09876543 21098765432109876543210
+-+--------------+---------------------------------------------+
 |         |                             +-- 23 significand / mantissa (normal binary #)
 |         +----------------------------- 8 exponent (128 - value of the exponent)
 +-------------------------------------- 1 sign bit (if 1 then it's negative)
​
An interesting decision was made here. The float's designers chose for the exponent bits to represent a number that would be subtracted from 128 instead of representing the exponent itself. That allows for fractions because a large number subtracted from 128 will yield a negative exponent.

TODO: because floats are an approximation, they can be lossy. Discuss how adding big numbers with small numbers can lead to loss of data and how to approach fixes to this phenomenon. Include mention of IsNearlyEqual and IsNearlyZero. Include a practice question to code a method such as IsNearlyEqual.

A float's lack of precision at large magnitude's is its general downside. This was a big problem for Minecraft, dubbed the Far Lands. In God of War, the team resolved this issue by introducing intermediary transforms for the level sections so that at any given time you only need to make calculations relative to a somewhat-nearby origin (so the numbers never got too big). In Star Citizen, the team used double precision floating point values (these "double's" act like floats but they're double the size). I think the latter approach is extraordinarily rare, developers usually avoid doubles because they take up so much space. In the next sections we will explore the relative sizes of these objects and the consequences they have on memory layout.

Data Type Sizes

Let's begin by covering the memory footprints of several common data types. In an interview, candidates will be expected to recite these values from memory. Note that 1 byte = 8 bits. Also note that the size of several of these types varies depending on if the processor size (32-bit vs 64-bit). However, since the first PlayStation, pretty much all development has been focused on 64-bit processors. More historical context here.
Data Type
32-bit Size
64-bit Size (if different)
Representation
Bool
1 byte ( 8 bits )
-
-
Char
1 byte ( 8 bits )
-
-
Short
2 bytes ( 16 bits )
-
-
Int
​4 bytes ( 32 bits )
-
Two's Complement
Long
​4 bytes ( 32 bits )
​8 bytes ( 64 bits )
Two's Complement
Float
​4 bytes ( 32 bits )
-
Floating Point
Double
​8 bytes ( 64 bits )
-
Floating Point
Pointer
​4 bytes ( 32 bits )
​8 bytes ( 64 bits )
-
While an Int is 32 bits by default, we often need to represent a number with a much smaller range. For these cases we can save memory by using a Int type of explicit size such as  int8_t which only uses 8 bits. More details ​here.

Since pointers are used to represent memory addresses, the pointer's size (and therefore it's maximum value) implicitly defines how much memory we can use. A 32-bit pointer can only access values up to about 3.5 GB of RAM (this is a serious limitation), whereas a 64-bit pointer could theoretically access values up to 17 Million GB of RAM.

Below are some game file sizes for perspective. Halo 1 (Combat Evolved) was released on the original Xbox (which was 32-bit) the later entries were released on 64-bit hardware.
Halo 1 (2001) - 1.2 GB
Halo 2 (2004) - 20 GB
Halo 3 (2007) - 55 GB
Halo 4 (2012) - 55 GB
Halo 5 (2015) - 95 GB
Practice Question: How large is an int* on a 64-bit system? What about a float* on a 64-bit system?

Alignment

With some rare exceptions, the size of a data type also determines an attribute called its "alignment". For example, an Int is 4 bytes large and therefore 4-byte aligned. When data types are stored into memory they are stored at the next available alignment boundary of appropriate size. Let's break that process down with an example. In the diagram below, I marked the 4-byte alignment boundaries with X1, X2, and X3. If we wanted to store an Int at Y1 (position 2) we might instead add bytes of padding at position Y1 and Y2, then we could place the Int at position X2 so that it is aligned. In simple terms, we find the next 4-byte aligned address by determining the next address that is a multiple of 4.

Data:          X1                Y1     Y2      X2                                     X3                                   
Address:    0   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |   10

Aligning data can drastically decrease the time it takes to access it, and some processors actually cannot perform reads on unaligned addresses. In C++, the compiler will automatically align data which can lead to some interesting behavior. For example, take the following struct on the left:
​struct MixedData{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
​};
This struct (on the left) is 8 bytes large prior to compilation:
1byte (char) + 2byte (short) + 4byte (int) + 1byte (char) = 8 bytes

However, after compilation, the compiler will add padding to align the data as shown on the right. These additional 4  bytes of padding mean that this struct will actually use 12 bytes of memory.

The trailing 3 bytes of padding are due to the struct assuming more MixedData's will be declared after it (as in an array).
struct MixedData{
    char Data1;           
    char Padding1[1];  
    short Data2; 
    int Data3;
    char Data4;
    char Padding2[3]; 
​};
TODO: Why would it need to 4-byte align the next MixedData if MixedData starts with a char? Aren't char's 1-byte aligned?
​
To reduce the amount of padding a struct will need, structs should always be laid out with data members in order of descending size. Note that you can explicitly tell a compiler to not add padding by wrapping a struct in: “#pragma pack(push,1)” and “#pragma pack(pop)”.
Practice Question: ​What is the size of the following struct before and after compilation?
​struct MixedData{
    short Data2;    
    float Data1;
​};

Example

X
Practice Question: ​Example Question?
More sections coming soon as I continue to port them from my Google Sheet: 
 tinyurl.com/gamedevStudySheet   <<<   You can view additional topics there!