[pp13]

@aplusbi

Let's say I interviewed you. I had asked to implement the fastest algorithm to give back the largest palindrome of words in English dictionary and compare it the largest palindrome of the french language. What the best solution you can come up with in 45 minutes.

After, that I asked you, write a simple ftp server, in the language of your choice. With your first solution, I asked you implement a SSL library and add it to the ftp server to make it sftp.

Based on that I can judge how good of a programmer you really are.

Sorry for being sarcastic, but I think most interviewers are on a power trip. They ask questions that if they heard for the first time, they couldn't come up with answers either.

I think your better off really talking about and going in depth with the programmers experience. If your experienced yourself, you should have no problem.

[eropple]

His first question is very straightforward if you've ever encountered permutations in a math class (and you should have, if you're a programmer). Even if you haven't, it shouldn't be that difficult.

His second is trickier, but solvable. And, no, I've never seen that (particular) question before.

[pp13]

My point was, his questions, doesn't really indicate if the candidate is a good programmer or not.

It could be the person studied up on all sorts of puzzles and famous algorithms online but hasn't really written or programmed anything.

Not all jobs require that much expertise. You could be doing some really simple programming work.

I think most interviewers ask these type of questions 1.) make themselves feel smart 2.) they get a kick out it

[eropple]

That wasn't much of a point, on your part. The second question in particular requires some not-entirely-simple breaking down into subproblems. The first one can be handled in such a way if you're unfamiliar with the mathematics behind it; it's easier, as are many things, if you remember combinations and permutations from math class but not at all unsolvable if you don't. His questions aren't bad at demonstrating important aspects of a programmer's problem-solving approach.

And your complaining that "not all jobs require that much expertise" is unfounded. I consider those to be novice questions, personally--and even if they weren't, you don't know what he's hiring for.

He's not being unreasonable. You, on the other hand, seem to be, and seem to be doing so in a rather defensive manner.

[pp13]

@eropple

So do you have data to back up your claims that; answering those questions determine if your a good programmer.

Yes, there are tons of programming jobs out there, that don't require much of those skills. Not all jobs are that innovative.

Most of the development jobs I have seen require you to come up to speed with the code base fast. So it's that code reading comprehension that I think is most prevalent.

[eropple]

I did not in any way, shape, or form claim that such questions determine whether or not a candidate is a good programmer. If you are going to respond to my posts, please respond to my posts and not what you think or wish I said in those posts.

No interview or interview question can determine conclusively that you are a good programmer. But they reduce the likelihood that you're not, and comments like your strident and hysterical analogy drawn between these really very simple problems and "write a SSL library!" are doing little to change my mind.

[pp13]

Ok, I didn't mean to offend you, I am sorry if I have.

That being said these are my thoughts on the subject of interviewing programmers.

When I just graduated college, I was all about puzzles and programming puzzles. My thoughts were that only people who could do these puzzles deserved programming jobs.

I was so wrong. Puzzles are something that you get or don't get. If your in an interview, and you haven't faced those combinatorial problems for a while, you could bomb, if someone asked you those questions.

Understood "fizzbuzz" problems are suppose to be the the lowest level of programming problems that any competent programmer can solve. If you want to fast screen candidates, go ahead and ask them.

When you get into problems, that require "tricks", either you get it or don't. It could be easy for some people and hard for others. There is no correlation of them getting it, to being good on the job, unless the problems are such that, the programmer will face them every day on the job.

Another good permutation problem, is subset sum problem. Come up with a program that determines if a array or list, can be partitioned into 2 non overlapping subsets, such that the the sum of both subsets equals each other. Print out both subsets if they are equal or state that it cannot be done. Is it possible to get better than O(n^2) for the optimal solution. That is fun one, but I don't think asking that would give you much insight into determining whether the programmer is fit or not.

I think interviewing is a really important task. It a really hard job to get right. If your a bad interviewer, the company you work for will eventually get a bad reputation.

Many software companies do not train people how to interview. That in our industry, is a huge problem.

There are many other things besides raw technical skills that will determine, how well the candidate will do at their job and at at the company.

Going over the candidate's experience in detail. Getting a feel for what they really want and expect from the job. Do you like the candidate's personality? What does your gut instinct say. What technical things do you need to ask that are relevant for that job, that you couldn't determine from the their experience? How would you design questions, relevant to the job at hand.

Just my random thoughts.

[Someone]

"Another good permutation problem, is subset sum problem. [...] Is it possible to get better than O(n^2) for the optimal solution."

AFAIK subset sum is NP complete, so I guess you meant O(2^n). Even so, I would not expect a programmer to tell me much about it.

[aplusbi]

Part of our interview process is having the candidate code-review some really bad code. The only problem with it is that it is biased against students/recent graduates. I'd say close to 90% of student/recent grad candidates do pretty poorly on the code review question.

[pp13]

What type of candidate are you looking for? Obviously recent graduates will not have that much coding experience and reading comprehension.

Are you looking for someone to write new libraries from scratch? Who can implement new algorithms and data structures from nothing. Someone who can write new protocols and publish it to the team?

Are you looking for someone who can read your code base? Just fix bugs?

This one problem I keep seeing, many software companies don't know what to look for. Everyone wants that "smart and gets things done", but do you what things need to be done?

[aplusbi]

I work for a financial software company and we have a lot of projects so it depends, really. Recently we've been looking for some frontend Javascript developers the project I work on. The interviews we've been conducting have reflected that - mostly questions on things like JQuery/Moo Tools, having the candidate code stuff using AJAX, etc. "Real world" stuff in other words.

We often hire C++/C#/Python/Perl/Ruby/Objective-C/Java/etc (seriously, we use all those languages) to work on existing code bases. We work on Linux, VMS, Windows, iOS, and BlackBerry. We have plenty of "glue" code, frontend code and code that needs to deal with large amounts of data.

We don't expect recent graduates to have much coding experience. You seem to think that we have some strict checklist which is not the case at all. I really don't know where you got this idea. My initial comment was simply meant to answer the OPs question. I don't always ask those questions, I weight many things in my decision (including whether I think I conducted the interview well - sometimes it's clear that I've failed to properly describe the problem) and discuss the candidate with other people who have also interviewed them.

[tzs]

Interesting. I'd find the permutations one trickier, and yes I've encountered permutations in math and have been a programmer a long time). Here's why I'd find it tricky.

There is an obvious recursive algorithm, but I'd be worried that if I gave that the interviewer would quibble about stack usage (although it is going to be linear in the number of items being permuted which should be OK most of the time).

Thinking a bit more, I can see that it should be possible to do an iterative algorithm that needs little or no state other than the last permutation generated and that given a sorted input string would generate the permutations in lexicographic order. The basic idea is that if you partition the string into two parts, AB, such that no permutation of B exists that is lexicographically after B, then the next permutation of AB is formed by replacing B with the lexicographically first permutation of B, and then exchanging the last character of A with the first character of the new B. (I think that will generate them all, in order--but I've not seriously analyzed it--I'm just riffing off the top of my head as I type here, like I'd be doing in an interview).

OK, now I'd worry about that step of replacing B with the lexicographically first permutation of B. That can be done by sorting B, but then the interviewer might complain about all that sorting. Aha! The lexicographically last permutation of B and the first permutation or reverses of each other, and reversal can be done in O(n). (And maybe it can be done even faster with some kind of doubly linked list to store strings as list of elements, where a string is represented by a pointer into the list, a length, and a direction flag...something to think about).

Anyway, the permutation question is fraught with potential pitfalls. I'd be smart enough, I hope, to do all the above musings out loud to give the interview a chance to jump in and tell me "It's OK...I just want to see if you can write code, so go ahead with the recursive solution".

That second problem is straightforward. It's just binary search. The rotated array doesn't change anything fundamental about it--it just slightly complicates the check to see which half the target element must lie in. There will always be at least one "normal" half--that is, a half where all the elements are sorted. You can recognize a normal half be the left endpoint being less than the right endpoint. You check for the target in a normal half the usual way. If the target is not in the normal half you check, it must be in the other half (or not in the array at all).

[aplusbi]

Interestingly enough no one I've interviewed has every suggested lexicographical ordering although I have implemented it that way myself to see how hard it would be (answer: it's kind of hard).

That said, C++'s standard library has a next_permutation function that returns the lexicographical next permutation of a pair of iterators (actually it does it in-place and returns a bool). If a candidate used that I'd allow it (as long as there was some discussion as to how it worked).

I've since stopped asking that question and now stick primarily with the split array question as I think it's less tricky. There's more than one way to solve it and most of the solutions build up on simpler solutions which makes for good discussion. I also don't ask for actual code for that problem unless I get the feeling the candidate will understand the problem better by expressing it in code.

[eropple]

Given that I've been back in C++ mode for the last week, this is exactly what I was considering (using next_permutation). ;)

[aplusbi]

Like I said, 80-90% of candidates can answer my questions. I am also very generous with what I accept as an answer and how much help I give. My interview is as much a discussion about the question as it is the solution.

As for what I get out of the interview - you're right, it's not going to tell me how good of a programmer the candidate is. But it will tell if they can code, and will give me some idea of their problem solving abilities. (I've also personally solved both questions without help in under 15 minutes each, though not under stressful interview conditions).

[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.

[aplusbi]

I think the best programmers are ones who can utilize abstractions while at the same time understand what they are abstractions of. For example, someone who knows Django and SQL is probably a better programmer than someone who knows Django but doesn't understand what a relational database is.

While people might not need to write searching and sorting algorithms much any more, understanding the difference between an ordered map and a hash table can be crucial in many common "real world" scenarios.

I also have tried to stress that the answers to my algorithm questions are only part of the criteria in determining whether we hire someone or not. I brought them up because the OP asked specifically about coding questions, not hiring questions.

[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.

[ig1]

The problem with that is that there are plenty of programmers who can talk the talk without being good programmers.