Some Developer Interview Questions

Seeing as my "Favorite Java developer interview questions" entry was such a hit (read "controversial") I thought I'd follow-up with some more of questions I like to ask. I don't think these are nearly as contentious (I hope!) :-)

These however are more generic in nature - not specific to Java or any language/platform. Some may be for more senior developers than others (but I've had kids out of school be able to answer them too)

And once more - I'm not providing answers - hey just use Google ;-)

Basic OO Concepts
1) Define "Polymorphism"
2) Define "Encapsulation"
3) Define "coupling"? Why do we want "loose coupling" in our systems?
4) What is "cohesion"? Why do we want "high levels of cohesion" in the modules of our systems?

Code scalability / efficiency
1) In terms of Order notation, what is the best and worst complexity for "Bubble Sort"?
2) Now "Quick Sort"
3) Now "Heap Sort"

Puzzle Questions (yes I'm starting to ask a few of these - but very software related)
1) You have an array of 10 billion objects, how would you search it most efficiently?
2) How would you implement an LRU Cache in your favorite language?

Miscellaneous
1) What process do you follow for performance tuning of an application?
2) What is "refactoring"? (Note: I'm shocked how few people know this.)
3) Name for me your top 5 practices to deliver high-quality applications on time and on budget.

Don't worry I'm not giving away my "game" - if you get past each of these there's a myriad more drill-down questions to verify you really know it. Some are also pretty "open" questions.