FastPrepCircular Primes Below a Limit
Problems/Circular Primes Below a Limit

Circular Primes Below a Limit

Amazon logoAmazon● EasyINTERNPHONE SCREEN
QuestionExamples

Problem statement

Source note: Amazon asked this in the first round of a summer intern technical phone screen, for a team that works in C. The task was to list each prime under 10^6 whose digit rotations are all prime as well.

The report gave only that one sentence. Our choices here: the limit is a parameter n from 1 to 10^6 instead of a fixed one million, the answer is returned as an increasing list instead of printed, and a rotation counts even when it is larger than n. The usual definitions apply: rotating moves the first digit to the end, and a one-digit prime counts as circular.

Our version is about 90% the same as the reported question.

A circular prime is a prime number whose every rotation of its digits is also prime. To rotate a number, move its first digit to the end; the rotations of 197 are 197, 971 and 719, and all three are prime, so 197 is a circular prime. A one-digit prime is a circular prime because its only rotation is itself.

The problem statement continues
Pro

Examples

Example 1

n = 100return = [2,3,5,7,11,13,17,31,37,71,73,79,97]
  • Every prime below 10 is circular, since a one-digit number has only itself as a rotation.
  • 11, 13, 17, 31, 37, 71, 73, 79 and 97 are circular: for example 13 and 31 are both prime. 19 is not, because 91 = 7 × 13.
02 · Example 2
FastPrep Pro
Reported in 1 Amazon interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
See Amazon hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Amazon interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week