reevo·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

May 2026

Summary

Reevo OA for a Software Engineer role, one algorithmic problem that looks deceptively clean until you sit with it for a few minutes. Not a lot of context given about the process beyond this.

Questions Asked (1)

You have an integer array of length n. The weighted sum S is defined as the sum of arr[i] * (i+1) for all i. You can perform adjacent swaps, but each position can be involved in at most one swap (swaps must be non-overlapping). Return the maximum possible value of S.

Algorithms & Data Structures

Author's notes

This one took me a while to even parse correctly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and confirm that each position can be swapped at most once, meaning swaps are disjoint adjacent pairs. Then, recognize that the weighted sum can be maximized by greedily swapping adjacent elements when the swap increases the sum, but since swaps are non-overlapping, use dynamic programming to decide which disjoint swaps to perform.

Pro tip: Emphasize that the greedy choice of swapping whenever arr[i] < arr[i+1] fails because swaps are non-overlapping; instead, use DP to handle the dependency between adjacent positions. Also, mention that the problem reduces to selecting a set of non-adjacent edges in a path graph to maximize the gain from swapping.

1. Understand the problem and constraints

Restate the problem: given an array, you can perform non-overlapping adjacent swaps (each index in at most one swap) to maximize S = sum(arr[i]*(i+1)). Clarify that swaps are disjoint and can be performed in any order.

2. Analyze the effect of a swap

For a swap at positions i and i+1, the change in S is (arr[i+1]*(i+1) + arr[i]*(i+2)) - (arr[i]*(i+1) + arr[i+1]*(i+2)) = arr[i+1] - arr[i]. So swapping is beneficial if arr[i+1] > arr[i].

3. Formulate as a dynamic programming problem

Since swaps cannot overlap, we need to choose a set of disjoint adjacent pairs to swap. Define dp[i] as the maximum S achievable for the prefix up to index i. Transition: either skip position i (dp[i] = dp[i-1]) or swap i-1 and i (dp[i] = dp[i-2] + gain), where gain = arr[i] - arr[i-1] if positive.

4. Implement and optimize

Compute the base sum S0 without swaps, then add the maximum total gain from disjoint swaps using DP. The DP runs in O(n) time and O(1) space if we only keep the last two values.

5. Test with edge cases

Consider arrays of length 1, already sorted arrays, reverse sorted arrays, and arrays with equal elements. Verify that the DP correctly handles cases where no swap is beneficial.

Key Points to Mention

The change in weighted sum from swapping adjacent elements i and i+1 is arr[i+1] - arr[i].
Swaps must be non-overlapping, so we cannot swap adjacent pairs that share an index.
This is equivalent to selecting a set of non-adjacent edges in a path graph to maximize total gain.
Dynamic programming with state dp[i] representing the maximum gain for prefix up to i.
Time complexity O(n) and space complexity O(1) with rolling variables.
Edge cases: n=1, all elements equal, strictly increasing/decreasing arrays.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.