Amortized Array Doubling - Quant Trader Interview Question
Difficulty: Medium
Category: Algorithms & Data Structures
Practice quant interview questions from top firms including Jane Street, Citadel, Two Sigma, DE Shaw, and other leading quantitative finance companies.
Topics: dynamic-array, amortized-analysis, algorithms, data-structures
Problem Description
A dynamic array starts with a size of 1. When the array is full, it doubles in size. Appending an element takes $O(1)$ time, except when the array is full, in which case doubling the array takes $O(n)$ time, where $n$ is the current size of the array. What is the amortized time complexity of $n$ append operations?
Practice this medium trader interview question on MyntBit - the all-in-one quant learning platform with 200+ quant interview questions for Jane Street, Citadel, Two Sigma, and other top quantitative finance firms.