Implement Function to Determine Mode and Prime Numbers
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
Implementing utility algorithms within a data-processing library.
##### Question
Write a function that returns the mode of an integer list; if all values are unique return None, and support multiple modes when ties exist. Given an integer array containing 1 to n, output all prime numbers in the array.
##### Hints
Emphasize time complexity and edge-case handling.
Quick Answer: This question evaluates algorithmic problem-solving skills, including frequency analysis for mode computation, correct handling of ties and uniqueness edge cases, and basic number-theoretic competency for prime identification.
Given an integer array nums, implement analyze_numbers(nums) that returns a 2-element list: [modes, primes]. modes is either None (if all values in nums appear exactly once) or a sorted list of all values that have the maximum frequency (support ties). primes is a sorted list of unique prime numbers present in nums (values > 1 only). If nums is empty, return [None, []].
Constraints
- 0 <= len(nums) <= 200000
- -10^6 <= nums[i] <= 10^6
- Return modes as None if and only if every value appears once
- Return primes as unique values in ascending order
- 1 and negative numbers are not prime
Solution
from typing import List
from collections import Counter
import math
def analyze_numbers(nums: List[int]) -> list:
# Modes computation
if not nums:
return [None, []]
freq = Counter(nums)
max_freq = max(freq.values()) if freq else 0
modes = None if max_freq <= 1 else sorted([v for v, c in freq.items() if c == max_freq])
# Primes computation (unique, sorted)
pos_vals = {x for x in nums if x > 1}
if not pos_vals:
primes = []
else:
max_val = max(pos_vals)
sieve = bytearray(b"\x01") * (max_val + 1)
sieve[0:2] = b"\x00\x00"
limit = int(math.isqrt(max_val))
for p in range(2, limit + 1):
if sieve[p]:
start = p * p
step = p
sieve[start:max_val + 1:step] = b"\x00" * (((max_val - start) // step) + 1)
primes = sorted([x for x in pos_vals if sieve[x]])
return [modes, primes]
Explanation
Count frequencies with a hash map to find the maximum occurrence and collect all values that match it. If the maximum is 1, there is no mode, so return None. For primes, gather unique positive values > 1 and run a Sieve of Eratosthenes up to their maximum to mark primality in O(U log log U), where U is the maximum positive value. Finally, filter the set with the sieve and sort the result.
Time complexity: O(n + U log log U), where n is len(nums) and U is the maximum positive value in nums. Space complexity: O(n + U).
Hints
- Use a frequency map (e.g., collections.Counter) to find the maximum frequency and all values that match it.
- If the maximum frequency is 1, return modes = None.
- To list primes efficiently, build a sieve up to the maximum positive value in nums and filter the unique values.
- Ignore values <= 1 for prime detection.