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 Medium difficulty Coding & Algorithms question, commonly asked during HR Screen rounds at SoFi.

What role is this question designed for?

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

Simulate 1-D collisions and scale to huge inputs

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: HR Screen

Given an array of integers representing objects on a 1-D track, where the sign indicates direction (positive moves right, negative moves left) and the absolute value indicates mass, simulate all collisions: when two objects moving toward each other meet, the smaller mass is destroyed; if equal, both are destroyed; otherwise, the larger continues with its original direction. Return the final sequence of objects in order after all collisions resolve. Implement an O(n) time solution using an appropriate data structure and analyze time and space complexity. Follow-ups: How would you handle extremely large inputs (e.g., up to 1e8 elements) under tight memory limits (1–2 GB)? Discuss streaming, chunking, and external-memory approaches. How would you parallelize processing across cores while ensuring correctness at chunk boundaries? What test cases and invariants would you use to validate the implementation?

Quick Answer: This question evaluates a candidate's algorithm design skills, proficiency with appropriate data structures, and ability to analyze time and space complexity alongside system-level scalability concerns for large datasets.

You are given an array of integers `asteroids` representing objects in a row on a 1-D track. For each object, the absolute value represents its mass and the sign represents its direction: positive means moving right, negative means moving left. Every object moves at the same speed. Resolve all collisions and return the final state of the objects after all collisions resolve. A collision occurs only when an object moving right is immediately followed by an object moving left (they meet). When two objects collide, the one with the smaller mass is destroyed; if both have equal mass, both are destroyed; otherwise the larger one survives and continues in its original direction. Two objects moving in the same direction, or moving apart (a left-mover before a right-mover), will never meet. Implement an O(n) time solution using a stack. Return the surviving objects in their original left-to-right order. Follow-ups (discussion): For extremely large inputs (e.g. up to 1e8 elements) under tight memory (1-2 GB), discuss streaming the input and keeping only the bounded stack in memory, chunking with external/on-disk spillover for the surviving prefix, and how to parallelize across cores while reconciling the boundary stacks between adjacent chunks.

Constraints

2 <= asteroids.length (the surrounding problem assumes at least a few elements, but the solution also handles 0 and 1)
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0 (every object has a direction and nonzero mass)

Examples

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

Expected Output: [5, 10]

Explanation: The -5 meets the 10 (larger) and is destroyed; 5 and 10 survive since they never meet.

Input: ([8, -8],)

Expected Output: []

Explanation: Equal masses moving toward each other destroy both.

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

Expected Output: [10]

Explanation: -5 destroys 2 (smaller), then meets 10 (larger) and is destroyed; only 10 remains.

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

Expected Output: [-2, -1, 1, 2]

Explanation: All left-movers precede all right-movers, so nothing ever collides.

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

Expected Output: [-2, -2, -2]

Explanation: The first -2 destroys the 1, then the remaining left-movers pass freely.

Input: ([],)

Expected Output: []

Explanation: Empty input yields an empty result.

Input: ([7],)

Expected Output: [7]

Explanation: A single object never collides.

Input: ([-3, 3],)

Expected Output: [-3, 3]

Explanation: A left-mover followed by a right-mover diverge and never meet.

Input: ([3, -3, 3, -3],)

Expected Output: []

Explanation: Each adjacent right/left equal-mass pair annihilates, leaving nothing.

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

Expected Output: [-6, 6]

Explanation: 5 and -5 annihilate; then -6 has nothing to its left to hit, and 6 diverges from it, so -6 and 6 survive.

Hints

A collision can only happen between a right-moving object (positive) and a left-moving object (negative) that appears immediately after it. Same-direction or diverging neighbors never meet.
Use a stack of the surviving objects so far. The only object the current one can collide with is the top of the stack.
When the current object moves left (negative), repeatedly compare it against positive objects on top of the stack: pop the smaller, pop both on a tie, and stop (current destroyed) if the top is larger or equal.

Quick Overview

This question evaluates a candidate's algorithm design skills, proficiency with appropriate data structures, and ability to analyze time and space complexity alongside system-level scalability concerns for large datasets.