I've been working in my first job for about 2 years now, and I've been "asked" to interview a potential teammate (whom I might have to mentor as well) on pretty short notice (2 days from now). Initially, I had been given a free rein(or so I thought, and hence agreed), but today, I've been told "not to pose bookish questions" - implying I can only ask basic programming puzzles and stuff similar to the 'fizbuzz' question. I strongly believe that not knowing basic algorithmic notations(the haziest ideas of space/time complexities) or the tiniest idea of regular expressions would make working with the guy very difficult for anyone.

I know i'm asking for a lot here, but according to you, what would be a comprehensive way to test out the absolutely basic requirements of a CS guy(he has 2 yrs of exp) without sounding too pedantic/bookish etc ? It seems it would be legit to ask C questions/simple puzzles only....but I really do want to have something a bit different from "finding loops in linked lists" that has kind of become the opening statement of most techie interviews !! This is a face-to-face interview with about an hour or more of time - I looked at Steve's basic phone-screen questions, and I was wondering if there exists a guide on "basic face-to-face interview questions" that I can use(or compile from the community's answers here).

EDIT: The position is mostly for a kernel level C programming job, with some smattering of C++ required for writing the test framework.