Skip to content
Get started

Writes in an in-place dedup

The standard in-place two-pointer dedup runs on the sorted array [2,2,3,5,5,5,7,8,8,8][2,2,3,5,5,5,7,8,8,8]: a write pointer ww starts on the first (kept) element, and for each later element the read pointer visits, the algorithm advances ww and executes arr[w] = arr[r] only when that element is a new value. Counting only those arr[w] = arr[r] write operations, how many writes occur?

Show hints (2)+
  1. A write fires only on a new value; runs of duplicates and the in-place first element write nothing.
  2. Writes == (distinct values) −1=5−1-1 = 5 - 1.

Answer

Reveal answer →

4

Create a free account to see the full worked solution and track your progress.

Interview format: Numerical Reasoning Tests, Trading Aptitude Tests

Related questions