Simulate 1-D collisions and scale to huge inputs

Q: Simulate 1-D collisions and scale to huge inputs

This is a Coding & Algorithms interview question from SoFi for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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?

Simulate 1-D collisions and scale to huge inputs

Comments (0)