2 ms·
I had an interview where the interviewer didn't understand amortized complexity. * thought pushing n elements into an empty vector took O(n) amortized time (it
by im3w1l 8y ago
I had an interview where the interviewer didn't understand amortized complexity.
* thought pushing n elements into an empty vector took O(n) amortized time (it's just O(n) guaranteed)
* thought a hashmap lookup took O(1) amortized time (it's O(1) expected not O(1) amortized).
I tried to gently correct him but he insisted on his views and I felt like I had to drop it so we could discuss other things also felt like I was dinged for it.
On the other hand I've been on the other side of the table, and can appreciate that interviewing people is hard too.
- cpppppp55 8y agoSometimes pushing into a vector is O(n), but typically not. So it’s the penalty of allocating new data memory when the underlying array needs a resize that’s amortized for multiple push calls. Similarly with a typical hashmap, the keyspace should occasionally collide, meaning non-edgecases would amortize to O(1) for multiple inserts.