FAANG | OA Coding Questions and Solutions | Set - 21 | 2022

Question

All past online assesments of Amazon can be found using the tag "amazon_oa" in the search bar.

Here is the link : https://www.desiqna.in/tag/amazon_oa

Answer 1

// C++ implementation to count total
// number of ways to split a
// string to get prime numbers

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
bool sieve[1000000];

// Function to build sieve
void buildSieve()
{
    for (auto& i : sieve)
        i = true;

    sieve[0] = false;
    sieve[1] = false;

    for (int p = 2; p * p <= 1000000;
        p++) {

        // If p is a prime
        if (sieve[p] == true) {

            // Update all multiples
            // of p as non prime

            for (int i = p * p; i <= 1000000;
                i += p)
                sieve[i] = false;
        }
    }
}

// Function to check whether a number
// is a prime number or not
bool isPrime(string number)
{
    int num = stoi(number);
    return sieve[num];
}

// Function to find the count
// of ways to split string
// into prime numbers
int rec(string& number, int i,
        vector<int>& dp)
{
    if (dp[i] != -1)
        return dp[i];

    int cnt = 0;

    for (int j = 1; j <= 6; j++) {

        // Number should not have a
        // leading zero and it
        // should be a prime number
        if (i - j >= 0
            && number[i - j] != '0'
            && isPrime(
                number.substr(i - j, j))) {

            cnt += rec(
                number, i - j, dp);
            cnt %= MOD;
        }
    }
    return dp[i] = cnt;
}

// Function to count the
// number of prime strings
int countPrimeStrings(string& number)
{
    int n = number.length();
    vector<int> dp(n + 1, -1);
    dp[0] = 1;
    return rec(number, n, dp);
}

// Driver code
int main()
{
    buildSieve();

    string s1 = "3175";

    cout << countPrimeStrings(s1) << "\n";

    return 0;
}

Answer 2

Given a string made up of integers 0 to 9, count the number of ways to split the string into prime numbers in the range of 2 to 1000 inclusive, using up all the characters in the string.

Each prime number, pn, must not contain leading 0s, and 2 <= pn <= 1000.

Constraints

The input string does not contain any leading 0s.

Examples

Example 1:

Input: "31173"

Output: 6

Explanation:

The string "31173" can be split into prime numbers in 6 ways:

• [3, 11, 7, 3]
• [3, 11, 73]
• [31, 17, 3]
• [31, 173]
• [311, 7, 3]
• [311, 73]