3 ms·

> And some things (like binary search) should be easy to write anyway. It's a different story when a) your mind is set on statistics/linear algebra b) you've n

> And some things (like binary search) should be easy to write anyway. It's a different story when a) your mind is set on statistics/linear algebra b) you've never had to actually implement binary search by hand since college and c) even if you do implement the algorithm and demonstrate that you have a general understanding, it must work perfectly and pass test cases otherwise it doesn't count. FWIW I was rarely asked about algorithmic complexity which is more relevant in DS/ML, albeit it's usually in the context of whiteboarding another algorithm and the interviewer mocking me for doing it in O(n) instead of O(logn).

kragen 5y ago
Binary search in particular is surprisingly tricky, which is precisely what makes it useful for telling if someone knows how to program. To a significant extent, though, you can cheat by studying binary search itself, which is a surprisingly beautiful thing. I like this formulation for finding the first index in a half-open range where p is true, assuming p stays true thereafter: bsearch p i j := i if i == j else bsearch p i m if p m else bsearch p (m + 1) j where m := i + (j - i)//2 Or in Python: def bsearch(p, i, j): m = i + (j - i) // 2 return (i if i == j else bsearch(p, i, m) if p(m) else bsearch(p, m+1, j)) The only tricky thing about this formulation is that m < j if i < j, thus the asymmetric +1 in only one case to ensure progress. If invoked with a p such as a[m] >= k it gives the usual binary search on an array without early termination. The i + (j - i) // 2 formulation is not needed in modern Python, but historically an overflowing (i + j) // 2 was a bug in lots of binary search library functions, notably in Java and C. (Correction: I said a[m] <= k. This formulation is less tricky than the usual ones, but it's still tricky!)
- minimaxir 5y ago
  > Binary search in particular is surprisingly tricky, which is precisely what makes it useful for telling if someone knows how to program. That's the problem. There are many other ways to do that without risking false negatives and annoying potential candidates (e.g. I would not reapply to places that have rejected me due to skepticism about my programming abilities and using tests blatantly irrelevant to day-to-day work because it's a bad indication of the engineering culture). Even FizzBuzz is better at accomplishing that task.
  - nerdponx 5y ago
    FizzBuzz (or equivalent) is actually great IMO. It weeds out the people who lied on their resume, without punishing the people who never learned CS because they were too busy learning things that were actually useful to DS, like statistics or data visualization.
    - jstx1 5y ago
      I've actually been given fizzbuzz in a DS interview! Up to that point I thought that fizzbuzz was just a meme because it's obviously too easy.
      - rightbyte 5y ago
        I tried to make Fizzbuzz on a paper when I first heard of it, and it had a bug printing fizzbuzzfizzbuzz on 15. If you want a correct program without a compiler/computer I don't think anything is too easy. Maybe like, "make a function returning the sum of two float parameters".
        kragen 5y ago
        That would just test syntax, though. Fizzbuzz tests logic. Your bug was a logic bug. To a certain extent you can dispense with mental logic by using a compiler. But the feedback loop is much slower. Thinking your logic through before feeding it to a compiler is like looking at a map when you're driving a car; you can cut off whole branches of exploration. Binary search is a particularly tricky logic problem in part because it's so deceptively simple. In a continuous domain it's easy to get right, but the discrete domain introduces three or four boundary cases you can easily get wrong. But the great-great-grandparent is surely correct that many programming jobs don't require that level of thinking about program logic. Many that do, it's because the codebase is shitty, not because they're working in an inherently mentally challenging domain.
        rightbyte 5y ago
        Ye I meant running it and then correcting the error. Concerning binary search I acctually implemented that in an ECU for message sorting. It took like a whole day, including getting the outer boundries one off too big in the first test run. Funnely enough the vehicle ran fine anyway. I would never pull that algorithm off correctly in an interview without training to, I think.

kragen 5y ago

Binary search in particular is surprisingly tricky, which is precisely what makes it useful for telling if someone knows how to program. To a significant extent, though, you can cheat by studying binary search itself, which is a surprisingly beautiful thing. I like this formulation for finding the first index in a half-open range where p is true, assuming p stays true thereafter: bsearch p i j := i if i == j else bsearch p i m if p m else bsearch p (m + 1) j where m := i + (j - i)//2 Or in Python: def bsearch(p, i, j): m = i + (j - i) // 2 return (i if i == j else bsearch(p, i, m) if p(m) else bsearch(p, m+1, j)) The only tricky thing about this formulation is that m < j if i < j, thus the asymmetric +1 in only one case to ensure progress. If invoked with a p such as a[m] >= k it gives the usual binary search on an array without early termination. The i + (j - i) // 2 formulation is not needed in modern Python, but historically an overflowing (i + j) // 2 was a bug in lots of binary search library functions, notably in Java and C. (Correction: I said a[m] <= k. This formulation is less tricky than the usual ones, but it's still tricky!)

minimaxir 5y ago
> Binary search in particular is surprisingly tricky, which is precisely what makes it useful for telling if someone knows how to program. That's the problem. There are many other ways to do that without risking false negatives and annoying potential candidates (e.g. I would not reapply to places that have rejected me due to skepticism about my programming abilities and using tests blatantly irrelevant to day-to-day work because it's a bad indication of the engineering culture). Even FizzBuzz is better at accomplishing that task.
- nerdponx 5y ago
  FizzBuzz (or equivalent) is actually great IMO. It weeds out the people who lied on their resume, without punishing the people who never learned CS because they were too busy learning things that were actually useful to DS, like statistics or data visualization.
  - jstx1 5y ago
    I've actually been given fizzbuzz in a DS interview! Up to that point I thought that fizzbuzz was just a meme because it's obviously too easy.
    - rightbyte 5y ago
      I tried to make Fizzbuzz on a paper when I first heard of it, and it had a bug printing fizzbuzzfizzbuzz on 15. If you want a correct program without a compiler/computer I don't think anything is too easy. Maybe like, "make a function returning the sum of two float parameters".
      - kragen 5y ago
        That would just test syntax, though. Fizzbuzz tests logic. Your bug was a logic bug. To a certain extent you can dispense with mental logic by using a compiler. But the feedback loop is much slower. Thinking your logic through before feeding it to a compiler is like looking at a map when you're driving a car; you can cut off whole branches of exploration. Binary search is a particularly tricky logic problem in part because it's so deceptively simple. In a continuous domain it's easy to get right, but the discrete domain introduces three or four boundary cases you can easily get wrong. But the great-great-grandparent is surely correct that many programming jobs don't require that level of thinking about program logic. Many that do, it's because the codebase is shitty, not because they're working in an inherently mentally challenging domain.
        rightbyte 5y ago
        Ye I meant running it and then correcting the error. Concerning binary search I acctually implemented that in an ECU for message sorting. It took like a whole day, including getting the outer boundries one off too big in the first test run. Funnely enough the vehicle ran fine anyway. I would never pull that algorithm off correctly in an interview without training to, I think.