Firstly, write actual code to solve a simple but real, or at least realistic, problem. That could be a take-home exercise, or it could be on-site pair programming, or some other format. Memorable examples: a stock exchange (submit orders, get trades); a Tetris engine (submit blocks, get rows filled); an auction house (submit bids, get winners); an uploader for the Azure blobstore (submit blocks, get files); an online metric summarizer (submit samples, get summaries). This tests someone's ability to actually write code.

Secondly, suggest an algorithm for a real, or realistic, problem that doesn't have a well-known good solution. Memorable examples: subset-sum, but on an ordered set, where the solution must be contiguous; placing primers for PCR [1]; online k-anonymisation [2]. This tests someone's ability to think on their feet, and synthesize facts they've learnt into something new.

I'm a bit dubious about the "tell me about something you worked on" question. Firstly, because it requires the candidate to have worked on something chewy, and there are lots of capable people out there who are unfortunate enough to have had crummy jobs where they don't get to do that. Secondly, because it attempts to evaluate the judgement of an individual by looking at the work of a team. Too often, as a candidate, i've had to answer "why did you do it that way?" with "because the client specifically asked for it" or "because my colleagues who were working on it at the time decided so", which isn't useful for me or the interviewer.

[1] http://wiki.c2.com/?StridingAcrossSteppingStones

[2] https://en.wikipedia.org/wiki/K-anonymity