You had to solve it on a blackboard, with chalk, and the intent (I later learned) was not necessarily that you got the right answer, but how you worked through it. Did you just lock up? Did you get frustrated? Did you ask the interviewer to clarify with more data? They wanted to see your thought process.

I was able to answer it (not everyone that got hired did), and when I was done, I looked at the interviewer and asked "Do you write code this way, here?". He laughed and said 'no, no no no'. I told him, I wasn't sure I would want to work there if they did. We both laughed. He ended up being my first supervisor at that company.

Hello Dan! (If you happen to read this...)

Out of curiosity, why?

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?

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.

[0] https://news.ycombinator.com/item?id=31265554#31266239

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.

These "new ideas" are things you should be paying them for.

Any code problems we present to the interview candidate are _clearly_ made-up examples. Though one of them was simplified from a real-world project we had years and years ago.