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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

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

Maximize sum without choosing adjacent elements

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an integer array `nums` where `nums[i]` is the value in position `i`. Select a subset of indices such that **no two selected indices are adjacent** (i.e., you cannot select both `i` and `i+1`). Return the **maximum possible sum** of the selected values. ### Input - `nums`: array of integers (can include `0`) ### Output - An integer: the maximum achievable sum under the non-adjacent constraint. ### Constraints (reasonable interview assumptions) - `1 <= nums.length <= 2 * 10^5` - `0 <= nums[i] <= 10^9` - Time target: `O(n)` - Space target: `O(1)` or `O(n)` ### Examples - `nums = [2, 7, 9, 3, 1]` → `12` (pick `2 + 9 + 1`) - `nums = [1, 2, 3, 1]` → `4` (pick `1 + 3`)

Quick Answer: This question evaluates a candidate's understanding of array-based optimization and dynamic programming concepts for computing a maximum sum under non-adjacent selection constraints.

You are given an integer array `nums` where `nums[i]` is the value in position `i`. Select a subset of indices such that **no two selected indices are adjacent** (i.e., you cannot select both `i` and `i+1`). Return the **maximum possible sum** of the selected values. ### Input - `nums`: array of integers (can include `0`) ### Output - An integer: the maximum achievable sum under the non-adjacent constraint. ### Constraints - `1 <= nums.length <= 2 * 10^5` - `0 <= nums[i] <= 10^9` - Time target: `O(n)` - Space target: `O(1)` ### Examples - `nums = [2, 7, 9, 3, 1]` → `12` (pick `2 + 9 + 1`) - `nums = [1, 2, 3, 1]` → `4` (pick `1 + 3`) Note: For an empty array, return `0`.

Constraints

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 10^9
Return 0 for an empty array

Examples

Input: ([2, 7, 9, 3, 1],)

Expected Output: 12

Explanation: Pick indices 0, 2, 4 -> 2 + 9 + 1 = 12. No two are adjacent.

Input: ([1, 2, 3, 1],)

Expected Output: 4

Explanation: Pick indices 0 and 2 -> 1 + 3 = 4, which beats picking index 1 then 3 (2 + 1 = 3).

Input: ([5],)

Expected Output: 5

Explanation: Single element: take it.

Input: ([],)

Expected Output: 0

Explanation: Empty array: no elements to pick, sum is 0.

Input: ([0, 0, 0],)

Expected Output: 0

Explanation: All zeros: any valid selection sums to 0.

Input: ([2, 1, 1, 2],)

Expected Output: 4

Explanation: Pick indices 0 and 3 -> 2 + 2 = 4. They are not adjacent.

Input: ([1000000000, 1, 1000000000],)

Expected Output: 2000000000

Explanation: Pick the two endpoints (non-adjacent) -> 1e9 + 1e9 = 2e9, exercising large values.

Input: ([3, 2, 5, 10, 7],)

Expected Output: 15

Explanation: Pick indices 0, 2, 4 -> 3 + 5 + 7 = 15, beating other non-adjacent combinations.

Hints

This is the classic 'House Robber' DP. At each index you either take nums[i] (and must skip i-1) or skip it.
Track two running values: the best sum that INCLUDES the current element and the best sum that EXCLUDES it.
Transition: new_incl = excl + nums[i]; new_excl = max(excl, incl). The answer is max(incl, excl) after the last element.
Because all values are non-negative, skipping never hurts via negatives, but the same O(1) rolling DP still works for general (including zero) values.

Quick Overview

This question evaluates a candidate's understanding of array-based optimization and dynamic programming concepts for computing a maximum sum under non-adjacent selection constraints.