4 ms·

> if I forgot how to write binary search The binary search algorithm isn't something you can "forget". For a literate programmer it's like forgetting how to w

> if I forgot how to write binary search The binary search algorithm isn't something you can "forget". For a literate programmer it's like forgetting how to write the letter 'A' or forgetting which pedal is the gas and which is the brakes.

sedeki 5y ago
I think the overall point is the risk of forgetting something judged as "fundamental."
- Vvector 5y ago
  Can you clarify what you mean here? I would argue that any decent programmer could hack out a sorting routine, without having the code memorized. If you cannot write a binary search routine from scratch, how can you be expected to solve much bigger problems?
  - kragen 5y ago
    Sure, but there are a lot of subtle issues in both sorting and binary search. The simplest sorting routine is probably dumbsort: void dumbsort(int *p, int n) { for (int tmp, i = 1; i < n; i++) { if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0; } } But it lives up to its name; I can't imagine any reason you should ever use this algorithm. It compiles to 16 instructions but it's O(N³). Insertion sort is more complicated—it compiles to 17 instructions—and is actually a reasonable thing to use in some circumstances: void isort(int *a, size_t n) { for (size_t i = 1; i < n; i++) { for (size_t j = i; j > 0; j--) { if (a[j-1] <= a[j]) break; int tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } That's because it has the lowest constant factor of all the O(N²) comparison sorts on common machines, so it's the absolute fastest way to sort small arrays. (On my laptop it sorts N items in 0.34 ns × N² ± 2%.) And it's also very fast for large arrays of nearly-sorted data, so it's a reasonable way to finish up after a rough quicksort. It took me about five minutes to write that, and it worked the first time I tested it. But that's in part because I find sort routines fascinating and I've been studying them, and programming in C, for almost 30 years. Even if it took you an hour or four hours and required a lot of debugging, you still might be a decent programmer. Especially for jobs where things are less well defined and you have to do a lot of debugging anyway! (By contrast, I've actually spent most of the last hour trying to write a properly working quicksort, the variant that finishes up with a single call to insertion sort, using both notes and a compiler. Of course it produces correct results because of the final insertion sort but it's not as efficient as it should be and I can't figure out why. Apparently I can't brain today... good thing I'm not in a job interview!)
cassonmars 5y ago
I think you’re overestimating most people’s ability to withstand the stress that quiz show style Leetcode interviews can put on people. I’ve literally blanked on an interview before when I was tasked with writing a simple parser and I’ve written entire compilers. The interview processes are broken in most companies. Pair programming sessions with debugging and incremental graduation of the problem scope are way better at assessing programming competency, because you also get a sense for how well the candidate can collaborate and communicate.
- eschneider 5y ago
  Yeah, folks can definitely freeze up and I'm pretty sympathetic to that in interviews. I'll often spot folks most or all of the algorithm if it looks like they locked up. "Hey, you could dry implementing it like this..." and see where they go from there. I mean, we really want to see people succeed with these things.
- colinmhayes 5y ago
  Stressful situations happen at work. If you're not able to handle it in the interview you might not be able to during crunch time.
jerrre 5y ago
Your analogies are things that you use a large % of the time, almost any second. Whereas I've been programming for years, and never wrote a binary search (I think?), but perhaps I don't qualify as literate? I think writing an if-statement would be closer to your analogies.
- Ueland 5y ago
  Yeah, the parent commment is what I consider a reason for why many fear the imposter syndrome. They read about other developers saying "If you dont know how to do X, you suck and cant get a job".
- otabdeveloper4 5y ago
  > ...but perhaps I don't qualify as literate? Probably. Point is, you don't really need to know how to program to ship software.
midasz 5y ago
How often are you writing binary search algorithms hahah, is it like your variant of a doodle?
- kragen 5y ago
  For me it is! It's one of my standard exercises when I'm sketching out a new programming language: what does binary search look like in this language? How general is it? http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_23 http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_23
kragen 5y ago
Well, but he said "forgot how to write binary search in 10 minutes". This came up here three months ago: "school was years ago...I've forgotten how to implement a hash table in C within 30 minutes. Is that really the gatekeeper we want?" Well, I thought, yes, I think it is, actually? So I tried implementing a hash table in C—without testing it, as if I were writing it in an interview without programming tools. It took me 15 minutes and had a significant bug: https://news.ycombinator.com/item?id=26593250 https://news.ycombinator.com/item?id=26593250 I concluded that implementing a hash table in C in 30 minutes is a reasonable thing to ask someone to try during an interview, and how people work on it will probably tell you a lot about their programming abilities. I wouldn't hire them for a C programming job if they said "school was years ago, I've forgotten", but you shouldn't necessarily expect them to succeed flawlessly. Binary search in particular is notoriously tricky. It's easy to explain the idea in a lot less than 10 minutes, and it's easy to write a version of the code that sometimes works in less than 10 minutes, something like bs(k, a, i, j) { int m = (i+j)/2; return a[m] == k ? m : a[m] < k ? bs(k, a, m, j) : bs(k, a, i, m); } But it's easy for the algorithm to hide subtle bugs. That version has at least one type error (in modern C, anyway), one obvious correctness bug, at least one obvious performance bug, and probably some subtle correctness bugs as well. Many years passed between the first publication of a binary search algorithm and the first publication of a correct one. Also, though, there are lots of kinds of programmers. You can spend a lot of time writing screen-scrapers or CRUD or machine learning models in Python without ever needing to implement binary search. In Python you should probably just use the bisect module in practice, most of the time, rather than reimplementing it.
- otabdeveloper4 5y ago
  > But it's easy for the algorithm to hide subtle bugs. For sure, but I guarantee you the interviewer from the grandparent comment wasn't looking for correctness and safety when they asked to implement a binary search. They ask the binary search question to check if the applicant knows what an algorithm is and if they ever had to implement one. (Any algorithm.) Sadly, 90% of programmers these days don't and haven't. > In Python you should probably just use the bisect module in practice, most of the time, rather than reimplementing it. Well, yes, most developers ship software without ever having to actually program.
adamors 5y ago
This comment is nonsense. Nobody is writing binary searches in their day-to-day jobs, and if they do it's once in a blue moon, not every day. You're using pedals every time you drive.
- sgtnoodle 5y ago
  Yeah, I need to implement a binary search maybe once a year. I had a legit use of a priority queue a couple years ago and I'm still excited about it! I've still never had a professional use for a Trei structure. I tried really hard to make a case for it on a project at Google, but it just didn't make sense vs. slapping down std::map and then drinking a beer.
  - mewpmewp2 5y ago
    In which case would you actually implement a binary search instead of using an existing library method for that?
    - sgtnoodle 5y ago
      Code running on a microcontroller with very limited RAM, operating on data structures that don't naturally plug into generic algorithm implementations. For example, finding the end of a several GB long append-only log file stored on the raw blocks of an SD card.
      - mewpmewp2 5y ago
        In these cases did you write it from scratch or were you able to copy paste a working solution? Because most pragmatic to me would be to google for a solution on Stack overflow, see what is upvoted and seems reasonably vetted, then potentially go over the code yourself to see if there's any issues and maybe write few tests to be extra sure. Maybe your use case is too niche though to be able to copy paste though, I'm not sure.
        sgtnoodle 5y ago

sedeki 5y ago

I think the overall point is the risk of forgetting something judged as "fundamental."

Vvector 5y ago
Can you clarify what you mean here? I would argue that any decent programmer could hack out a sorting routine, without having the code memorized. If you cannot write a binary search routine from scratch, how can you be expected to solve much bigger problems?
- kragen 5y ago
  Sure, but there are a lot of subtle issues in both sorting and binary search. The simplest sorting routine is probably dumbsort: void dumbsort(int *p, int n) { for (int tmp, i = 1; i < n; i++) { if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0; } } But it lives up to its name; I can't imagine any reason you should ever use this algorithm. It compiles to 16 instructions but it's O(N³). Insertion sort is more complicated—it compiles to 17 instructions—and is actually a reasonable thing to use in some circumstances: void isort(int *a, size_t n) { for (size_t i = 1; i < n; i++) { for (size_t j = i; j > 0; j--) { if (a[j-1] <= a[j]) break; int tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } That's because it has the lowest constant factor of all the O(N²) comparison sorts on common machines, so it's the absolute fastest way to sort small arrays. (On my laptop it sorts N items in 0.34 ns × N² ± 2%.) And it's also very fast for large arrays of nearly-sorted data, so it's a reasonable way to finish up after a rough quicksort. It took me about five minutes to write that, and it worked the first time I tested it. But that's in part because I find sort routines fascinating and I've been studying them, and programming in C, for almost 30 years. Even if it took you an hour or four hours and required a lot of debugging, you still might be a decent programmer. Especially for jobs where things are less well defined and you have to do a lot of debugging anyway! (By contrast, I've actually spent most of the last hour trying to write a properly working quicksort, the variant that finishes up with a single call to insertion sort, using both notes and a compiler. Of course it produces correct results because of the final insertion sort but it's not as efficient as it should be and I can't figure out why. Apparently I can't brain today... good thing I'm not in a job interview!)

cassonmars 5y ago

I think you’re overestimating most people’s ability to withstand the stress that quiz show style Leetcode interviews can put on people. I’ve literally blanked on an interview before when I was tasked with writing a simple parser and I’ve written entire compilers. The interview processes are broken in most companies. Pair programming sessions with debugging and incremental graduation of the problem scope are way better at assessing programming competency, because you also get a sense for how well the candidate can collaborate and communicate.

eschneider 5y ago
Yeah, folks can definitely freeze up and I'm pretty sympathetic to that in interviews. I'll often spot folks most or all of the algorithm if it looks like they locked up. "Hey, you could dry implementing it like this..." and see where they go from there. I mean, we really want to see people succeed with these things.
colinmhayes 5y ago
Stressful situations happen at work. If you're not able to handle it in the interview you might not be able to during crunch time.

jerrre 5y ago

Your analogies are things that you use a large % of the time, almost any second. Whereas I've been programming for years, and never wrote a binary search (I think?), but perhaps I don't qualify as literate? I think writing an if-statement would be closer to your analogies.

Ueland 5y ago
Yeah, the parent commment is what I consider a reason for why many fear the imposter syndrome. They read about other developers saying "If you dont know how to do X, you suck and cant get a job".
otabdeveloper4 5y ago
> ...but perhaps I don't qualify as literate? Probably. Point is, you don't really need to know how to program to ship software.

midasz 5y ago

How often are you writing binary search algorithms hahah, is it like your variant of a doodle?

kragen 5y ago
For me it is! It's one of my standard exercises when I'm sketching out a new programming language: what does binary search look like in this language? How general is it? http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_23 http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_23

kragen 5y ago

Well, but he said "forgot how to write binary search in 10 minutes". This came up here three months ago: "school was years ago...I've forgotten how to implement a hash table in C within 30 minutes. Is that really the gatekeeper we want?" Well, I thought, yes, I think it is, actually? So I tried implementing a hash table in C—without testing it, as if I were writing it in an interview without programming tools. It took me 15 minutes and had a significant bug: https://news.ycombinator.com/item?id=26593250 https://news.ycombinator.com/item?id=26593250 I concluded that implementing a hash table in C in 30 minutes is a reasonable thing to ask someone to try during an interview, and how people work on it will probably tell you a lot about their programming abilities. I wouldn't hire them for a C programming job if they said "school was years ago, I've forgotten", but you shouldn't necessarily expect them to succeed flawlessly. Binary search in particular is notoriously tricky. It's easy to explain the idea in a lot less than 10 minutes, and it's easy to write a version of the code that sometimes works in less than 10 minutes, something like bs(k, a, i, j) { int m = (i+j)/2; return a[m] == k ? m : a[m] < k ? bs(k, a, m, j) : bs(k, a, i, m); } But it's easy for the algorithm to hide subtle bugs. That version has at least one type error (in modern C, anyway), one obvious correctness bug, at least one obvious performance bug, and probably some subtle correctness bugs as well. Many years passed between the first publication of a binary search algorithm and the first publication of a correct one. Also, though, there are lots of kinds of programmers. You can spend a lot of time writing screen-scrapers or CRUD or machine learning models in Python without ever needing to implement binary search. In Python you should probably just use the bisect module in practice, most of the time, rather than reimplementing it.

otabdeveloper4 5y ago
> But it's easy for the algorithm to hide subtle bugs. For sure, but I guarantee you the interviewer from the grandparent comment wasn't looking for correctness and safety when they asked to implement a binary search. They ask the binary search question to check if the applicant knows what an algorithm is and if they ever had to implement one. (Any algorithm.) Sadly, 90% of programmers these days don't and haven't. > In Python you should probably just use the bisect module in practice, most of the time, rather than reimplementing it. Well, yes, most developers ship software without ever having to actually program.

adamors 5y ago

This comment is nonsense. Nobody is writing binary searches in their day-to-day jobs, and if they do it's once in a blue moon, not every day. You're using pedals every time you drive.

sgtnoodle 5y ago
Yeah, I need to implement a binary search maybe once a year. I had a legit use of a priority queue a couple years ago and I'm still excited about it! I've still never had a professional use for a Trei structure. I tried really hard to make a case for it on a project at Google, but it just didn't make sense vs. slapping down std::map and then drinking a beer.
- mewpmewp2 5y ago
  In which case would you actually implement a binary search instead of using an existing library method for that?
  - sgtnoodle 5y ago
    Code running on a microcontroller with very limited RAM, operating on data structures that don't naturally plug into generic algorithm implementations. For example, finding the end of a several GB long append-only log file stored on the raw blocks of an SD card.
    - mewpmewp2 5y ago
      In these cases did you write it from scratch or were you able to copy paste a working solution? Because most pragmatic to me would be to google for a solution on Stack overflow, see what is upvoted and seems reasonably vetted, then potentially go over the code yourself to see if there's any issues and maybe write few tests to be extra sure. Maybe your use case is too niche though to be able to copy paste though, I'm not sure.
      - sgtnoodle 5y ago