Coding questions · Bloomberg

Compute the Nth Recency Value

This question evaluates understanding of recurrence-based sequence generation, index-based historical state tracking, and the design of time- and space-efficient algorithms. It is commonly asked in the Coding & Algorithms domain to assess algorithmic analysis and performance reasoning, emphasizing practical implementation-level competency rather than purely theoretical concepts.

Given an integer n >= 1, define a sequence a as follows:

a[0] = 0
For each i >= 1:
- If a[i - 1] has appeared earlier in the sequence, meaning there exists some index in [0, i - 2] with the same value, let last_index be the most recent such index.
  - Then a[i] = (i - 1) - last_index
- Otherwise:
  - a[i] = 0

Return the value a[n - 1].

Example:

a[0] = 0
a[1] = 0 because 0 had not appeared before index 0
a[2] = 1 because the previous 0 was at index 0, so 1 - 0 = 1
a[3] = 0 because 1 had not appeared before index 2

So for n = 4, the sequence begins as [0, 0, 1, 0], and the answer is 0.

Design an efficient algorithm to compute the answer.

Compute the Nth Recency Value

Constraints

1 <= n <= 1000000
An O(n^2) simulation that scans backward every step will be too slow for large n.

Hints

You only need to remember the most recent previous index of each value, not every occurrence.
While generating the sequence, update the last seen position of the previous value before moving to the next value.