PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCareers

Quick Overview

This pair of problems evaluates array manipulation, partitioning, and sum-optimization competencies, focusing on handling element removals, contiguous partitions, and maximizing subarray sums.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Solve Two Array Optimization Problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two coding problems from the same interview round. **Problem 1: Split a gold chain fairly** An array `weights` represents the weights of consecutive links in a gold chain. You must perform the following steps: 1. Remove exactly one link. 2. Reconnect the remaining links, preserving their relative order. 3. Cut the reconnected chain once so that it becomes two non-empty contiguous parts. Return `true` if there exists a choice of removed index `r` and cut position `k` in the new array such that the two resulting parts have the same total weight. Otherwise, return `false`. Formally, after removing `weights[r]`, the new array is: - `weights[0], weights[1], ..., weights[r-1], weights[r+1], ..., weights[n-1]` You need to determine whether there exists a cut position `k` in this new array such that: - sum of elements from index `0` to `k` equals the sum of elements from `k+1` to the end. **Follow-up:** Return all valid `(r, k)` pairs, where `r` is the removed index in the original array and `k` is the cut index in the array after removal. --- **Problem 2: Maximize a subarray whose endpoints are equal** Given an integer array `a`, find indices `i` and `j` such that: - `0 <= i <= j < n` - `a[i] == a[j]` - the value of `a[i] + a[i+1] + ... + a[j]` is maximized Return one pair `(i, j)` that achieves the maximum sum. **Follow-up:** Solve the problem using strictly `O(1)` extra space, even if a higher time complexity is allowed.

Quick Answer: This pair of problems evaluates array manipulation, partitioning, and sum-optimization competencies, focusing on handling element removals, contiguous partitions, and maximizing subarray sums.

Part 1: Split a Gold Chain Fairly

You are given an integer array `weights` representing the weights of consecutive links in a gold chain. Remove exactly one link, reconnect the remaining links without changing their relative order, and then cut the new chain once so that it becomes two non-empty contiguous parts. Return `True` if there exists some removed index `r` and cut index `k` in the new array such that the two parts have the same total weight. Otherwise, return `False`.

Constraints

  • 0 <= len(weights) <= 2000
  • -10^9 <= weights[i] <= 10^9

Examples

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

Expected Output: True

Explanation: Remove index 1 to get [1, 1]. Cutting after k = 0 gives two parts with sums 1 and 1.

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

Expected Output: False

Explanation: No choice of removed link and cut position produces two equal-weight non-empty parts.

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

Expected Output: True

Explanation: Removing any one link leaves [1, 1], which splits equally at k = 0.

Input: ([5, 5],)

Expected Output: False

Explanation: After removing one link, only one link remains, so you cannot cut into two non-empty parts.

Hints

  1. Use prefix sums so you can compute the weight of a left segment in O(1) time after a hypothetical removal.
  2. For a fixed removed index `r`, a cut index `k` maps differently depending on whether `k < r` or `k >= r`.

Part 2: Split a Gold Chain Fairly - Return All Valid Pairs

You are given an integer array `weights` representing consecutive link weights in a gold chain. Remove exactly one link, reconnect the remaining links without changing their relative order, and cut the new chain once into two non-empty contiguous parts. Return all valid `(r, k)` pairs where `r` is the removed index in the original array and `k` is the 0-based cut index in the array after removal. A pair is valid if the left and right parts have the same total weight. Return the pairs sorted by increasing `r`, then increasing `k`.

Constraints

  • 0 <= len(weights) <= 2000
  • -10^9 <= weights[i] <= 10^9
  • The number of valid answers can be O(n^2)

Examples

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

Expected Output: [(1, 0)]

Explanation: Only removing index 1 leaves [1, 1], and cutting after k = 0 is balanced.

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

Expected Output: [(0, 0), (1, 0), (2, 0)]

Explanation: Any removed index leaves [1, 1], and the only cut k = 0 works.

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

Expected Output: [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]

Explanation: Every removal and every possible cut produces equal sums because all sums are 0.

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

Expected Output: []

Explanation: After any removal, the remaining total is 6, but no cut produces left sum 3.

Input: ([7, 7],)

Expected Output: []

Explanation: After removing one link, only one element remains, so no valid cut exists.

Hints

  1. The follow-up only changes what you return, not the core check for whether a specific `(r, k)` works.
  2. For each removed index `r`, scan every possible cut `k` in the reconnected chain and compute the left sum with prefix sums.

Part 3: Maximum-Sum Subarray with Equal Endpoints

Given an integer array `a`, find indices `(i, j)` such that `0 <= i <= j < n`, `a[i] == a[j]`, and the subarray sum `a[i] + a[i+1] + ... + a[j]` is as large as possible. Return one optimal pair. If multiple pairs achieve the same maximum sum, return the one with the smallest `i`; if there is still a tie, return the one with the smallest `j`. If the array is empty, return `None`.

Constraints

  • 0 <= len(a) <= 200000
  • -10^9 <= a[i] <= 10^9

Examples

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

Expected Output: (0, 2)

Explanation: The endpoints match and the subarray sum is 3, which is better than any single-element choice.

Input: ([5, -10, 5, 5],)

Expected Output: (2, 3)

Explanation: The best valid subarray is [5, 5] from indices 2 to 3, with sum 10.

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

Expected Output: (2, 2)

Explanation: No longer subarray has equal endpoints, so the best choice is the single element 4.

Input: ([5, -10, 5],)

Expected Output: (0, 0)

Explanation: The best sum is 5, achieved by both (0, 0) and (2, 2); tie-breaking chooses the smaller i.

Input: ([],)

Expected Output: None

Explanation: There is no valid pair in an empty array.

Hints

  1. The sum from `i` to `j` can be written as `prefix[j+1] - prefix[i]`.
  2. For each value `x`, while scanning from left to right, keep the occurrence of `x` with the smallest prefix sum before it.

Part 4: Maximum-Sum Subarray with Equal Endpoints Using O(1) Extra Space

Solve the same task as Part 3, but now you must use strictly `O(1)` extra space, excluding the returned answer. Given an integer array `a`, return indices `(i, j)` such that `a[i] == a[j]` and the sum of `a[i..j]` is maximized. If multiple pairs achieve the same maximum sum, return the one with the smallest `i`; if still tied, the one with the smallest `j`. If the array is empty, return `None`.

Constraints

  • 0 <= len(a) <= 5000
  • -10^9 <= a[i] <= 10^9

Examples

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

Expected Output: (0, 2)

Explanation: The best valid subarray has equal endpoints 2 and sum 3.

Input: ([5, -10, 5, 5],)

Expected Output: (2, 3)

Explanation: The subarray from 2 to 3 has equal endpoints and sum 10, which is optimal.

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

Expected Output: (2, 2)

Explanation: Only length-1 subarrays are valid here, and index 2 gives the largest sum.

Input: ([5, -10, 5],)

Expected Output: (0, 0)

Explanation: The best sum is 5, and tie-breaking prefers the earlier index.

Input: ([],)

Expected Output: None

Explanation: There is no valid answer for an empty array.

Hints

  1. Without a hashmap, you can still try every starting index `i` and extend `j` to the right with a running sum.
  2. A subarray is only a candidate when `a[j] == a[i]`, but you do not need extra arrays to keep track of sums.
Last updated: Apr 27, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • Careers
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Turnstile Crossing Times - Google (hard)
  • Simulate In-Place Cellular State Updates - Google (hard)
  • Determine Whether a Word Exists in a Graph - Google (medium)
  • Solve Shortest Paths and Rental Allocation - Google (medium)
  • Find Shortest Queue with Few Calls - Google (medium)