Solve subset-count and kth-factor problems
Overview
This question evaluates algorithm design and analysis skills, including selection under sum constraints with negatives and zeros, streaming and query-preprocessing strategies for repeated budgets, and number-theoretic factor enumeration for large N, all within the Coding & Algorithms domain.
Amazon
Oct 13, 2025, 9:49 PM
Data Scientist
Take-home Project
Coding & Algorithms
0
0
Two Independent Tasks
A) Maximum Count Under Sum Constraint
You are given an integer array arr and an integer budget n. Return the maximum number of elements you can select whose sum is ≤ n. Output only the count.
-
Constraints:
- 1 ≤ |arr| ≤ 200,000
- −1e9 ≤ arr[i] ≤ 1e9
- n fits in a 64-bit signed integer
-
Requirements:
- Design an algorithm that is optimal for the case arr[i] ≥ 0.
- Handle zeros and negative numbers correctly.
- Analyze time and space complexity.
- Prove correctness for the non‑negative case.
- Describe how to answer up to Q = 100,000 queries with different n on the same static arr.
-
Follow‑ups:
- If arr arrives as a stream you cannot fully store, what changes?
- Provide a strategy with at most ±1 error in the count and justify it.
B) Find the Kth Factor
Given positive integers N and K (1‑indexed), return the Kth factor of N in ascending order; if fewer than K factors exist, return −1.
- Optimize for N up to 10^12.
- Discuss an O(√N) solution that avoids duplicate factors when N is a perfect square and analyze time/space trade‑offs.
Solution
Login required
Show