3 ms·

As the person who posted that question, if you gave me that answer right away, I'd say "good, but can you do better?" "Sort and take the second highest" is a f

As the person who posted that question, if you gave me that answer right away, I'd say "good, but can you do better?" "Sort and take the second highest" is a fine first answer. I'd expect most good candidates to start with that. I'd also expect them to say "but I think I can do better" on their own.

grey-area 14y ago
This is where I find questions like this a little confusing. To define better (at least in real world situations) the question requires more context. How many records? How are they stored? What are the characteristics of the storage? Which libraries are we using to store it and how do they behave (and in the real world there might be a few)? What are the other constraints? If we request a sort (say in a remote db) will that be quicker than the latency of requesting data in batches and iterating? Presumably you mean better given infinite memory to store all the records and a very large number of records? Because for most small collections of say a few thousand, a sort then select would be better than an iteration IMHO as it is simpler and the intent is clear if performance is acceptable. Perhaps I have misunderstood the intent of the question though, I'd be interested to hear what you feel is the ideal answer.
- danielweber 14y ago
  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.
  - grey-area 14y ago
    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.
    - klibertp 14y ago
      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?
- pseut 14y ago
  As a rule of thumb, if you feel that the correct answer depends on these details, ask questions to pin it down. Or, even better, just pick what you think is the most relevant for the company that you're interviewing at and (briefly) say what you're using as working assumptions.

grey-area 14y ago

This is where I find questions like this a little confusing. To define better (at least in real world situations) the question requires more context. How many records? How are they stored? What are the characteristics of the storage? Which libraries are we using to store it and how do they behave (and in the real world there might be a few)? What are the other constraints? If we request a sort (say in a remote db) will that be quicker than the latency of requesting data in batches and iterating? Presumably you mean better given infinite memory to store all the records and a very large number of records? Because for most small collections of say a few thousand, a sort then select would be better than an iteration IMHO as it is simpler and the intent is clear if performance is acceptable. Perhaps I have misunderstood the intent of the question though, I'd be interested to hear what you feel is the ideal answer.

danielweber 14y ago
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.
- grey-area 14y ago
  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.
  - klibertp 14y ago
    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?
pseut 14y ago
As a rule of thumb, if you feel that the correct answer depends on these details, ask questions to pin it down. Or, even better, just pick what you think is the most relevant for the company that you're interviewing at and (briefly) say what you're using as working assumptions.