[unshift]

couldn't agree more.

if i had to come up with a permutation algorithm as part of writing code, you'd better believe i'd look one up so that i'm sure i'm doing things optimally. i wouldn't trust myself to come up with the exactly right algorithm on the first try.

if i had to deal with some weird half-sorted array, i assume i'd be working in the same context as the problem and wouldn't have to make up a solution on the spot with limited details. why do you have a weird-ass data structure like that to begin with? that's the first question i'd ask.

personally i always ask a couple of simple questions (like FizzBuzz) and then talk experience. if you want to see a code sample, ask for one -- written on a computer, without someone hovering over the candidate's shoulder. coding solutions to weird questions on a whiteboard doesn't help anybody.

[aplusbi]

These questions aren't about "real world" situations, they are about problem solving and basic coding. Questions are good, as is a discussion on how and why these things should be implemented.

For the split array problem I rarely ask for code (only when I think it will actually help the candidate), it's just a discussion. It usually goes something like this:

    Candidate: Well I can sort it first, then do a binary search.
    Me: How would you sort it?
    C: I'd use quicksort.
    M: Can you do better than an nlogn algorithm?
    C: Well I suppose since it's two pieces that are both already sorted, I can just find where they are split and then rearrange them.
    M: How would you find the split?
    C: I can go through each number until they stop increasing.

And so forth. The "best" solution (that I've come up with, anyway) is to find the split using a modified binary search, and then use a regular binary search on the piece that might contain your query. Not everyone gets that and that's okay.

In addition to asking coding questions I always ask candidates about previous experience and projects they've worked on. Sometimes the answers to these questions are more important. Most of the people I have been interviewing, however, are recent graduates or students who are just finishing college and may not have much experience or many projects that really engaged them.

I spend a lot of time thinking about how I can improve interviews within the confines of how my company conducts them. I've stopped asking the permutations question as I feel that it has too much of the "aha!" factor in that either the programmer goes "aha!" and solves it or they don't.

[pp13]

You should highlight, recent college graduates. If someone does get hired to your firm, I hope the "real world" problems are just as interesting.

I actually like those type of algorithmic problems you highlighted. I am not sure, what it measures other than the recent graduate knew his/her data structures and read their MIT Algorithms books really well. Very few jobs do require knowing that fundamentals that in depth. Are we writing a Kernel, or a file system? Are we writing a new type of java collection.

The type of real world problems that in the class of the 2 problem solving problems you mentioned seem far in few, unless you writing something new, that really needs to be optimized in some way.

I think this is a real problem with computer science schools. It great to teach the absolute bare essentials. But I think schools should also teach some modern programming and not leave it on the kids to learn on there own.

College grads that know modern frameworks, Node, ROR, they know javascript and ruby really well. They have written some nice web apps. Those are the ones with the best job perspective. They have proven they can do the work.

I can understand if you were interviewing for the core google search team. Their optimization's make the company money.

Remember what Knuth said about optimization.

[bryanlarsen]

You probably get a few false negatives out this, depending on how good you are at drawing people out. Some people would be thinking "this question seems easy enough that I should be able to solve it without asking dumb questions, but I'm so nervous I'm not thinking straight" and then just freeze up. You should be able to draw them out, though, as long as you're aware that the reason they're not answering is mostly because they're nervous. It sounds like you've done a lot more interviews than I have, so I'm sure you could handle it. It is harder when their facility with English is poor.

[jtchang]

My first intuition was that you could somehow write a binary search with two pointers throwing about half of the array away each time. I ran into issues with this train of thought because there might be duplicates in the array or the array might be all the same number.

My second thought was just do a linear search and if you happen to find the pivot, store it, and make the array sorted. Subsequent calls therefore would result in a binary search.