What do I look for, when I hire.

Interviews are a shot in the dark. You never know the state of the candidate on that one date, and deciding his fate based on how he solves a certain analytical problem, has never seemed the right thing to me.
What they have done earlier: I always ask about one project that the candidate has done in her previous work experience that she is most comfortable with. I ask the candidate, to then, go in depth, and explain to me. There are a few things that I can assess from this question:

Depth of knowledge : While knowledge of depth first trees and red-black trees are important, what I feel is more important, is how they have applied this knowledge. I go deep and probe into the problem, assessing, how deep the candidate has understood the problem, and the involvement with which it was solved.
Applied problem solving: How was the problem solved? You can test, how the candidate has applied existing algorithm techniques, or data structures to solve this problem. I ask "why so?" and "why not?" questions to see if the candidate took these decisions in an informed manner, or was she just implementing what she was told.
Big picture : I typically ask, where the particular piece that was developed new, or fixed, goes in the large product, or project. This gives me an idea as to how much the engineer is focused on the larger picture. The great candidates would know exactly 'why' they are fixing a problem, or developing a new feature.
Customer empathy : Yes. Every project has a customer. It might be external, or internal, but everything has an end-user. A developer in another team, consuming your API is a consumer too. I ask questions on how the candidate kept the consumer in mind. You get a lot from this question.
Communication skills : Was the candidate able to explain to me in a structured, lucid manner, about the problem, and how it was solved? I place very high importance in this facet. This is not to be confused with presentation skills. I do not expect engineers to be brilliant presenters (they are a few, I know of, though!). But, they should be able to communicate well enough to QA, PM, Design, and management. Else, there is huge productivity wasted here.

Attitude towards learning: Let us all agree, that, there is no one who knows everything. No one. So the best candidate, to me, is one, who realises this, and has an open slate to learn anything that is required, to do her job efficiently. There are a few ways by which I gauge this. I ask how much the candidate has learnt in the recent past. I ask about good projects and bad projects in recent past. I look for, if the candidate mentions her learnings on good and bad projects. I ask if something completely greenfield is thrown at the candidate, what would she do? Her structured methodology to crack it. I look for google, quora, online MOOCs etc.
Team player: While this seems cliche, I place a lot of important in this. I observe the candidate keenly on behavioural aspects. I ask questions such as, how the interactions with other teams such as QA, Design, PMs are? I seed sly questions such as - "These designers just don't get technology, do they?" and observe. If there is one thing that I cannot tolerate, it is jerks. There is no place for brilliant jerks on my team. Sorry, cannot tolerate it. I will take a week more, with a slightly lesser brilliant engineer, but I would rather have fun doing it. Life is short. I want the engineer, and the team, to have pride in what they built, and jerks hamper this beautiful emotion.
Thinking process (PM interviews): I usually toss in a large green field project, such as "Growth for a Boutique Online Coffee Roasting Company". I give the PM a few minutes alone. Once back, we work through the scenario together. I gauge structured thinking process here. I see how the PMs are making assumptions and communicating to me. I watch how the PMs react to suggestions from me. Is she accepting everything I am saying? Is she contradicting appropriately? If so, how is the dialog? Prodded deep enough, you check attitude here as well. I can sense condescension from a mile away. I was thinking about all this today morning, and I thought, it would be good if penned these down here as well. I have been using these techniques for more than a decade for interviewing folks, and to a large extent, hit success. Sure, there were a few misses, but then, like I said, interviews are a shot in the dark. In the case of misses, you just need to realise it quickly and rectify.