I think "do better" is a pretty obvious description, but if the candidate is having trouble with it, I'd say "you have a few million records, and your current mechanism is too slow."
I have patience for candidates, but not an infinite amount. If they keep on trying to come with reasons why they don't need to improve their answer, or try to drown me in a sea of bullshit, that's a no-hire. I'm screening out assholes and prima donnas as much as I'm screening out people who can't code.
Upon being told that "sort and take the second element" isn't good enough, I'd expect the candidate to come up with a linear walk through the code, keeping track of the two top elements.
I'd then ask the candidate to generalize it to "the #n element" instead of "the #2 element," which will probably require a new data element. Keeping those n elements in a sorted list is a fine way to start. A really great candidate would ask if they could re-order the elements as they find them (doing a partial version of a quick sort) or use some variation of a heap-sort with limited space.
Ok, I think that clarifies your intent, the question is purely hypothetical (many records, infinite resources) and designed to elicit the platonic algorithm given no constraints save time. You surely recognise though that 'improving' depends on the constraints which were not given? I find it curious that you characterise questions attempting to relate your problem to real world constraints as 'a sea of bullshit' :) Surely no one tries to avoid answering by asking for clarification of the constraints, wouldn't you normally face this problem with records in a db, not all in memory directly accessed? I'm not sure this interviewing game would suit me.
If sort first was too slow and it had to be done in memory, I would have iterated once and kept the results in an ordered list but not sorted the records during iteration as you have suggested, didn't think of that. Thanks for clarifying.
I think this - I mean the "meaning of better" being obvious or not - is a major difference between most of industry and academia. In academia code readability matters less, it's asymptotic performance matters more and constants can be safely ignored. Reimplementations of things tend to be rewarded, because it shows the student's understanding. It's completely different in the "real world".
And this is why looking at actual code someone wrote is a good idea - because there are things one cannot check during the interview, like how well the candidate structures the code, how well he writes comments, how does he manage the complexity of a growing codebase, how quickly he can learn a new library or tool and so on.
In this particular case I'd probably know that "doing better" means algorithmic complexity, but I would never come up with "but I can do better" remark myself. It's also possible that, when asked to "do better", the first thing I'd try to do would be to write unit tests and docstrings. Is this unacceptable? Would I be seen as an asshole or prima donna?
Also, there's an issue of me being able to come up with a "correct", "better", faster in terms of Big-Oh algorithm. I am not a genius, I know this. I am not and I can not hope to become Dijkstra. I'm also not a computer scientist. I worked hard to be able to read and understand and then code algorithms presented in papers, but I'm damn sure I couldn't come up with even the simplest of them. For example just last week I had to implement a scheduling algorithm called "highest response ratio next". I was able to look it up in the sources, understand it and implement it in a product, but I am sure as hell that I would not invent it during an interview. Does it mean that I'm not qualified for a job? Would I be seen as dumb?
Posts like danielweber wrote above make me nervous. It's probably not what he had in mind, but it seems to me like he would not hire me - and I work in "the industry" for almost ten years now and I have been programming for twenty. I can brush this off as irrelevant - I have a job that I'm proud of and happy with, but what a young, aspiring programmer has to feel when he gets told that he's no good, no hire, because he can't invent algorithms on the spot?
The algorithm design is all said out loud. If I printed up a page of code and handed it to the candidate and said "make it better" I might expect them to work on style.
So I don't mind answering questions during the interview process. The candidate might be nervous and I should be clear about my expectations. I don't like mind games like picking a fight and making sure the candidate responds the "right" way.[1] I would hold no points against them for asking on clarification for what "better" means, as long as I didn't they they were trying to be difficult and accepted that faster was better.
I'm sorry if you don't think I would hire you. Maybe I wouldn't, but that doesn't mean you aren't a good coder. But I also think you shouldn't be intimidated by "algorithm invention." You probably do this a bunch already. In the order you write your code you are probably already doing implicit algorithm invention. I think you can write the code to figure out the biggest number in a list if you sit down to do it, and once you do that finding the second biggest just involves keeping track of one more thing and doing one more test on each pass through.
Often the question is figuring out what data structure you should be using.
Oh, I don't actually expect anyone to give me the perfect answer of how to find the nth-biggest element in the list. In fact, if a candidate did give the perfect answer, I would say "this person is more qualified than me, please hire." I'm not capable myself of giving the perfect answer even though I've thought about it a few times and it's essentially a question I've practiced.
Ok, I thought it was being written as a code, even if just on paper or a board.
"accepted that faster was better"
The point we - grey-area and I - are trying to make is that it's not always the case, or rather that the "betterness" of faster implementation is, in practice, dependent in large parts on other characteristics of the code. If someone deleted slower implementation along with tests and docs and replaced it with faster, but undocumented, untested implementation I would not consider it a change for the better.
And I think you would agree with this in general (of course there are situations when a change like this is necessary!), and I think this is just a misunderstanding on my part - I was thinking about actual code, an implementation, all along while you were talking about description of the algorithm with words. In this case - with one additional assumption that memory complexity is irrelevant or not changed, but that's nitpicking - of course faster is better! :)
"I think you can write the code to figure out the biggest number in a list"
Yes, of course: (foldl max (first lst) (rest lst))
And I can even explain what foldl is and how it works.
"you shouldn't be intimidated by "algorithm invention.""
I am not "intimidated". I know my limits. I wouldn't be able to invent quicksort during the interview and I wouldn' be able to invent this: http://www.jstor.org/discover/10.2307/2346806 even if my life depended on this and I was given all the time of universe to do this (but I still coded it).
This also depends on what we mean by "inventing". Does using some previously learned technique or adjusting other already known algorithm count as an invention?
But from what you say I gather that you wouldn't want me to invent quicksort on the spot - and then it's ok, it seems like I still have a chance of getting a job! ;)
http://www.jstor.org/discover/10.2307/2346806 was not something someone came up with after a few days at it. They had deep understanding of the statistics behind the algorithm, and an almost unfathomable knowledge in the domain, not to mention a large network to help them. I'm sure that most intelligent people would be able come up with it if they had the same circumstances working in their favor.
I have patience for candidates, but not an infinite amount. If they keep on trying to come with reasons why they don't need to improve their answer, or try to drown me in a sea of bullshit, that's a no-hire. I'm screening out assholes and prima donnas as much as I'm screening out people who can't code.
Upon being told that "sort and take the second element" isn't good enough, I'd expect the candidate to come up with a linear walk through the code, keeping track of the two top elements.
I'd then ask the candidate to generalize it to "the #n element" instead of "the #2 element," which will probably require a new data element. Keeping those n elements in a sorted list is a fine way to start. A really great candidate would ask if they could re-order the elements as they find them (doing a partial version of a quick sort) or use some variation of a heap-sort with limited space.