Solve array and list algorithms
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 315. Count of Smaller Numbers After Self LeetCode 23. Merge k Sorted Lists Design algorithm for Amazon Locker getPackage (retrieve package) operation
https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/ https://leetcode.com/problems/merge-k-sorted-lists/description/
Quick Answer: This question evaluates proficiency in array and list algorithms, including ordering and counting techniques for relative element ranking, merging multiple sorted inputs, and algorithmic design for a package locker retrieval operation, testing data structure manipulation and retrieval logic.
Given an integer array nums, for each index i compute how many elements to the right of i have a value strictly less than nums[i]. Return an array of the same length where the i-th value is this count.
Constraints
- 0 <= n <= 200000, where n is len(nums)
- -10^9 <= nums[i] <= 10^9
- Return a list of length n
- Aim for O(n log n) time; O(n) or O(n + U) space (U = number of distinct values) is acceptable
Hints
- Process elements from right to left while maintaining counts of seen values.
- Use coordinate compression to map values into a dense range.
- Maintain a Binary Indexed Tree (Fenwick Tree) to get prefix sums and update counts in O(log U).
- Alternatively, a modified merge sort can count smaller-on-right during merging.