Compute array products excluding self and top-k
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Algorithms
### 1) Product of array except self (no division)
Given an integer array `nums` of length `n`, return an array `ans` where:
- `ans[i]` = product of all `nums[j]` for `j != i`
- You **must not use division**
- Target time: **O(n)**
- Extra space: **O(1)** beyond the output array
#### Follow-ups
- How does your approach handle **many zeros** in the input?
- How do you handle **overflow / very large products**?
### 2) Find the k largest elements
Given an unsorted array of numbers and an integer `k`, return the **k largest elements** (order does not matter unless specified).
Discuss time/space trade-offs for different approaches.
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.
