Archive

Archive for the ‘Interview Questions’ Category

How to detect if a matrix is not orthogonal?

August 14th, 2014 No comments

So…. Some devs like to ask questions similar this and I’ve seen a lot of good potential applicants miss it. Which is okay! We all understand people might suffer the jitters and all that during an interview. But when you’re applying for a game industry job you can probably expect at least one good math question.

Okay so the key to solving to many warm-up interview questions is to ask yourself can you come up with a solution using Dot Product? Cross Product? A lot of interviews just want to make sure you understand how these things can be used rather than just seeing how good your memory is.

If I were asked this question. I’d probably clarify this is a rotation matrix. Right there, you know a rotation matrix is supposed to contain 3 orthogonal vectors (Up, Right, Forward). Any two of these vectors should be perpendicular to each other. So, taking the dot product between them should be 90 degrees (or rather, dot product of orthogonal vectors equals 1). If it isn’t, then the matrix is not orthogonal. There are other properties of an orthogonal matrix too. Such as taking the Transpose of this matrix will give you the Inverse.

And remember, you probably don’t want to rely on pure memory but rather you’d want to practice this. Take the dot product of two unit vectors like (1,0,0) and (0,1,0) a couple times on paper.

Categories: Interview Questions Tags:

Prefer Composition over Inheritance

April 16th, 2013 No comments

Popular question, awesome anwser

Categories: Interview Questions Tags:

Swap Two Integers Without a Temporary Variable

October 20th, 2008 No comments

Good programming question that we were just discussing today. Wikipedia has the solution

Categories: Interview Questions Tags:

Const correctness

October 2nd, 2008 No comments


Fred * const ptr = NULL;
const Fred * ptr = NULL;

Q: Do these lines have the same meaning?
A: No. The first line declares a const pointer meaning the value of ptr cannot be reassigned. The second line means that the Fred object itself is const and it cannot be altered unless it has a mutable member declared (mutable members can be altered in const functions)

A lot of people no doubt miss this one. Read bout const correctness here

Number Ranges {Number Sets}

September 6th, 2008 No comments

One really good question I’ve seen interviewers ask is a basic math question dealing with number sets. Just to trip up the applicant just a little, they ask in reverse order.

If you have a number range {10….6} please find the number that is 10% within this number range.

This is actually a very good question to determine basic math skills. Dealing with Number sets might be used for Targeting gameplay systems whereas the joystick value is used to sample a number within a number set (for instance, the number set is our set threshold that we are sampling a value from).

Anyway the solution is simple.

First determine the difference between [x,y] where x=10 and y = 6

size = 4 (10 – 6 = 4)

This is the size of our entire boundary. Now, multiply the size of our number range by z (z = 10%)

result = size * z;(result = 4 x 0.10 = 0.4)

Next, take x and subtract the result to get our answer.

solution =  x – result;

solution = 10 – 0.4 = 9.6 or if its {6…10} then the solution is 6.4

Categories: Interview Questions Tags:

Bit Manipulation

September 2nd, 2008 No comments

Ericson brings up an interesting point on Bit Manipulation. Yep, it’s a very important skill to have and it’s not a bad idea to keep reviewing at the very least, the basics. I’m linking this article more for my own selfish reasons though. Many interviews will contain at least one Bit Manipulation question so this looks like a very good read. I have to go to bed so only made it halfway through atm. So will have to review it more tomorrow when I’m fully rested

Categories: Interview Questions Tags:

Write a Function to Detect if a Linked List is Corrupt?

January 28th, 2008 No comments

Code Sample: Visual Studio 2005 Solution and .cpp

This is a pretty common interview question to ask C++ programmers. The key to solving this one is to write a nested loop. The outer loop iterates through the nodes. The inner loop checks each node’s next pointer member for corruption (node that points to a previous one in the list). 

More efficient solutions can be found if you search, “How to Detect a Circular Linked List” such as the solution described here.

bool IsCircular(Node* head)
{
      bool circleFound = false;
      bool tailFound = false;

      if (head && head->next)
     {
          Node* slower = head;
          Node* faster = head;

          do 
          {
               slower = slower->next;
               faster =  faster->next->next;
               tailFound = ! (faster && faster->next);
               if ( ! tailFound )
               {
                   circleFound = (slower == faster || slower == faster->next);                                         
               }
          }
          while ( ! tailFound && ! circleFound)
     }

     return ( circleFound );
}

Determine the Maximum Depth of a Binary Tree

January 11th, 2008 No comments

Code Sample: Visual Studio 2003 solution (.cpp included) 

 The trick to solving this problem is to use Recursion to iteratively search through each branch of our binary tree and tally up how many nodes each node contains. Once you realize you need to take one parameter (depth) and return the maximum size for each branch from “each” node then you’re on the right track. So, the main trick you must do is at each individual node, examine the child, left, and right sibling. Store the number of nodes each branch reports back and store it off. Later, compare all 3 results to find the best number then return this maximum depth you discovered back to the caller.

I can’t recall if I’ve seen a Binary Tree blow the Calling Stack on a small memory machine offhand but I’ve seen other complex recursion routines blow through the Call Stack. So if you’re ever asked why Recursion can possibly be bad is because of limited memory assigned to the Call Stack.

Write a Program to detect a Palindrome

January 9th, 2008 No comments

Code Sample: Visual Studio 2003 solution and .cpp

This is another pretty good interview question that often gets asked. It can’t hurt to already know what a Palindrome is before you get asked this question. Palindromes are words that are symmetrical somewhat. A word like DOOD or TAT can be flipped and mean the same thing. Yeah, I know I just made up those words but hopefully you get the gist. This example makes good use of Asserts and pointer arithmetic.

bool isPalindrome( const char* str )
{
size_t len = strlen( str );
const char* head = str;
const char* end = &str[ len-1 ];

while( len > 1 )
{
if( *head != *end )
{
return false;
}

head++;
end--;

// decrement from our string length count for each string_ptr move
len -= 2;
}

return true;
}

Categories: Interview Questions Tags:

Programmer Interview Questions

January 8th, 2008 3 comments

I’ve been in the game industry for a few years now. I’ve been on the receiving end (getting interviewed) and on the attacking end (the interrogator). Most game industry interviews focus on knowledge of C and C++ however it is still helpful to know how to deal with Number Ranges, Vectors (Cross, Dot product), and good ole fashioned problem solving.

The link below is really good it contains many questions you might get asked:

http://vijayinterviewquestions.blogspot.com/

Off hand, I want to say at every single interview I’ve been asked at least one Bit Manipulation question, one question from the link above, perhaps a pointer question, smart pointers, and Big O notation which is explained in detail here and a more brief but very nice description can be found here. Know the complexity of array O(1), linear search O(N), hash table best- O(1) worst O(N), and binary search.

Others asked about preincrement operators and how they differ from post increment operators, Palindromes, detecting a corrupt node in a Linked List, differences between C and C++, recursive functions, bit operators, multiply a number by 8 without using mult/divide, etc. All of this is pretty much covered by the link above. Soon in the future I’ll give my own solutions for fun

Coding Horror has some good articles on phone interview questions (those aren’t game industry specific however). Keep in mind most game companies stick to C / C++.

Another pretty good subject is called ‘Bit Twiddling Hacks’. If you Goggle for this topic all sorts of interesting links will popup. These questions tend to be stuff I’d probably never ask a candidate but still they are probably very handy to know. I’d prioritize this as tricky, fringe stuff though thats just like handy to know. I’d prioritze the questions covered at the link above much higher (like Palindromes, etc)

Here is one interesting link for example:

http://graphics.stanford.edu/~seander/bithacks.html

Here’s a good example:

Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here       

f = (v & (v - 1)) == 0;

Design Patterns is something that is asked at almost every interview too. This link provides a very nice list.

Programmer Math Questions

Some standard math questions usually deal with Dot products so you’ll want to know them backwards & forwards. The key is realizing that two vectors that are in the same directions is greater than 0 (dot product == 1 when they are perfectly parallel). Two vectors that are perpendicular will equal 0. Two vectors that face opposite directions will be less than zero. You can take dot product of vectors to get a scalar that allows us to measure distance + get the angle between two vectors using arccos / atan2. For practice, I’d highly recommend just playing around with basic unit vectors on paper. Such as taking the dot product of [1,0,0] DOT [1,0,0] (parallel) and [1,0,0] DOT [0,1,0] (othogonal) and [1,0,0] DOT [-1,0,0] (opposite). By that same token, you really want to know bout Cross Product and how you can take inverse sin to solve for theta as described here.

More advanced tests may concern the distance from a point to the plane + ray vs plane + ray vs sphere intersection

Object Oriented Questions

Method Overloading

Method Overriding

Polymorphism

Virtual Inheritance

Design Patterns

Other subjects:
Difference between pre-increment and post-increment
Cast operators such as static_cast, dynamic_cast, const_cast, & reinterpret_cast
Good info about testing for Google (applicable to almost anywhere!)

Brain Teasers

Some developers like to ask “Brain Teasers”. Most of your AAA (triple A) game developers will not due to barely having enough time to cover the stuff covered above (3d math, C++ knowledge, etc). This is more common to business industry. One question I’ve been asked before is this about the City of Truth/Lies as discussed here.