5 ms·

Life, the Universe and Technical Interviews

14 points by sahlhoff 12y ago

deleted 12y ago
[deleted]
tempestn 12y ago
I tend to ask what I think is a rather simpler question in most interviews: find the sum of the two largest (most positive) numbers in an array of arbitrary integers. Consider the efficiency of your solution for very large arrays. It is amazing how many seemingly knowledgeable, intelligent people cannot do this. And the vast majority of those who do, do it by sorting the array, efficiency be damned. Actually, I'd like a bit of feedback here. Is this something any decent developer should be able to do with ease? Should it be obvious that it can be done much more efficiently without running a sort on the array? Admittedly there are minor gotchas with things like the initial conditions, but still, I've been flabbergasted by how few people can even get close to a solution, let alone a bug-free and efficient one.
- Blackthorn 12y ago
  I'd expect anyone I interview to be able to do that, kind of like fizzbuzz. It's okay if they pull out the sort-the-array solution first, but I'd definitely try to get them to improve it.
  - tempestn 12y ago
    Yes, I agree with this too. And in some ways sorting is a better solution. The code is certainly simpler. That said, once you point out that you need an efficient solution for large data sets, a competent developer should be able to recognize how to do that. Heck, even if they just said, "ok, so you need to loop through it and keep track of the two largest numbers", then messed up the details, that would be better than most of the answers I've seen. (Again, from people with reasonable-looking applications and resumes.)
- angersock 12y ago
  Solution is just to have two indices into it leapfrogging as they find the next biggest one, right, and sum at the end if they've moved? Why would you sort?
  - tempestn 12y ago
    My thoughts exactly. O(n) vs O(nlog(n)). Or even if you don't have formal comp sci experience, it seems intuitive that sorting the entire array (which I specify could be large) just to get the two highest values is overkill. Want to apply to our full stack developer position? Edit: Out of curiosity, what would you initialize the two tracking variables to?
    - Blackthorn 12y ago
      Initialization is language dependent, of course :-)
    - angersock 12y ago
      So, both variables are just indices, so we'll just start them at the first and second elements in the array. The smaller of the two we'll start marching forward, comparing against the value at the larger. Once the value is larger, we'll start marching the other one forward until we hit the end of the array. At this point, I realize that if we just reuse the indices, life becomes difficult if we don't encounter a larger value later in the array and hence we lose the smaller of the two largest values. So, instead, let's start with three indices (Biggest,Biggerest,Curr), set at the first, second, and third positions. So, now, we'll just move the Curr index forward, and if it encounters a value larger than the the current largest value, we'll set the index of the Biggerest into the Biggest and the index of the Curr into the Biggerest. We can then continue until we hit the end of the array, and add the values under the Biggest and Biggerest indices. I think that'll work. EDIT: For cleanliness' sake, we could init the Curr and Biggerest to both point at the second element of the array, but there may be a little special-case code there to worry about and I'm not awake enough yet for that. :)
      - tempestn 12y ago
- Retric 12y ago
  I have seen plenty of useful code far worse than sorting such an array. IMO, someone missing the 'obvious' choice in an interview question is completly reasonable. Thinking back how many people verified that the array was non empty and it had more than one element? I call it the toy problem mindset, when coding you consider things deeply but in meetings your looking for roadblocks not optimal solutions. PS: From a preformace standpoint sorting your array is relativly better than ant of the posted solutions. Even though the article links to a much faster method. Aka there x log x solutions when a log x solution exists.
  - tempestn 12y ago
    Most people didn't think to check that the array had at least two elements, but more did that than managed to correctly loop through it. I'm not sure what your PS is referring to. Which posted solutions, and what article?
    - Retric 12y ago
      link at the top... "life the universe and technical interviews" http://diegobasch.com/life-the-universe-and-technical-interviews http://diegobasch.com/life-the-universe-and-technical-interv.... Every solution has a loop 1 to 1000000 which is N but then they check every digit which is a log N making them N log N solutions. But there are Log N solutions that avoid checking every possibility. Ex: s dup if 10 /mod recurse + then ; : f 0 1000000 0 do i s 42 = if 1 + then loop ;
autarch 12y ago
FizzBuzz is a reasonable way to find people who can't code. I've been surprised to find people with resumes that appeared decent who couldn't complete FizzBuzz even given 20 minutes of time to do it in.
deleted 12y ago
[deleted]

14 points by sahlhoff 12y ago

deleted 12y ago

[deleted]

I tend to ask what I think is a rather simpler question in most interviews: find the sum of the two largest (most positive) numbers in an array of arbitrary integers. Consider the efficiency of your solution for very large arrays. It is amazing how many seemingly knowledgeable, intelligent people cannot do this. And the vast majority of those who do, do it by sorting the array, efficiency be damned. Actually, I'd like a bit of feedback here. Is this something any decent developer should be able to do with ease? Should it be obvious that it can be done much more efficiently without running a sort on the array? Admittedly there are minor gotchas with things like the initial conditions, but still, I've been flabbergasted by how few people can even get close to a solution, let alone a bug-free and efficient one.

Blackthorn 12y ago
I'd expect anyone I interview to be able to do that, kind of like fizzbuzz. It's okay if they pull out the sort-the-array solution first, but I'd definitely try to get them to improve it.
- tempestn 12y ago
  Yes, I agree with this too. And in some ways sorting is a better solution. The code is certainly simpler. That said, once you point out that you need an efficient solution for large data sets, a competent developer should be able to recognize how to do that. Heck, even if they just said, "ok, so you need to loop through it and keep track of the two largest numbers", then messed up the details, that would be better than most of the answers I've seen. (Again, from people with reasonable-looking applications and resumes.)
angersock 12y ago
Solution is just to have two indices into it leapfrogging as they find the next biggest one, right, and sum at the end if they've moved? Why would you sort?
- tempestn 12y ago
  My thoughts exactly. O(n) vs O(nlog(n)). Or even if you don't have formal comp sci experience, it seems intuitive that sorting the entire array (which I specify could be large) just to get the two highest values is overkill. Want to apply to our full stack developer position? Edit: Out of curiosity, what would you initialize the two tracking variables to?
  - Blackthorn 12y ago
    Initialization is language dependent, of course :-)
  - angersock 12y ago
    So, both variables are just indices, so we'll just start them at the first and second elements in the array. The smaller of the two we'll start marching forward, comparing against the value at the larger. Once the value is larger, we'll start marching the other one forward until we hit the end of the array. At this point, I realize that if we just reuse the indices, life becomes difficult if we don't encounter a larger value later in the array and hence we lose the smaller of the two largest values. So, instead, let's start with three indices (Biggest,Biggerest,Curr), set at the first, second, and third positions. So, now, we'll just move the Curr index forward, and if it encounters a value larger than the the current largest value, we'll set the index of the Biggerest into the Biggest and the index of the Curr into the Biggerest. We can then continue until we hit the end of the array, and add the values under the Biggest and Biggerest indices. I think that'll work. EDIT: For cleanliness' sake, we could init the Curr and Biggerest to both point at the second element of the array, but there may be a little special-case code there to worry about and I'm not awake enough yet for that. :)
    - tempestn 12y ago
Retric 12y ago
I have seen plenty of useful code far worse than sorting such an array. IMO, someone missing the 'obvious' choice in an interview question is completly reasonable. Thinking back how many people verified that the array was non empty and it had more than one element? I call it the toy problem mindset, when coding you consider things deeply but in meetings your looking for roadblocks not optimal solutions. PS: From a preformace standpoint sorting your array is relativly better than ant of the posted solutions. Even though the article links to a much faster method. Aka there x log x solutions when a log x solution exists.
- tempestn 12y ago
  Most people didn't think to check that the array had at least two elements, but more did that than managed to correctly loop through it. I'm not sure what your PS is referring to. Which posted solutions, and what article?
  - Retric 12y ago
    link at the top... "life the universe and technical interviews" http://diegobasch.com/life-the-universe-and-technical-interviews http://diegobasch.com/life-the-universe-and-technical-interv.... Every solution has a loop 1 to 1000000 which is N but then they check every digit which is a log N making them N log N solutions. But there are Log N solutions that avoid checking every possibility. Ex: s dup if 10 /mod recurse + then ; : f 0 1000000 0 do i s 42 = if 1 + then loop ;

autarch 12y ago

FizzBuzz is a reasonable way to find people who can't code. I've been surprised to find people with resumes that appeared decent who couldn't complete FizzBuzz even given 20 minutes of time to do it in.

deleted 12y ago

[deleted]