4 ms·

'select the second highest number in this list' is actually O(n) and does not require sorting.

by bearmf 14y ago

grey-area 14y ago
Does that mean I fail the test :) A sort then select for the second highest seemed the simplest solution off the cuff (perhaps not the quickest), and if the code is fast enough, there's no point in optimising. Of course you could write a loop and check each value against a stored memo - your O(n) right?, but why bother when the library sort is fast enough for the purpose? If you're dealing with genuinely huge data sets obviously this becomes important, but then often the data will be in a db anyway.
- bearmf 14y ago
  It depends entirely on the person asking the question. Some people probably don't care, but there are some fans of the most efficient possible solution.
- danielweber 14y ago
  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?

'select the second highest number in this list' is actually O(n) and does not require sorting.

by bearmf 14y ago

'select the second highest number in this list' is actually O(n) and does not require sorting.

Does that mean I fail the test :) A sort then select for the second highest seemed the simplest solution off the cuff (perhaps not the quickest), and if the code is fast enough, there's no point in optimising. Of course you could write a loop and check each value against a stored memo - your O(n) right?, but why bother when the library sort is fast enough for the purpose? If you're dealing with genuinely huge data sets obviously this becomes important, but then often the data will be in a db anyway.

bearmf 14y ago
It depends entirely on the person asking the question. Some people probably don't care, but there are some fans of the most efficient possible solution.
danielweber 14y ago
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?