Friday, June 20, 2008
Monday, April 21, 2008
A Native American elder once described his own inner struggles in this manner:
"Inside of me there are two dogs. One of the dogs is mean and evil. The other dog is good. The mean dog fights the good dog all the time."
When asked which dog wins, he reflected for a moment and replied, "The one I feed the most."
Monday, March 17, 2008
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();
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.
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
static foo 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.
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.
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
// 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.
Sunday, February 03, 2008
"Microhoo", that's what a Microsoft-Yahoo conglomerate might become. The web has been going crazy over Microsoft's bid for Yahoo. A lot of people believe it doesn't augur well for the world but the same people also believe it's a good thing for the
I think this is a very bad move by Microsoft. They have traditionally done poorly on the web and have managed to keep their web offerings online by virtue of all that extra money from their desktop cash cows - Windows and Office. But times are changing and the world is moving away from a desktop-centric model. I, for one don't believe the web is set to replace the desktop anytime now. There are a bunch of things I would prefer doing offline no matter how compelling the online version is. Even though I would love my computing to happen on the cloud, the same cannot be said about my storage. I would still prefer a local (and private) storage area where the majority of my files reside.
Given that Microsoft don't get the web, it might seem logical for them to go buy a web giant and hope things would turn around. But that's exactly where the problem lies; "Microsoft don't get the Web". I would consider it an almost impossible task to do well on something I don't understand very well in the first place. Unless Microsoft understand what the web is all about, I doubt they can do well, no matter who they manage to buy. Yahoo will be a useful addition to Microsoft's arsenal but I doubt if a $44 billion purchase is warranted for what would merely be a useful addition.
Will Google sit up and take notice ? Sure. Will Microsoft's profits improve ? I guess so. Will it be game changing ? Nope, Sorry.
The areas that Microsoft would benefit almost immediately if they manage to acquire Yahoo would include online photo sharing, instant messaging, email and to a certain extent, groups. And photos is perhaps the only area that Microsoft could better Google outright if the Yahoo deal materializes. Yahoo Mail is certainly better than Hotmail and could supplant or improve Hotmail but it might not make a huge difference to the bottom-line other than a staggering increase in the number of users. However, GMail simply blows all competition away and I don't expect Yahoo to come anywhere close. Yahoo did try with their new
Yahoo search is not so much better than Microsoft's and I would expect the latter to retain their Live Search as the primary search offering. Yahoo and Microsoft already allow cross pollination on their IM platforms and they might be able to give Google a run for its money in this segment (given that Google hasn't done much to improve their IM platform lately).
The name of the game is online advertising and that's what Microsoft is vying for. They predict a $80 Billion market by 2010 and want a sizable chunk of that pie. Yahoo's
There are a lot of areas where Microsoft and Yahoo offerings will clash and it's going to be one hell of a mess as some of these services might either be collapsed to form a monolith or dropped altogether. The net gain for Microsoft might be more users and a small increase in their net revenue (not counting the cost of the acquisition). This is where things start bothering me.
Microsoft has become this giant that cannot do anything cool on its own, it needs to buy someone to make it happen. Sadly, Yahoo is more or less on the same boat and haven't done anything path breaking for a while now. I fail to understand how such a conglomerate can pull off anything spectacular (and they better, because $44 B is not small money even if it's Microsoft in question). There are a whole class of problems that Microhoo will have to encounter and it looks unsurmountable at this time.
Microsoft and Yahoo are two entirely different cultures and
Since Microsoft will end up being the dominant partner in Microhoo, they could enforce the "
If Microsoft does decide to act a responsible parent to Yahoo and lets the latter run its show and ensures a steady flow of money, the collective intelligence of both the companies could come up with offerings that give Google some serious heat. But I seriously doubt if this would happen. Microsoft don't have a single profitable division outside Windows and Office. (I know about XBox, shut up about XBox, it's seriously subsidized by the surplus monies from other divisions). Perhaps, a serious misstep by Google if it coincides with a coup by Microhoo could tilt the balances which I seriously doubt will ever occur. Google is not invincible, they are just very very difficult to beat. And if someone does manage to beat Google, I can bet it's going to be someone new or unexpected, not the usual suspects Microsoft or Yahoo, simply because if these companies could beat Google, they already would have.
Disclaimer : The writer is not affiliated to Google, Microsoft or Yahoo at the time of this writing.
1. I know about Live and also about how much it sucks and don't even get me talking about MSN.
2. GMail uses
3. I can't imagine Flickr on Windows servers or Yahoo Mail written in ASP.NET, I just can't no matter how hard I try.