Monday, March 17, 2008

Interesting tech interview questions

I've given numerous tech interviews in the span of the last 4 years or so and I thought I could take time to share some question from a few of them. Of course, I don't intend this writeup to be a ready reckoner for interviews, you might be better off going here. I rather wanted to share some good and some not so good questions I have been asked in tech interviews just to give an idea of the staggering variety and yet the common undercurrent in these questions.

I must admit that though I love interesting questions, I generally hate questions that rely on quirks or little known facts in a language or technology. These questions are binary in nature, you either know the answer (because you have read it before) or you don't know. These binary questions are pretty difficult to figure out by thinking hard. They also don't allow a discussion around the question, which is the whole intent of the interview: "to get the candidate talking on technical things and figure out how good he/she is". Joel has an excellent article on this here.

Now, on to the questions.

1. How would you implement your word count program in C++ ? (this was in a phone interview).

Fair enough, I got going about how I would implement it only to be stopped by the interviewer abruptly. He didn't want to know about my logic, he just wanted the code. I started off rattling that I would parse my input string only to be interrupted with "But you don't have a main() yet, so things are not going to work". I started to say that main() would call my wordcount() method only to be interrupted again with my code missing preprocessor directives and a return type for main(). By this point, I was a bit flummoxed because he was expecting me to recite code over the phone. This continued for the next 15 minutes where he pointed out every missing semi colon and brace. At the end of it all, he started comparing my code with a solution he had handy and emphatically remarked that I had made 16 deviations from what was optimal code. And most of these deviations were in the parameters passed and the data types used. What a dork !

The basic idea behind this question is to identify words in a sentence(s). This can be done by identifying word separators and incrementing the word count whenever we encounter a separator. The usual word separators (the characters that separate one word from another) are ' ' (whitespace), comma, period, semicolon and newline.


2. How would you print out something before entering main() in C++ ?

Now, this seems to be a famous interview question yet binary in nature. If you know the fact that global class objects get initialized before main gets called or global variables who initialize from a function return value will be called before main, you would be able to answer this question. I didn't know the latter and was interested in knowing why someone would want to print something before main() gets called. The interviewer simply said "we prefer our programmers to work on requirements without asking too many questions". No wonder I decided not to talk to them ever after.

The usual ways to do this, declare a global variable that gets initialized from the return value of a function and execute your print within the function.

int a = foo();
int main()
{
...
}

int foo()
{
std::cout << "printing before main"; return 42; }


Global class objects will be constructed before main gets called and hence, putting a print statement in the constructor of the object will achieve the same results.

class A
{
A()
{
cout << "Printing before main"; } };



3. What is Coercion by Member Templates in C++ ?

Coercion by what ? I could only take a guess because this seems to be a C++ idiom I am not aware of. This was followed by a question on Policy templates and Policy classes. Flummoxed again. The final nail in the wall was "What is RAII". I at least knew it stood for "Resource Acquisition Is Initialization". It's a technique used for ensuring clean-up for dynamically allocated storage and usually involves putting some code in the destructor that will be invoked always and will trigger clean-up. I had some follow up questions on problems with RAII and I couldn't think of any other than C++ error throwing mechanism that could prevent the clean-up code from getting called. That apparently was not the right answer because the interviewer shook his head vigorously.


4. How would you sort 1 million integers with only 2 MB memory and no storage. You are allowed to output results to a display. Optimize the solution for space first and then time.


Cool. This is an interesting question in many ways because there is no one line answer and no truly best solution. Hence, it leaves a lot of room to discuss CS concepts. I am not going to try and answer this question here since it's too involved but I would like to point out that choosing the correct data structure, choosing the correct (sorting) algorithm and applying data partitioning and slicing techniques would be the general direction to take.


5. What is lazy evaluation in C++


It's a technique that is alternately referred to as "construct on first use". It involves using a local static and putting that local static into a function. eg. If I want to call a method JumpAround() with a "foo" object inside another struct/class and if the foo object is not initialized before calling the method, it could lead to strange errors.

To fix this, we call the method JumpAround() like this

bar().JumpAround()

bar()
{
static foo obj;
return obj;
}


6. What is a virtual constructor in C++ ?

It is a feature that is not supported by the language itself. Let us examine why. The keyword "virtual" implements run time polymorphism or late binding. In an inheritance hierarchy, it is usual to call any class method using a base class pointer (or reference). Since a base class pointer has enough information to call any derived class method which is originally declared and/or defined in the base class, this idiom allows us to use a single pointer and call any member function in an inheritance hierarchy.

We fully expect function binding to happen, based on the "pointed to" object and not on the type of the pointer itself (which is merely a container). "virtual" merely ensures that this late binding or object type determination happens correctly. The keyword here is "type identification".

Based on the type of the object pointed to, we expect the base class pointer to call the method of that object. Since this whole implementation depends so heavily on the type of the object, we expect that the object is fully constructed and open to introspection and run time type identification (RTTI).

If we wanted a virtual constructor idiom, we are asking to call a constructor (which is also a member function) based on type determination of an object which is not fully constructed yet. Essentially we are trying to call a member function on an object that is still undergoing construction. This could lead to difficult errors and hence the language doesn't allow constructors to be virtual. (Destructors on the other hand can be virtual and are usually so when you have virtual functions in a class. "Thinking in C++" by Bruce Eckel available here has an excellent chapter on this, read it)


7. Does late binding work inside a constructor ? [OR] Can we call a virtual function inside a constructor ?

You can call a virtual function inside a constructor but you might not get expected behavior always. This is because the virtual mechanism breaks down inside a constructor and all function calls are mapped to member functions of the same class as the constructor. No late binding or type determination happens and this is precisely the reason why constructors themselves can't be virtual. Read the previous answer and also Eckel's chapter on "virtual" to understand this better.


8. Can we use "this" pointer inside a constructor or destructor ?

You can, but it is redundant. The compiler automatically makes all function calls and data member access using "this" unless you have used explicit scope resolution.


9. In an array of integers, how do you determine the longest continuous sequence with the greatest sum ? (Hint : Array could have negative integers as well)

I am not going to answer this since it seems to be a popular interview question and the answer is readily available if you know how to use a search engine.


10. Which operators cannot be overloaded in C++ ?

Direct member access operator .
De-reference pointer to class member operator .*
Scope resolution operator ::
Conditional operator ?:
Sizeof operator sizeof

Similarly, any of the new casting operators: static_cast<>, dynamic_cast<>, reinterpret_cast<> and const_cast<>, as well as the # and ## preprocessor tokens, may not be overloaded.

I would expect a lot of people to know which operators can't be overloaded but very few know why. The reason is this, most of these operators take a name instead of a value as an operand and the language will not allow names to be manipulated.

For eg,

A obj;
obj.myFunc();


obj.myFunc() calls myFunc() method on the obj object. The compiler usually converts the function call into something like this A::myFunc(obj&). You will notice that A:: refers to a name and not a type and there is no way this can be overloaded.

# cannot be overloaded since it is a preprocessor directive and the preprocessor is not aware of overloads.

Closing thoughts on operator overloading : Eckel calls operator overloading as syntactic sugar, a way to keep using the operators we are familiar with to perform their "usual tasks" on user defined types as well. I would personally avoid operator overloading and implement explicit functions that will perform the task in question because overloading an operator merely makes code look familiar but hides certain internal details which could cause difficult bugs.

eg.

A obj1, obj2, obj3;
obj3 = obj1 + obj2;


In order to make this work, I would need to overload the '+' operator to sum two A objects and '=' operator since copy construction is involved here (in case a bitwise copy will not suffice which is what a compiler generated copy constructor will provide)

Though the snippet above is neat, it hides the fact that instead of '+', you are calling a function that adds the two objects for you (yes, operator overloading is implemented as a function call)

I would rather do this.

obj3 = obj1.add(obj2);

where add() is defined as below

A A::add(obj&)
{
// do your object addition here, usually adding corresponding member data (though not always)
// return an A object
}

I am hoping to expand this article with more questions (and answers). You will notice that more than a few of these questions demand a good understanding of OOP concepts and their application in a language like C++. I usually find that understanding data structures solves half the problem and knowing the best algorithm to apply for the problem at hand is also useful.

No comments:

Post a Comment