When you interview for a technical position such as a Software Development Engineer aka SDE position at Microsoft you will be asked one or more coding questions (aka coding exercises) as part of your interview loop. Sometime you even get asked a coding question as part of a technical screening (a short 1-hour interview prior to the hiring manager making a decision to make a full interview loop or not).
A bad -and rude- interviewer, and you found them even at Microsoft, will ask you the coding question and then leave you solve the solution in silence while he does something else. A good interviewer will ask you to talk aloud what is going through your mind while you solve the exercise so he can understand your thought process.
Typically you will have the choice of the programming language for the answer, although the interviewer may pick a specific language from your resume. C, C++ or C# are typically used at Microsoft and your interviewers will be familiar with them. Java is seldom used, so unless it is the language you are most effective with, I would advise to avoid it.
Often you will be asked to provide test cases for the code you implemented, to validate and stress it. In real life, when you implement a method or function, you should write so-called unit tests which will validate your code, but also protect it from regression when the code is later modified by yourself or your colleagues.
The coding question varies in difficulty depending of the level of position you interview for, but also varies with the interviewer. For a junior position, or SDE (I), you should expect to be asked to code a function or method to manipulate basic software data structure.
The canonical data structure is the linked list http://en.wikipedia.org/wiki/Linked_list ; the canonical function is reversing the linked list. There is no particular trick to reversing a link list. Link list manipulation are good questions to validate basic coding capabilities of college graduate – they should be familiar with the data structure and its manipulation from their course.
Other typical data structure is the string, and the matching function is to reverse the words from the input string. A trick for the reversal of words is to reverse the entire string character by character, then to reverse again the characters in each words. The repeatition of the resersion causes the characters in each words to be again in the same order. The benefit of such approach is that you can do the reversal in-place without allocating temporary memory or using a target buffer different from the source buffer.
Anoter typical coding question is to re-implement the basic C function of memcpy http://msdn.microsoft.com/en-us/library/dswaw1wk(v=vs.71).aspx . You have to implement an iteration that will copy word by word (the word is a unit of bytes). Note that it is more efficient to copy by the unit of bytes matching the CPU architecture, i.e 4 bytes or 32 bits for a 32 bit x86 CPU, 8 bytes or 64 bits for a 64 bit amd64 CPU. Also, if asked to code the memcpy function, you should expect your interviewer to ask you what would be good test cases for the code you implemented. One case he will point out is the case where the input and the ouput buffers overlap. You can either code pointer validation code which can then branch to copy the buffer in a different sequence to guarantee the output, at a small cost to performance, or you can simply declare the behavior of the function is not guaranteed if the buffers overlap (i.e. the caller should not use the method for that). Lack of guarantee is actually how the real memcpy function is defined.
A harder coding question which should not be asked to a junior candidate is for instance touching pattern matching, such as finding all occurences of a string in another string and replace the occurences with a new string. While the question may appear initially simple, the handling of repeatitions in the input string makes even the brute force approach non-trivial as you have to back-track everytime you find the first non-matching character of a partial match. More details on wikipedia, including the most efficient pattern matching / string searching algorithms to date http://en.wikipedia.org/wiki/String_searching_algorithm . Note that the basic trick is to test the character of the input string at the offset equal to the length of the pattern to match. If that character is not matching any of the characters in the pattern, you know that there is not possible matching starting anywhere before this offset, and you can proceed further. In the other case, which character you match leads to a reduce set of possibilities at to the position of the match in the input string.
A failry poor but unfortunately common coding exercise is to write a function that resolves the game of Sudoku ( http://en.wikipedia.org/wiki/Sudoku ). Unless the candidate is much familiar with the game, or even has previously coded a near-optimal solution, it is very unlikely that he can come up with anything else than a brute force approach in the reduced time of an interview (1 hour) and the difficult medium which the witheboard is.
Even if the interviewer’s expectation is not reasonable, you should play the ‘game’ of the interview – learn the typical questions and their answers (understand them! Don’t just repeat them!). It will allow you to clear these code validation questions and get to the meat of the interview.