Get Maximum in Generated Array

Get Maximum in Generated Array

What is this problem about?

The Get Maximum in Generated Array interview question gives you an integer $n$. You need to generate an array nums of length $n + 1$ based on specific rules:

• nums[0] = 0
• nums[1] = 1
• nums[2 * i] = nums[i] (for $2 \le 2i \le n$)
• nums[2 * i + 1] = nums[i] + nums[i + 1] (for $2 \le 2i + 1 \le n$) After generating the array, you must return the maximum value it contains.

Why is this asked in interviews?

Companies like Meta and Amazon ask this Array simulation problem to test basic coding skills and attention to detail. It’s an "Easy" difficulty question that evaluates your ability to translate mathematical formulas into a loop. It also checks if you can handle edge cases like $n = 0$ or $n = 1$ correctly without causing an "Index Out of Bounds" error.

Algorithmic pattern used

This problem is a direct Simulation.

1. Handle base cases immediately: if $n == 0$, return 0. If $n == 1$, return 1.
2. Initialize an array of size $n + 1$ with zeros.
3. Set nums[0] = 0 and nums[1] = 1.
4. Loop from $i = 1$ up to $n/2$. Inside the loop, apply the two formulas to generate nums[2*i] and nums[2*i + 1]. Be careful not to write past index $n$.
5. Keep track of the maximum value seen so far or find the max after the array is fully generated.

Example explanation

Suppose $n = 7$. Array size is 8.

1. nums[0] = 0, nums[1] = 1.
2. $i = 1$: nums[2] = nums[1] = 1. nums[3] = nums[1] + nums[2] = 1 + 1 = 2.
3. $i = 2$: nums[4] = nums[2] = 1. nums[5] = nums[2] + nums[3] = 1 + 2 = 3.
4. $i = 3$: nums[6] = nums[3] = 2. nums[7] = nums[3] + nums[4] = 2 + 1 = 3. Array: [0, 1, 1, 2, 1, 3, 2, 3]. Maximum value is 3.

Common mistakes candidates make

• Index Out of Bounds: Forgetting that if $n$ is even, the formula 2*i + 1 might attempt to write to index $n + 1$, which doesn't exist.
• Base Case Failure: Not handling $n = 0$ properly, leading to errors when trying to set nums[1] = 1 on an array of size 1.
• Over-complicating: Trying to find a closed-form mathematical formula for the maximum when a simple $O(n)$ array generation is fast enough and explicitly requested.

Interview preparation tip

When implementing formulas that calculate multiple future indices (like 2*i and 2*i+1), always use if statements to ensure you don't exceed the target array size $n$.