MATTHEW VENTURES
  • Home
  • Resume
  • Side Quests
  • Other
    • Professional Timeline
    • Recommendations
    • Tutorials
    • Research >
      • Glyph
      • NASA
    • Getting Into Game Dev

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

  • ​About the Author
  • Getting an Interview
    • ​TODO
  • ​Passing an Interview: Part 1
    • Non-Technical Questions
      • ​TODO
    • Memory Manipulation & Management
      • Bitwise Operators
      • Bitwise Operations
      • Binary / Hexadecimal​
      • Floating Point
      • Data Type Sizes
      • Alignment
    • ​C++ Specific Topics
      • ​TODO
  • ​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?
Compare the sign bit of both numbers to see if they are equal, an AND or XOR would work.

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?
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1. But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.

Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32

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 learned that the maximum value of a signed int-32 is 2^31-1, because of the 32 bits one needs to be used for the sign (hence the 31) and because one combination of bits is used to represent 0 (hence the -1). Because we accounted for 0 by lowering the maximum value by 1, we do not need to constrain the minimum value. Therefore the minimum value of a signed int-32 is simply -2^31.

Additional reading:
https://stackoverflow.com/questions/11243014/why-the-absolute-value-of-the-max-negative-integer-2147483648-is-still-2147483

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?
Step 1: Write 42 in hex.
I know that my answer will be a number with several columns. I start by writing out labels for my columns from right to left to assess how many columns I will need. First, 16^0 = 0, then 16^1 = 16. These two columns are respectively the 0's column and the 16's column. I know I will not need more than these 2 columns because the highest value I can place into the 16's column is 15 (F). And 15 * 16 is a value far beyond 42, which means I will not need additional columns to reach the number 42.
To determine which number to put in the 16's column, I divide 42 by 16. The result is 2, with 10 remaining. So I place a 2 in the 16's column and bring the remaining 10 into the 0's column. The 0's column is our final column and we place the entire remainder of 10 inside by using the letter A. Remember that each column can only have one digit, so when we need to represent a two digit number, they become letters (in this case 10-->A).
Our final answer for this step is therefore 2A.

Step 2: take 1's compliment.
In this case we are working in hex, so the 1's compliment is |#-15|. Let's apply this to both column values, 2 and A.
2 : |2-15| = |-13| = 13 = D
A : |A-15| = |10-15| = |-5| = 5
Our final answer for this step is therefore D5.

Step 3: add 1
In this step we add 1 to the entire number (not each column). Our 0's column is currently 5, 5+1=6. 6 does not exceed 15 (the maximum value we can hold in any particular column) so we don't need to worry about carrying over any values to the 16's column.
Our final answer for this step is therefore D6.

I should note that this D6 is represented by 8-bits. If it were instead a 16-bit representation, then we would have 00D5 as our answer to Step 1, and FFD6 as our answer to Step 3.

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?
Both int* and float* are pointers so they will both be the size of a pointer (we can disregard the int vs float distinction regarding the type of data we are pointing to). A pointer is 8 bytes ( 64 bits ) on a 64-bit system. So both of these will be 8 bytes.

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;
​};
Prior to compilation the size would be 2bytes (short) + 4bytes (float) = 6bytes.
After compilation, two bytes of padding would be added after the short so that the float will be 4-byte aligned. The resulting size is then 8 bytes.

Additional reading:
https://www.youtube.com/watch?v=c0g3S_2QxWM&list=PLW3Zl3wyJwWPmA00yqu9wiCREj4Of_1F8&index=15&ab_channel=JorgeRodriguez

Example

X
Practice Question: ​Example Question?
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1. But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.

Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32

More sections coming soon as I continue to port them from my Google Sheet: 
 tinyurl.com/gamedevStudySheet   <<<   You can view additional topics there!
  • Home
  • Resume
  • Side Quests
  • Other
    • Professional Timeline
    • Recommendations
    • Tutorials
    • Research >
      • Glyph
      • NASA
    • Getting Into Game Dev