Hi all,

When an interviewer ask me in an interview "given an array, write a sorting algorithm for sorting this array", what is he looking for to see ?
Is he looking for the most efficient algorithm ? Is he asking that to see if I'm familiar with some kind (doesn't matter what) of sorting algorithm ? Is he checking my programming write skills ?
I'm asking that cause I know how to implement and to write the in-place bubblesort algorigthm (it's not so difficult to write), but at the other hand it's not that efficient (O(n^2)). I also know how to implement the counting sort (sometimes it's also called 'bucket sort') but it's too also not that efficient (O(n)).
I am familiar with some other efficient algorithms like quicksort (most of the cases O(nlogn), depends on the pivot choosing) and merge sort (O(nlogn)) but it's not that easy to implement them and for the first one , in most cases you use the directory function for that.

I would be glad to hear your point of view if you are also interviewers and also if not....

thanks!

 

I also know how to implement the counting sort (sometimes it's also called 'bucket sort') but it's too also not that efficient (O(n)).

Well, after an interviewee claimed that an O(n) algorithm wasn't that efficient compared to O(nlogn) algorithms I would probably just chat with them about the weather until their time was up and wish them a good day before moving on to someone that might actually be worth hiring.

But to answer your question about what most technical interviewers are looking for, they generally want to see a combination of things, but high on that list is whether you have sound problem solving skills. They want to see not just what you know, but how you go about using it. Often times, they don't really care about the knowledge base you have (particularly for entry level positions) because they can teach you that. But if you can't take what you do know and apply it, then that is something that is much harder to teach (if you've already managed to get all the way through school without learning it). Many employers will ask at least some questions that are specifically intended to be something that you haven't seen before precisely so that they can get a look at how you go about applying what you know to something new to you. They probably don't care if you come up with a good solution, they want to see how you go about finding a solution at all. Is it coherent? Is it random guesses? Do you make an effort to understand the problem? Do you blindly regurgitate formulas? Do you make an attempt to ask if your solution makes sense? Along the way they will also get a feel for how good your fundamental understanding of the field is.

 

As an interviewer I would not be looking for a correct answer or even if you know what is a sort algorithm or how to code it.
I would be looking for your problem solving skills, how you would tackle a problem, any problem. The sort algorithm is just an example of context. The context will change in the next question. I would also be examining your ability to communicate.

 

I could care less if you know how to write a sort algorithm. What I care about is that you basically know what one is and where to find the details on how to use one. In fact I likely would not want you writing sort algorithms. I would rather you spend your time on the application and make use of well established libraries that have sttod the test of time.

 

Sorting algorithms are a common question not because the interviewer cares whether you can write a sorting algorithm or expects you to be doing that if you are hired. They are simply a reasonable example of a problem whose scope and complexity fits within the timeframe of an interview that that has a very well-defined goal in which most people with any programming experience have had some exposure to and which few people are going to be walking around with memorized solutions. So most people are going to need to think about how to sort something at a conceptual level and then figure out how to turn that understanding into an algorithm that is sufficiently detailed to then be implemented in code.

 

My 2¢ philosophy: Interviews are first of all a big time waster. People believe they are far better at judging people in a brief encounter – an interview – that they actually are. A person's technical chops are far better determined by their transcripts and/or resumé than by some random trick question in an interview. This is not just my opinion. Studies have repeatedly shown a very poor predictive value for interviews, compared to a person's established paper trail, for predicting career progress within the company. Of course, interviews still exist because everyone believes they're better than average.

So if your technical ability is established by your history, why would you be challenged with a technical question in an interview? An interview is primarily a social interaction requiring a set of interpersonal skills above and beyond technical expertise. It's also a chance for a higher level conversation about the goals of the company, the interviewee, and whether there is some overlap in those goals. Suddenly shifting gears to a random bit of technical trivia is a bit rude, frankly. The only value of that I can think of is to see how you react to rudeness, which you will inevitably encounter on the job, and to gauge your confidence under pressure.

Another more sinister reason is to assess your intelligence. It's against the law (in the U.S., at least) to administer intelligence tests, even though later success on the job is highly correlated to your tested IQ. There are many surrogate measures of IQ that companies have come up with to get around this testing law. You're allowed to ask questions that are loosely related to the job, and I suppose a sorting algorithm might be arguably relevant.

The last thing the interviewer should have been interested in was whatever algorithm you came up with. Some unscrupulous employers have been known to mine for ideas from interviewees they have no intention to hire. So it can happen, but hopefully that's rare.

 

You should have a good idea about big O complexity in general. Even in embedded programming there are concerns about 'Space complexity'. Sometimes we want to optimize for using less memory instead of (or in addition to) using less time by designing sort algorithms with things like dense instead of sparse data structures.

 

If a potential employer asks you to write some code then you damn well better write some correct code!

You any algorithm that works but is simple and foolproof to be done correctly on paper first time.

I would discuss other methods for other cases but stick to the simplest foolproof way. 99% of the time that is what your job will require anyway.

 

Sitting in the interviewer seat on occasion myself; they're probably just trying to figure out if you know how to problem solve and write code, in general. Think about it; if you ask the secretary to write an array sorting routine, their reaction will tell you instantly that they're clueless. The interviewer is just trying to figure out if you're clueless, student level or very experienced, in general. They don't want to know how much theory you know about sorting, they want to know if they can give you a problem and expect a solution.

Academics like to sit around theorizing about the best possible solution. Developers find a solution that works, implement it and move on. Businesses want to hire developers, not academics.

 

A nice blend of theory and practice is usually looked upon favorably.

When I had a phone interview with Amazon they asked me to write (and e-mail them) a function to implement Quicksort. I asked them if they preferred the sort to occur in-place or not. While I was at the on-site interview one of the guys mentioned that the fact that I asked that question demonstrated two things to them that all but guaranteed me a trip to Seattle on their dime: (1) I new enough about the theory to be able to even think to ask that question, and (2) I new enough about the practice to know that there wasn't a one-size-fits-all solution and that finding out what the customer actually wants instead of forcing my notion of the best solution down their throats has value. Normally I would have been somewhat taken aback by that, but having given quite a few technical interviews (mostly in EE) I was well aware that simple stuff like this really does tell you a lot -- and that a big part of it is the vast numbers of applicants that are so far below even a bar like this that you look seriously at anyone that does reach it.