Compute array products excluding self and top-k
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates skills in array manipulation, in-place algorithm design, numerical stability and edge-case reasoning (such as handling multiple zeros and large products), plus selection and ranking competencies for extracting the top-k elements.
Product of Array Except Self
Constraints
- Do not use division
- O(1) extra space beyond output
Examples
Input: ([1, 2, 3, 4],)
Expected Output: [24, 12, 8, 6]
Input: ([0, 1, 2, 3],)
Expected Output: [6, 0, 0, 0]
Input: ([0, 0, 2],)
Expected Output: [0, 0, 0]
Input: ([-1, 2, -3],)
Expected Output: [-6, 3, -2]
Hints
- Store prefix products in the output, then multiply by suffix products.
K Largest Elements
Constraints
- k may be 0 or larger than n
Examples
Input: ([3, 1, 5, 2, 5], 3)
Expected Output: [5, 5, 3]
Input: ([1], 5)
Expected Output: [1]
Input: ([4, 4, 4], 2)
Expected Output: [4, 4]
Input: ([9, 8], 0)
Expected Output: []
Hints
- A heap works well when k is much smaller than n.