Interview questions for developers

I get to participate a lot lately in job interviews. (I'm interviewing, that is...). When it comes to trying to see how technical is the candidate in front of me I normally ask one or more from the following questions:

1. "Please describe your part in a recent project." I then try to eliminate as much hype and buzz talk and get the candidate the draw a diagram that describes a system and its components. I then query about the exact locations where that person was developing and drill down from there. -- Here I try to understand how well the candidate can describe what s/he did, how well s/he communicates technical information, and of course, how well s/he knows what s/he was working on.
2. "Tell me about a bug or customer problem that you were responsible to solve. What was the problem? How did you realize what was the real cause? How did you solve the problem?" -- Here I try to see what counts as a "problem worth talking about", the organization and manner used by the candidate to solve the problem. I try to understand the methods and the tools used to solve problems of that kind.
3. When I see that a candidate lists a programming language other than the expected Java/C/C++, such as Lisp, Haskell, Perl, Prolog, etc. I tend to cook up a simple question suitable for that language (that is: something that is pretty easy to write down using that language) and ask the candidate. Unfortunately, I usually get disappointed when I either hear the candidate giving excuses why s/he cannot write down a solution, although s/he was bragging in the CV that this is one of the strong programming languages s/he uses. I do, nonetheless, sometimes get to see people who actually can write down some code in the programming language they say they know.
4. Depending on the area of expertise of the candidate, I then ask a few questions in that area.

Here are some questions that I sometimes ask (it's pretty easy to make up new questions):

1. Please implement a function that receives an array of integers and the size of the array and returns the same array sorted. For example, for a given array {1,3,5,11,2,2,7,41,17,3,3} the resulting ordering of the array is {1,2,2,3,3,3,5,7,11,17,41}. Please make sure you take into consideration the following requirements:
1. For every number i in the array, i is equal or greater than 0 and equal or less than 100.
2. Your implementation should be as efficient as possible.
3. Note that the returned sorted array must use the same memory as the received array.
2. Please write down the definition of a C structure that describes a node in a tree data structure. Note that a node in a tree can have zero or more children. The number of possible children is not known.
3. Please write down an implementation of a function that receives a pointer to a node in a tree (the same node description you implemented in the previous question) and returns the number of nodes in the sub-tree, including the node itself.
4. Please implement a function that receives an array of pointers to some structure and the size of the array and returns the same array sorted according to the color field of the struct. The structure is defined elsewhere and is of no relevance to us. All you know is that the structure has a field color and that the possible values of that field are RED=0, GREEN=1, BLUE=2. (RED, GREEN and BLUE are constants representing the numbers 0, 1 and 2, respectively.). Please take into consideration the following requirements:
1. The array should be ordered in place, i.e., using the same memory.
2. You are allowed to use only a constant number of additional memory units that is not dependent on the size of the input. You may use a hint that the amount of necessary additional memory is proportional to the number of colors used.
3. Once a color field of an array element has been read, it is not possible to read it again. This means that you’re allowed to view the contents of the color field only once per array element.
5. Solve question 4 for the general case of K colors using O(1) of memory.
6. Please describe a hashtable data structure, specify a hash function for it and explain the probability for a collision using your hash function.
7. Please describe an algorithm that accepts a pointer to a tree node of the same kind of the one in question 2, that can locate tree nodes that have child links to some ancestor node, i.e., can locate all loops. Reason about the complexity of your algorithm.