I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand.
I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of appends.
I don't know if I remembered the term "amortized complexity" or not, but it was clear that they had never heard of doing amortized analysis across a series of operations and they absolutely did not get my answer. They got hung up on the idea that some appends force the array to grow and get copied. I tried to explain that that was only true for a predictable fraction of them, but they were stuck on the idea that this meant dynamic arrays had O(n) worst case performance. They clearly thought I didn't know what the hell I was talking about.
I'm pretty sure that was the point where they decided to pass on me.
But now I'm a senior software engineer at Google and I just finished writing a textbook that explains dynamic arrays including their amortized analysis, so joke's on them.
I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of appends.
I don't know if I remembered the term "amortized complexity" or not, but it was clear that they had never heard of doing amortized analysis across a series of operations and they absolutely did not get my answer. They got hung up on the idea that some appends force the array to grow and get copied. I tried to explain that that was only true for a predictable fraction of them, but they were stuck on the idea that this meant dynamic arrays had O(n) worst case performance. They clearly thought I didn't know what the hell I was talking about.
I'm pretty sure that was the point where they decided to pass on me.
But now I'm a senior software engineer at Google and I just finished writing a textbook that explains dynamic arrays including their amortized analysis, so joke's on them.