PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates algorithmic reasoning in constrained pairings and resource allocation, focusing on maximizing aggregate memory under pairwise feasibility constraints while managing large input sizes.

  • hard
  • Amazon
  • Coding & Algorithms
  • Software Engineer

Maximize memory capacity with primary-backup servers

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are helping to optimize the capacity of a cloud system. There are `n` servers, where `n` is always even. The memory capacity of the *i*-th server is given by an integer array `memory` of length `n`. When there are `n = 2 * x` servers: - Exactly `x` servers will be chosen as **primary** servers. - The remaining `x` servers will be **backup** servers. For every primary server `P`, there must exist a **distinct** backup server `B` such that: > `memory[B] >= memory[P]` (Each server can be used as either primary or backup in exactly one such pair, so the `n` servers are partitioned into `x` (primary, backup) pairs.) The **system memory capacity** is defined as the sum of the memory capacities of all primary servers: > `capacity = sum(memory[P] over all primary servers P)` Your task is to determine the **maximum possible system memory capacity** that can be obtained by: - Partitioning the `n` servers into `n/2` disjoint (primary, backup) pairs, and - Respecting the constraint `memory[backup] >= memory[primary]` within each pair. ### Input - An even integer `n` (number of servers). - An integer array `memory` of length `n`, where `memory[i]` is the memory capacity of the *i*-th server. You may assume: - `2 <= n <= 2 * 10^5`, and `n` is even. - `1 <= memory[i] <= 10^9`. ### Output - Return a single integer: the **maximum possible system memory capacity**. ### Complexity requirement Design an algorithm efficient for `n` up to about `2 * 10^5` (i.e., significantly better than `O(n^2)` time).

Quick Answer: This question evaluates algorithmic reasoning in constrained pairings and resource allocation, focusing on maximizing aggregate memory under pairwise feasibility constraints while managing large input sizes.

Pair servers so each backup has memory at least its primary, and maximize the sum of primary memories.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

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

Expected Output: 4

Explanation: Pair adjacent sorted servers.

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

Expected Output: 101

Explanation: Large equal backups.

Input: ([5,3],)

Expected Output: 3

Explanation: One pair.

Hints

  1. Choose a representation that makes the requested operation direct.
  2. Handle empty inputs and boundary cases first.
Last updated: Jun 27, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • 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

  • Implement Top-p (Nucleus) Sampling in NumPy - Amazon (medium)
  • Implement Multi-Head Attention from Scratch in NumPy - Amazon (medium)
  • Detect and Break a Cycle in a Singly Linked List - Amazon (medium)
  • Caesar Cipher with Translation-Table Optimization - Amazon (medium)
  • Minimum Drone Delivery Time on a Ring of Hubs - Amazon (medium)