Katkat

Compute delay times in priority array

AmazonSoftware Engineer · Online Assessment

Last updated

This question evaluates algorithmic efficiency in array processing, specifically reasoning about nearest-smaller relationships and the use of auxiliary structures to achieve subquadratic performance.

Question

Given an array of integers representing task priorities processed from right to left, return an array where each element is the distance (index difference) to the first smaller priority found to its right (or 0 if none exists). Design an algorithm faster than O(N^ 2).