Count Primes
Given an integer $n$, return the number of prime numbers that are strictly less than $n$. Use the Sieve of Eratosthenes algorithm.
Why Interviewers Ask This
Amazon asks this question to evaluate a candidate's ability to optimize for time complexity when handling large datasets, a core requirement for their high-scale systems. Interviewers specifically look for the transition from naive O(n^2) brute force approaches to the efficient O(n log log n) Sieve of Eratosthenes algorithm. They assess whether you understand memory trade-offs and can implement clean, bug-free code under pressure.
How to Answer This Question
1. Clarify Constraints: Immediately ask about the range of n to determine if standard integer types suffice or if edge cases like n=0 or n=1 need explicit handling.
2. Discuss Naive Approach: Briefly mention checking each number individually but highlight its inefficiency (O(n*sqrt(n))) to demonstrate awareness of optimization needs.
3. Propose Sieve Strategy: Explain the Sieve of Eratosthenes concept clearly: create a boolean array, mark multiples starting from 2 as non-prime, and iterate only up to sqrt(n).
4. Analyze Complexity: Explicitly state the Time Complexity (O(n log log n)) and Space Complexity (O(n)), justifying why this is optimal for Amazon's scale.
5. Implement Cleanly: Write code with clear variable names, handle boundary conditions first, and walk through a small example (like n=10) to verify logic before finalizing.
Key Points to Cover
- Demonstrating knowledge of O(n log log n) time complexity versus naive O(n*sqrt(n))
- Correctly handling edge cases like n <= 1 without runtime errors
- Optimizing the loop limit to sqrt(n) to reduce unnecessary iterations
- Using a boolean array for space efficiency rather than a list of primes
- Articulating the trade-off between pre-computation speed and memory usage
Sample Answer
To solve this efficiently, I would use the Sieve of Eratosthenes. First, I'd handle edge cases where n is less than 2 by returning zero immediately. For larger inputs, I'll initialize a boolean array of size n, assuming all numbers are prime initially. I start at 2, the first prime, and mark all its multiples as false. Crucially, I only need to sieve up to the square root of n because any composite number greater than that must have a factor smaller than the square root. As I iterate through the array, if I find an unmarked number, it is prime, so I count it and then mark all its multiples. This avoids redundant checks. For example, with n=10, we mark multiples of 2 (4, 6, 8), then 3 (9), stopping after sqrt(10). The remaining true values correspond to primes 2, 3, 5, and 7, giving us a count of 4. This approach runs in O(n log log n) time, which is significantly faster than checking primality for every number individually, making it ideal for the high-throughput environments typical at Amazon.
Common Mistakes to Avoid
- Starting the inner marking loop at i*i instead of 2*i, causing incorrect results for small multiples
- Iterating the outer loop up to n instead of sqrt(n), resulting in TLE on large inputs
- Forgetting to exclude 0 and 1 from the prime count despite them not being prime
- Implementing trial division for every number instead of sieving, leading to poor performance
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.