Solve subset-count and kth-factor problems
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You will solve two independent tasks:
A) Maximum count under sum constraint: Given an array of integers arr and an integer n, return the maximum number of elements you can choose such that their sum ≤ n. Output only the count.
Constraints: 1 ≤ |arr| ≤ 200000, −1e9 ≤ arr[i] ≤ 1e9, and n fits in 64-bit signed integer. Requirements: design an algorithm that is optimal for the case where all arr[i] ≥ 0; handle zeros and negative numbers correctly; analyze time and space complexity; prove correctness for the non‑negative case; and describe how you would support Q up to 100000 queries with different n on the same static arr.
Follow‑ups: What changes if arr arrives as a stream you cannot fully store? 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.
Quick Answer: 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.
