Here is one I have had multiple times, although not phrased exactly the same way:

• Implement an RLE Compression algorithm (using either c-style string or std::string as input\output, this would depend on the interviewer they may even let you pick)

In an interview for a game company I was asked to write a function that will reverse a string without using the string class (i.e. use a null terminated char array).

I've seen that one, plus simple extensions like - for each word in the string, reverse the letters in the word, or, reverse the order of the words that make up the string, etc...

These kinds of questions are just to make sure that you're competent at basic, low-level programming concepts, like pointers and bytes.
In this category, you'd probably see other questions like, how would you test if the highest bit in a byte is set, or, how would you count the bits set in a word, or, how would you multiply a number by 8 without using multiplication, etc...

There's also questions that don't require you to explicitly write code, but say a lot about your ability to write code, like:
If you've got two classes that are dependent on each other (i.e. a circular dependency), how would you break this dependency?
Is inheritance useful for code-reuse?
What is the big-O complexity of inserting an item into a sorted array?

I was really hoping at least one candidate would say 'well, why not just have a lookup table', but sadly it never happened...

No one broke out the leet bit-twiddling skillz?
[font="Courier New"][size="1"]count = (((((v - ((v >> 1) & 0x55555555)) & 0x33333333) + (((v - ((v >> 1) & 0x55555555)) >> 2) & 0x33333333)) + ((((v - ((v >> 1) & 0x55555555)) & 0x33333333) + (((v - ((v >> 1) & 0x55555555)) >> 2) & 0x33333333)) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;[/font]

They ask for source code to reverse a linked list at Morgan Stanley, 2nd interview (just in case anyone was curious).
In the 3rd interview they ask you to make a date class which can print the month names and the number of days in each month, accounting for leap years. They tell you leap years occur and your job is just to make sure you implement that logic correctly.
You can also expect a lot of questions about design patterns.
There was only one question I could not get, and frankly to this day I still do not know the answer. I wish I could remember exactly how the question was phrased.


Other miscellaneous problems:
#1: Draw a BVH in 2D.
#2: Convert a string to an integer (manually).
#3: Pick a random number between 0 and 110 which is a multiple of 10.
#4: Given that the variables A and B are 32-bit unsigned fixed-point variables with 4-bit fractions, how many fractional bits will the results of each of these have?
-> A: A + B
-> B: A * B
-> C: A / B
#5: Given 2 axis-aligned boxes in 2D, outline an algorithm to determine if they overlap.
#6: Rewrite the following function so that the multiplication or division operators are not used and there are no loops:
int MultiplyInputBy123( int input_value )
{
return input_value * 123;
}

#7: Is C++ slower than C? Why or why not?


L. Spiro

This comes up a lot: "When and why should destructors be declared virtual?"

Perhaps the toughest interview question is the one you know the answer to but the interviewer has wrong. ;^)

I once had an interviewer ask me this:


class Base
{
public:
int X;
virtual void SetX() {X = 1;}
Base() {SetX();} // <-- Call to a virtual function in the base class constructor.
};

class Derived : public Base
{
public:
void SetX() {X = 2;} // <-- The virtual function is also defined in the derived class.
}

int main()
{
Derived MyDerivedObject; // <-- An object of the derived class is created.

// What is the value of MyDerivedObject.X ?

The interviewer thought (as programmer often do) that it was a clever question because he had stumbled upon it the hard way. I happened to know the answer. But he'd never really figured out what was going on when he ran into this problem, and he had the answer wrong.

After hearing his incorrect answer, I would explain why this is a special case, including the logic behind why this is a special case, and if he persists that I am wrong, I would finally say, “Okay, let’s make a deal. You check that on any compiler, and if I am right, I get hired unconditionally. If not, I pay you personally $100.”


L. Spiro