3 ms·

Leetcode is fine. Once a dude asked me to write out merge sort. Like, I’m not from a CS bg (I suppose that wouldn’t matter). And I literally did look at merge a

Leetcode is fine. Once a dude asked me to write out merge sort. Like, I’m not from a CS bg (I suppose that wouldn’t matter). And I literally did look at merge and other sorts two days back. But that didn’t matter, the only way you can write merge sort is if you memorize it (or spend an inordinate amount of time writing sorting algos). I didn’t get that job, but I’ve been monitoring that company and they’re not doing that well anyway. Perhaps a coincidence?

a1369209993 5y ago
> the only way you can write merge sort is if you memorize it (or spend an inordinate amount of time writing sorting algos) Umm, what? void merge(int* d,int const* a,size_t za,int const* b,size_t zb) { size_t zd = za+zb,ia=0,ib=0; for(size_t i=0; i<zd ;i++) { if(ia < za && ib < zb) { if(a[ia] < b[ib]) d[i] = a[ia++]; else d[i] = b[ib++]; } else if(ia < za) d[i] = a[ia++]; else if(ib < zb) d[i] = b[ib++]; else abort(); // should have i==zd now } } void msort(int* d,size_t z,int const* s) { if(z==1) *d = *s; if(z<=1) return; size_t h = z - (z>>1); // round up int* x = malloc(h * sizeof *x); if(!x) abort(); // out of memory msort(x,h,s+(z-h)); msort(d+h,z-h,s); merge(d,d+h,z-h,x,h); } // not that this is any *good*, but it does *work* Are you using a absurdly broad definition of what counts as memorizing something or something?
dirkt 5y ago
> the only way you can write merge sort is if you memorize it Nah. You only have to remember the central idea (if you have two sorted "runs", you can merge them into a single sorted run). You draw a quick diagram to explain the idea, you go ahead and write code that does it. Then you apply recursion, and write down the overall algorithm (subdivide into runs until you can use some other method to sort it, then merge recursively). Bonus points if you can explain the circumstances when this is useful (when you want to sort data that is a lot larger than your main memory, but you can write it on disk or tape). Which is kind of obsolete today, unless you are again dealing with BIG data (everything old is new again...)
- ramraj07 5y ago
  That’s a great question. Thanks for continuing to ask these so I can avoid those orgs. When I do come to having to decide on a sorting algorithm, I can refer to the code and algos and then decide. All I need to be able to do is understand the algorithm when I see it not memorize the differences between quick and merge sort. I’m actively working with multiple Olap and regular db solutions and my teams responsible for keeping 100 billion row tables in the most queryable format and it’s never been possible for me to make such a choice, only on whether I use spark or redshift or snowflake. So what exactly would you achieve by asking this question? The irony is I was rejected by 5 companies for not being technical, accepted by 1 where I’ve been thriving for years now at one of the most technical roles in the org.

a1369209993 5y ago

> the only way you can write merge sort is if you memorize it (or spend an inordinate amount of time writing sorting algos) Umm, what? void merge(int* d,int const* a,size_t za,int const* b,size_t zb) { size_t zd = za+zb,ia=0,ib=0; for(size_t i=0; i<zd ;i++) { if(ia < za && ib < zb) { if(a[ia] < b[ib]) d[i] = a[ia++]; else d[i] = b[ib++]; } else if(ia < za) d[i] = a[ia++]; else if(ib < zb) d[i] = b[ib++]; else abort(); // should have i==zd now } } void msort(int* d,size_t z,int const* s) { if(z==1) *d = *s; if(z<=1) return; size_t h = z - (z>>1); // round up int* x = malloc(h * sizeof *x); if(!x) abort(); // out of memory msort(x,h,s+(z-h)); msort(d+h,z-h,s); merge(d,d+h,z-h,x,h); } // not that this is any *good*, but it does *work* Are you using a absurdly broad definition of what counts as memorizing something or something?

dirkt 5y ago

> the only way you can write merge sort is if you memorize it Nah. You only have to remember the central idea (if you have two sorted "runs", you can merge them into a single sorted run). You draw a quick diagram to explain the idea, you go ahead and write code that does it. Then you apply recursion, and write down the overall algorithm (subdivide into runs until you can use some other method to sort it, then merge recursively). Bonus points if you can explain the circumstances when this is useful (when you want to sort data that is a lot larger than your main memory, but you can write it on disk or tape). Which is kind of obsolete today, unless you are again dealing with BIG data (everything old is new again...)

ramraj07 5y ago
That’s a great question. Thanks for continuing to ask these so I can avoid those orgs. When I do come to having to decide on a sorting algorithm, I can refer to the code and algos and then decide. All I need to be able to do is understand the algorithm when I see it not memorize the differences between quick and merge sort. I’m actively working with multiple Olap and regular db solutions and my teams responsible for keeping 100 billion row tables in the most queryable format and it’s never been possible for me to make such a choice, only on whether I use spark or redshift or snowflake. So what exactly would you achieve by asking this question? The irony is I was rejected by 5 companies for not being technical, accepted by 1 where I’ve been thriving for years now at one of the most technical roles in the org.