We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Incremental Memory Leak

Number: 1971

Difficulty: Medium

Paid? No

Companies: TikTok

Problem Description

Given two integers memory1 and memory2 representing the available memory (in bits) on two memory sticks, a faulty program allocates an increasing amount of memory every second. At the iᵗʰ second, i bits are allocated to the stick with more available memory (or stick1 if they are equal). If neither stick has at least i bits free, the program crashes. Return an array [crashTime, memory1_crash, memory2_crash] where crashTime is the time when the program crashes and memory1_crash and memory2_crash are the remaining memory bits.

Key Insights

  • The allocation amount increases by 1 each second (i.e., 1, 2, 3, ...).
  • At every step, determine the stick with the higher available memory (or the first in case of a tie).
  • The simulation stops when the chosen stick cannot satisfy the allocation requirement.
  • A straightforward simulation is efficient enough given the constraints.

Space and Time Complexity

Time Complexity: O(k) where k is the number of seconds before the crash (roughly proportional to the square root of the total memory). Space Complexity: O(1) since only a few variables are used.

Solution

We use a simulation approach:

  1. Initialize a counter (timeAllocated) starting at 1.
  2. For each second, check which memory stick has more available memory. If they are equal, allocate from the first stick.
  3. If the selected stick has at least timeAllocated bits available, subtract the allocation; otherwise, break out as the program crashes.
  4. Continue this process until the program crashes.
  5. Return an array containing the current second (crash time) and the remaining memory in both sticks.

This method directly simulates the allocation process and leverages simple conditional checks and arithmetic operations, avoiding the need for complex data structures.

Code Solutions

# Function to simulate the faulty memory allocation process.
def incrementalMemoryLeak(memory1, memory2):
    time_allocated = 1  # Starting from first second allocation
    # Loop until we can allocate memory successfully
    while True:
        # Check the memory stick with more available memory.
        if memory1 >= memory2:
            # If insufficient memory on memory1 for allocation, break.
            if memory1 < time_allocated:
                break
            # Allocate memory from memory1.
            memory1 -= time_allocated
        else:
            # If insufficient memory on memory2 for allocation, break.
            if memory2 < time_allocated:
                break
            # Allocate memory from memory2.
            memory2 -= time_allocated
        # Move to next second.
        time_allocated += 1
    # Return crash time and remaining memory in both sticks.
    return [time_allocated, memory1, memory2]

# Test cases
print(incrementalMemoryLeak(2, 2))   # Expected output: [3, 1, 0]
print(incrementalMemoryLeak(8, 11))  # Expected output: [6, 0, 4]
← Back to All Questions