Re:A list of lists of interview questions
by cpppppp55 on Monday December 31, 2018 @08:37AM
(#18794417)
Sometimes 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.
* 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.