How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bloomberg.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bloomberg during technical interviews.

Compute the Nth Recency Value | Bloomberg Coding Question

Quick Overview

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.

Compute the Nth Recency Value

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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.

Quick Answer: 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, look at a[i - 1]. If that value has appeared earlier in the sequence at some index from 0 to i - 2, let last_index be the most recent such index and set a[i] = (i - 1) - last_index. Otherwise, set a[i] = 0. Return the value a[n - 1]. For example, when n = 4, the sequence begins [0, 0, 1, 0], so the answer is 0.

Constraints

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

Examples

Input: 1

Expected Output: 0

Explanation: The sequence starts with a[0] = 0, so the first value is 0.

Input: 2

Expected Output: 0

Explanation: a[1] = 0 because the previous value 0 had not appeared before index 0.

Input: 4

Expected Output: 0

Explanation: The sequence is [0, 0, 1, 0], so a[3] = 0.

Input: 7

Expected Output: 2

Explanation: The sequence through index 6 is [0, 0, 1, 0, 2, 0, 2], so a[6] = 2.

Input: 10

Expected Output: 6

Explanation: The sequence through index 9 is [0, 0, 1, 0, 2, 0, 2, 2, 1, 6], so a[9] = 6.

Input: 20

Expected Output: 3

Explanation: Continuing the sequence efficiently gives a[19] = 3.

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.

Quick Overview