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 Onsite rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

Maximize sum with no adjacent elements

Q: Maximize sum with no adjacent elements

This question evaluates understanding of dynamic programming and array-based optimization, assessing competency in designing algorithms that maximize a sum under adjacency constraints.

Company: TikTok

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an array of non-negative integers `nums`, choose a subset of elements such that **no two chosen elements are adjacent in the original array**. Return the **maximum possible sum** of the chosen elements. ### Input - `nums`: array of integers, `0 <= nums[i]` ### Output - An integer: the maximum sum achievable without choosing adjacent elements. ### Constraints (typical interview constraints) - `1 <= n <= 10^5` - `0 <= nums[i] <= 10^9` ### Examples - `nums = [1,2,3,1]` → `4` (choose `1` and `3`) - `nums = [2,7,9,3,1]` → `12` (choose `2, 9, 1`)

Quick Answer: This question evaluates understanding of dynamic programming and array-based optimization, assessing competency in designing algorithms that maximize a sum under adjacency constraints.

Given an array of non-negative integers `nums`, choose a subset of elements such that **no two chosen elements are adjacent in the original array**. Return the **maximum possible sum** of the chosen elements. ### Input - `nums`: array of integers, `0 <= nums[i]` ### Output - An integer: the maximum sum achievable without choosing adjacent elements. ### Constraints - `1 <= n <= 10^5` - `0 <= nums[i] <= 10^9` ### Examples - `nums = [1,2,3,1]` → `4` (choose `1` and `3`) - `nums = [2,7,9,3,1]` → `12` (choose `2, 9, 1`)

Constraints

1 <= n <= 10^5
0 <= nums[i] <= 10^9
Elements are non-negative
The empty array returns 0

Examples

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

Expected Output: 4

Explanation: Choose 1 (index 0) and 3 (index 2): 1 + 3 = 4. Choosing 2 and 1 only gives 3.

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

Expected Output: 12

Explanation: Choose 2 (i0), 9 (i2), 1 (i4): 2 + 9 + 1 = 12.

Input: ([5],)

Expected Output: 5

Explanation: Single element: take it.

Input: ([],)

Expected Output: 0

Explanation: Empty array: nothing to choose, sum is 0.

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

Expected Output: 0

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

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

Expected Output: 4

Explanation: Choose the two 2's at the ends (indices 0 and 3): 2 + 2 = 4.

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

Expected Output: 9

Explanation: Choose 4 (i0), 4 (i3), 1 (i5): 4 + 4 + 1 = 9.

Hints

This is the classic 'House Robber' problem. At each index, you either skip the current element or take it (which forbids taking the previous one).
Track two running values: the best sum that INCLUDES the current element and the best sum that EXCLUDES it. The included value can only build on the previous excluded value.
You only need the two values from the previous step, so O(1) extra space suffices. Final answer is max(include, exclude).

Quick Overview

This question evaluates understanding of dynamic programming and array-based optimization, assessing competency in designing algorithms that maximize a sum under adjacency constraints.