Questions / Quant development, Algorithms & structures
Use the right queue
A Python list of 1,000 items is drained with pop(0) until empty. Each pop(0) on a list of length m shifts the m − 1 items behind it. How many element shifts happen in total?
Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 499500 shifts
- The pops see lengths 1,000, 999, …, 1 and shift 999, 998, …, 0 items.
- The total is 0 + 1 + … + 999 = 999 × 1,000/2.
- That is 499,500 shifts; a deque’s popleft would shift none.
Interview shortcut. Σ(m − 1) = n(n − 1)/2 = 999 × 500.
Takeaway. Front pops on a list cost O(n) each, O(n²) to drain.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.