Amazon Interview Question Senior Software Development Engineers
Country: United States
Interview Type: In-Person
{
public int[] generatePrime(int n) {
int[] prime = new int[n];
Arrays.fill(prime, -1);
prime[2] = 1;
int cnt = 1;
for (int i = 3; i < n ; i = i+ 2) {
if (prime[i] != 0) {
prime[i] = 1;
cnt++;
} else {
continue;
}
for (int j = i + i ; j < n ; j = j + i) {
prime[j] = 0;
}
}
int[] output = new int[cnt];
int i = 0;
/*for (int j=2 ; j < prime.length; j++) {
if (prime[j] == 1) {
output[i++] = j;
}
}*/
for (int j = 1; j < 10; j++) {
if (prime[j] == 1) {
output[i++] = j;
}
int k = j * 10;
int ct = 1;
while ( k < n) {
for ( int kk = k + 1; kk < k + Math.pow(10, ct) && kk < n; kk = kk + 2) {
if (prime[kk] == 1) {
output[i++] = kk;
}
}
ct++;
k *= 10;
}
}
return output;
}
}
bool isPrime(int num)
{
bool prime = true;
for (int i = 2; i <= num / 2; i ++)
if (num % i == 0)
{
prime = false;
break;
}
return prime;
}
int digits(int num)
{
int dig = 0;
while (num)
{
num /= 10;
dig ++;
}
return dig;
}
void insertMap(int num, int numdigits, map<int, int> &primeMap)
{
int base = numdigits - digits(num);
int baseAmount = 1;
while(base --)
baseAmount *= 10;
primeMap.insert(pair<int,int>(num * baseAmount, baseAmount));
cout << "insert: " << num * baseAmount << " - " << baseAmount << endl;
}
int restoreNum(int data, int baseAmount)
{
return data / baseAmount;
}
void primeSortInDigit(int range)
{
map<int,int> primeMap;
int numdigits = digits(range);
cout << "range is " << numdigits << " digits" << endl;
for (int num = 2; num <= range; num ++)
if (isPrime(num)){
cout << num << " ";
insertMap(num, numdigits, primeMap);
}
cout << "primeSortInDigit:" << endl;
for (map<int,int>::iterator it = primeMap.begin(); it != primeMap.end(); it ++)
cout << restoreNum(it->first, it->second) << " ";
cout <<endl;
}
You can generate a prefix tree / trie of the prime numbers and kind of do a inorder traversal on it. As numbers come in add it to the prefix tree. When inserting a number into trie, start from the last digit.
eg. 1 2 3 5 7 11 13 17 19 23 29
root
1 2 3 5 7 9
1 1 2 1 2
(11) (13) (23) (17) (29)
If a node represents a number mark the node as isNumber=true and ofcourse all the leafs represent the number.
Print the tree in preorder traversal (if the node has isNumber = true)
Basic thought here is to store the prime numbers in an array so that for determining any subsequent number say n, we need not do the checking for all n-1 integers instead we can check with only the given prime numbers less than n.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class generatePrimeNumbers {
public static void main(String[] args) {
int position = 1;
int N =40;
int arr[] = new int[N+1];
boolean valFound;
for (int i = 2; i < N; i++) {
valFound = findPrime(i, position, arr);
if(valFound){
arr[position++] = i;
}
}
//we have an array of prime numbers now(arr).
//Below code sorts the array lexicographically.
List<String> list = new ArrayList<String>();
for (int j = 1; j < position; j++) {
list.add(""+arr[j]);
}
Collections.sort(list);
for (String j : list) {
System.out.println(j);
}
}
private static boolean findPrime(int N, int position, int[] arr){
int flag = 0;
for (int i = 2; i < N; i++) {
if(position > 0 && flag == 0){
for (int j = 1; j < position; j++) {
if(N % arr[j] == 0)
return false;
}
flag = 1;
}
}
return true;
}
}
I am writing first time on this site. Do corrections if required.
package com.core;
import java.util.BitSet;
public class PrimeProg {
/**
* @param args
*/
public static void main(String[] args) {
int n = 50;// pass through the command line arguments.
int cnt = getPrimeCount(n);
int[] primeArr = new int[cnt];
int count = 0;
for(int k = 2;k <= n; k++){
if(findPrimes(k)){
primeArr[count++] = k;
}
}
int[] resultArr = swap(primeArr);
for(int i = 0; i < resultArr.length; i++) {
System.out.println(resultArr[i]);
}
}
private static int[] swap(int[] primeArr) {
int start = 0;
int mid = 0;
int end = primeArr.length-1;
boolean b= true;
boolean c= true;
for(int i=0; i<primeArr.length;i++) {
int x = primeArr[i]/10;
switch(x) {
case 1: {
int temp = primeArr[start];
primeArr[start] = primeArr[i];
primeArr[i] = temp;
start++;
mid++;
break;
}
case 2: {
if(b) {
++mid;
}
int temp = primeArr[mid];
primeArr[mid] = primeArr[i];
primeArr[i] = temp;
mid++;
b=false;
break;
}
case 3:{
if(primeArr[mid] != 3 && primeArr[mid+1] == 3) {
int temp = primeArr[mid];
primeArr[mid] = primeArr[mid+1];
primeArr[mid+1]=temp;
mid++;
}
int temp = primeArr[mid];
primeArr[mid] = primeArr[i];
primeArr[i] = temp;
mid++;
c=false;
break;
}
}
}
/*int temp = primeArr[mid];
primeArr[mid] = primeArr[end];
primeArr[end] = temp;*/
return primeArr;
}
private static boolean findPrimes(int i) {
boolean flag = true;
for(int j=2;j<=Math.sqrt(i);j++) {
if(i%j == 0) {
flag = false;
break;
}
}
return flag;
}
public static int getPrimeCount(int n){
if(n < 2)
return 0;
BitSet candidates = new BitSet(n - 1);
candidates.set(0, false);
candidates.set(1, false);
candidates.set(2, n);
for(int i = 2; i < n; i++)
if(candidates.get(i))
for(int j = i + i; j < n; j += i)
if(candidates.get(j) && j % i == 0)
candidates.set(j, false);
return candidates.cardinality();
}
}
Here is minor work around in code to reduce space required.
import java.util.ArrayList;
import java.util.Collections;
public class LexographicPrintingPrime {
void printPrime(int n){
ArrayList<String> arr = new ArrayList<String>();
arr.add(2+"");
arr.add(3+"");
arr.add(5+"");
arr.add(7+"");
int i = 8, k=0;
for(i =8; i<=n ;i++){
if(i%2 == 0)
continue;
if(i%3 == 0)
continue;
if(i%5 == 0)
continue;
if(i%7 == 0)
continue;
arr.add(i+"");
}
System.out.println(arr.size());
for(i=4; i< arr.size(); i++){
k = Integer.parseInt(arr.get(i));
for(int j = 2*k; j< n; j= j+k){
arr.remove(j+"");
}
}
Collections.sort(arr);
for(i=0; i< arr.size();i++){
System.out.println(arr.get(i));
}
}
}
How about the following approach for limited memory usage ?
Use an nlogn inplace sort algorithm like heap sort SUCH THAT the numbers should be compared
using the below compare function.
int compare(a,b,m) // m is the last prime number generated
{
int m_digits, a_digits, b_digits;
m_digits = digits(m);
a_digits = digits(a);
b_digits = digits(b);
a = a*pow(10,m_digits-a_digits);
b = a*pow(10,m_digits-b_digits);
return a.compare(b);
}
int digits(int a)
{
return ceiling(log(a)+1)); //log base 10;
}
Check this...
#include<stdio.h>
struct Element{
int val;
struct Element *next;
};
struct BaseElements{
struct Element *nodes;
struct Element *head;
};
struct BaseElements *Base[10] ;
struct Element* InsertNewNode( int v ){
struct Element *node = (struct Element*)malloc(sizeof(struct Element));
node->val = v;
node->next = NULL;
return node;
}
void MakeList( int val ){
int index = ( val /10 == 0 ? val%10 : val/10);
struct Element *newnode = InsertNewNode( val );
if( !Base[index] ){
Base[index] = malloc( sizeof(struct BaseElements) );
Base[index]->nodes = newnode ;
}
else{
Base[index]->head->next = newnode;
}
Base[index]->head = newnode ;
//printf("%d , %d , %d\n",index , val,Base[index]->head->val);
return;
}
void main(){
int i = 0 , j = 0 , k = 0;
for( i = 2 ; i < 40 ; i++){
k = 0;
for( j = 2 ; j *j <= i ; j++){
if( i % j == 0){
k = 1;
break;
}
}
if( k == 0){
//printf("%d , %d\n",i,k);
MakeList(i);
}
}
for( i=0 ; i<10 ; i++){
if( !Base[i]){
continue;
}
else{
while( Base[i]->nodes != NULL){
printf("%d\n",Base[i]->nodes->val);
Base[i]->nodes = Base[i]->nodes->next;
}
}
}
return;
}
a O(1) space and O(n) isprime tests solution
#include <iostream>
bool IsPrime(unsigned n)
{
if (n<2)
return 0;
for(unsigned i=2;i<n/2+1;++i)
{
if ( 0 == n % i )
{
return false;
}
}
return true;
}
void LexographicPrintingPrime(int n)
{
if( n <= 1 )
return;
int m = n;
int digits = 0, startNum = 1;
for(; m > 0; m /= 10, digits++) ;
for(int digit = 1; digit <= 9; digit++){
int cntsToSearch = 1;
startNum = digit;
for(int i = digits; i > 1; i--, startNum *= 10, cntsToSearch *= 10) ;
cntsToSearch = startNum > n ? cntsToSearch / 10 : cntsToSearch;
startNum = startNum > n ? startNum / 10 : startNum;
for(int num = startNum, cnt = 1; num <= n && cnt <= cntsToSearch; num++, cnt++){
int curNum = num;
while( (curNum % 10) == 0 ) curNum /= 10;
for(; curNum <= num; curNum *= 10 )
if( IsPrime(curNum) )
std::cout<<curNum<<std::endl;
}
}
}
.net - C#
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int N;
//string NS;
Console.Write("N: ");
N = Console.Read();
List<string> result = getArray(N);
foreach (string el in result)
Console.WriteLine(el);
Console.ReadKey();
}
private static bool isPrime(int i)
{
bool isPrime = true;
for (int j = 2; j <= i / 2; j++)
{
if (i % j == 0)
{
isPrime = false;
break;
}
}
return isPrime;
}
private static List<string> getArray(int N)
{
List<string> result = new List<string>();
for (int k = 2; k < N; k++)
{
if (isPrime(k))
result.Add(k.ToString());
}
result.Sort();
return result;
}
}
}
C++ version using Sieve of Eratosthenes. Uses std::vector<bool> which in most implementations is equivalent to a bitset in terms of memory consumption.
#include <iostream>
#include <vector>
#include <iterator>
#include <cstdint>
#include <cmath>
#include <stdexcept>
#include <algorithm>
std::vector<uint64_t> sieve_eratosthenes(uint64_t n) {
if (n <= 2)
throw std::invalid_argument("n must be > 2");
std::vector<bool> sieve(n, true);
sieve[0] = false;
sieve[1] = false;
for (uint64_t i = 2; i < std::sqrt(n); i++) {
for (uint64_t j = i * 2; j < n; j += i) {
sieve[j] = false;
}
}
std::vector<uint64_t> primes;
for (uint64_t i = 2; i < sieve.size(); i++) {
if (sieve[i])
primes.push_back(i);
}
return primes;
}
struct sort_by_digit {
bool operator()(uint64_t a, uint64_t b) {
std::string astr = std::to_string(a);
std::string bstr = std::to_string(b);
if (astr.size() == bstr.size())
return a < b;
else
return astr[0] < bstr[0];
}
};
int main() {
std::vector<uint64_t> primes = sieve_eratosthenes(40);
std::sort(primes.begin(), primes.end(), sort_by_digit());
std::copy(primes.begin(), primes.end(), std::ostream_iterator<uint64_t>(std::cout, " "));
return 0;
}
public class LexographicPrintingPrime {
void printPrime(int n){
ArrayList<String> arr = new ArrayList<String>();
arr.add(2+"");
arr.add(3+"");
arr.add(5+"");
arr.add(7+"");
int i = 8, k=0;
for(i =8; i<=n ;i++){
if(i%2 == 0)
continue;
if(i%3 == 0)
continue;
if(i%5 == 0)
continue;
if(i%7 == 0)
continue;
arr.add(i+"");
}
System.out.println(arr.size());
for(i=4; i< arr.size(); i++){
k = Integer.parseInt(arr.get(i));
for(int j = 2*k; j< n; j= j+k){
arr.remove(j+"");
}
}
Collections.sort(arr);
for(i=0; i< arr.size();i++){
System.out.println(arr.get(i));
}
}
}
If N is given , then simply use steve Er, method and print all the prime numbers upto N . its done as it will be in sorted order.
Assuming you referred to Sieve of Eratosthenes (en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
It helps finding prime numbers and prints them in sorted order and not in lexicographic order (treating numbers as strings, for example 11 comes before 2)
Please let me know if you intended to describe some thing else.
import java.util.*;
public class Prime {
static int a[] = new int[1000];
static int count = 0;
static boolean flag = false;
static void findPrimes(int n){
a[0] = 2;
for(int i = 3; i < n; i++){
for(int j = 0; j < count; j++){
if(i%a[j] == 0){
flag = true;
break;
}
}
if(flag==true){
flag = false;
}
else{
count++;
a[count] = i;
}
}
String s[] = new String[count+1];
for(int i=0; i <=count; i++){
s[i]=""+a[i];
}
Arrays.sort(s);
for(int i=0; i<=count; i++)
System.out.print(s[i] +" ");
}
public static void main(String arg[]){
findPrimes(40);
}
}
Find all primes up to N using any method (e.g. sieve of Erastosthenes), then sort the numbers lexicographically.
- Anonymous October 24, 2013