> As for the original interview question, there are systems where an occasional longer pause is not OK.
As you say, it's a tradeoff between worst-case operation cost and average operation cost: If you allow any worst-case operation cost, you can get really efficient on average. If you want really efficient worst-case operation cost, you can't get it down to exactly the average operation cost you could've otherwise gotten.
I wouldn't be surprised if this tradeoff is inherent to many de-amortization problems. But since the difference between the amortized and de-amortized solution is usually only a constant factor (as it is in this case), you have to be very specific about the model of computation if you want to prove anything mathematically.
You do lose the ability to do a no-copy realloc() though, and increase the average memory use (not peak).
This is the exact same average cost per element, just spread out evenly. Consider that each element still gets copied to the array of twice the size once whether you use this technique or the classic amortized version. Same average performance without the hitches (although copying a larger block of memory at once would likely be a bit faster).
I agree in principle. I think even something like std::unique_ptr could work; the concern would be self-referential types. Notably Rust doesn't allow those anyway, so I think any Rust type would be fine, not just Copy types.
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.
Still might be a lot better than a linked list for small types (due to less RAM spent on pointers and better cache locality because it's contiguous). With the exception of intrusive linked lists of stuff that is separately allocated anyway, I really hate linked lists.
Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.
As for the original interview question, there are systems where an occasional longer pause is not OK. Personally, I think that sticking to your gun must have come across as being stubborn and unyielding and maybe not ready to admit errors. As an interviewer, and for having worked with people who always think they're right and inflexible, it would have been a red flag.