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.
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.
Read the full Bloomberg Software Engineer interview experience this question came from
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.
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.
Community answers
Answer by kavob60880
public class Solution {
public int solution(int n) {
Map> valToIndex = new HashMap<>();
valToIndex.computeIfAbsent(0, k -> new ArrayList<>()).add(0);
int lastValue = 0;
for(int i = 1; i < n; i++) {
if( valToIndex.containsKey(lastValue) ) {
List indexes = valToIndex.get(lastValue);
int lastIndex = indexes.get(indexes.size() - 1);
if( lastIndex != (i - 1) ) {
lastValue = i - 1 - lastIndex;
} else if( indexes.size() > 1 ) {
lastValue = i - 1 - indexes.get(indexes.size() - 2);
} else {
lastValue = 0;
}
} else {
lastValue = 0;
}
valToIndex.computeIfAbsent(lastValue, k -> new ArrayList<>()).add(i);
}
return lastValue;
}
}