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 easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at SoFi.

What role is this question designed for?

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

Rearrange array to maximize positive prefix sums

Q: Rearrange array to maximize positive prefix sums

This question evaluates array manipulation, prefix-sum reasoning, and greedy/combinatorial optimization skills for maximizing a permutation-based metric in the Coding & Algorithms category.

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

## Problem You are given an integer array `a` of length `n`. You may **rearrange** the elements in any order. Define the prefix sums of a permutation `p` as: - `pref[i] = p[0] + p[1] + ... + p[i]` for `0 <= i < n` Let `score(p)` be the number of indices `i` such that `pref[i] > 0`. ### Task Compute the **maximum possible value of** `score(p)` over all permutations `p` of the array. ### Input - Integer array `a` (may contain negative, zero, and positive values). ### Output - An integer: the maximum number of positive prefix sums achievable. ### Constraints - `1 <= n <= 2 * 10^5` - `-10^9 <= a[i] <= 10^9` - Target time complexity: `O(n log n)` (or better). ### Example - Input: `[2, -1, 2, -3]` - One optimal permutation: `[2, 2, -1, -3]` - Prefix sums: `[2, 4, 3, 0]` → positive prefix sums = `3` → Output: `3`

Quick Answer: This question evaluates array manipulation, prefix-sum reasoning, and greedy/combinatorial optimization skills for maximizing a permutation-based metric in the Coding & Algorithms category.

You are given an integer array `a` of length `n`. You may rearrange the elements in any order. For a permutation `p` of the array, define its prefix sums as: - `pref[i] = p[0] + p[1] + ... + p[i]` for `0 <= i < n` Let `score(p)` be the number of indices `i` such that `pref[i] > 0`. Your task is to compute the maximum possible value of `score(p)` over all permutations of `a`. Example: - Input: `[2, -1, 2, -3]` - One optimal permutation: `[2, 2, -1, -3]` - Prefix sums: `[2, 4, 3, 0]` - Positive prefix sums: `3` - Output: `3`

Constraints

1 <= len(a) <= 2 * 10^5
-10^9 <= a[i] <= 10^9

Examples

Input: [2, -1, 2, -3]

Expected Output: 3

Explanation: Sorting in descending order gives [2, 2, -1, -3]. The prefix sums are 2, 4, 3, 0, so 3 prefix sums are positive.

Input: [-5]

Expected Output: 0

Explanation: The only prefix sum is -5, which is not positive.

Input: [-5, 10]

Expected Output: 2

Explanation: An optimal order is [10, -5]. The prefix sums are 10 and 5, and both are positive.

Input: [0, 0, 5, -6, 1]

Expected Output: 4

Explanation: Sorting descending gives [5, 1, 0, 0, -6]. The prefix sums are 5, 6, 6, 6, 0, so the answer is 4.

Input: [-1, -1, -1, 4]

Expected Output: 4

Explanation: Sorting descending gives [4, -1, -1, -1]. The prefix sums are 4, 3, 2, 1, so all 4 prefixes are positive.

Input: [0, 0, 0]

Expected Output: 0

Explanation: Every prefix sum is 0, and 0 is not considered positive.

Hints

For any fixed prefix length `k`, which choice of `k` elements gives the largest possible prefix sum?
Compare the prefix sum at each index after sorting in non-increasing order with the prefix sum at the same index in any other permutation.

Quick Overview

This question evaluates array manipulation, prefix-sum reasoning, and greedy/combinatorial optimization skills for maximizing a permutation-based metric in the Coding & Algorithms category.