Data structures and algorithms
A hot-path buffer is a dynamic array with O(1) amortised push.
AppliedMultiple choice
A hot-path buffer is a dynamic array with amortised push. Why might that still be unacceptable?
- AThe amortised bound is wrong for arrays
- BThe occasional reallocation is a tail-latency spike
- CArrays have poor cache locality
- DAmortised analysis assumes random inputs
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
Report an issue with this question
Learn the method
Of the kind reported at
More data structures and algorithms questions
- You need the 100 largest values from a stream of 10⁹ numbers you cannot store.Foundation · Free solution
- What does the recurrence T(n) = 2T(n/2)+O(n) solve to?Applied · Free solution
- Strassen’s matrix multiplication satisfies T(n) = 7T(n/2)+O(n²).Advanced · Premium
- Climbing a staircase, part 3 of 3Advanced · Premium
- How many times does the inner body run in for i in range(1000): for j in range(i): body()?Foundation · Premium
- What does the recurrence T(n) = 4T(n/2)+Θ(n²) solve to?Applied · Premium