Sometimes I do give candidates examples of real challenges we're facing. The purpose is not to get anything for free, but rather to see if they're good at coming up with new ideas.
It also gets boring asking the same questions that may or may not have leaked to the Internet over and over.
AITA?
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*
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...)
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.
It's a real shame in tech with its (past and present) history of open source work and contributions that can be interpreted as such, especially with many projects nowadays being maintained by billion dollar coporations that can certainly pay a candidate for contributions. But that's a huge beast to tackle.
follow up note: I'm not sure if this[0] comment is parody or unironic, but situations like this are exactly what gives the idea such a bad reputation.
These "new ideas" are things you should be paying them for.