Sliding window interview questions

Quick facts

Recall the answer first, then tap Show to check.

• collections.dequeShowHide

  A deque gives O(1) append and pop at both ends; list.pop(0) is O(n) because it shifts every item.

• deque(maxlen=k)ShowHide

  A deque with maxlen drops the oldest item automatically when a new one is appended at the full size.

• itertools.accumulateShowHide

  accumulate(xs) yields running totals; [0, *accumulate(xs)] gives prefix sums for O(1) range totals.

• Kotlin windowedShowHide

  list.windowed(k) returns every window as a new list: readable, but O(n·k) work and memory.

• Kotlin ArrayDequeShowHide

  kotlin.collections.ArrayDeque supports addFirst, addLast, removeFirst and removeLast in amortised O(1).