TheJobOverflow | Amazon Hackon, Online Assessment Asked Question (28th September 2023) | Ecnipering a String

Question: Amazon Hackon, Online Assessment Asked Question (28th September 2023) | Ecnipering a String | Maximum Prime Difference

Entering edit mode

ADD COMMENT • link

Entering edit mode

Problem 1: Enciphering a String

Solution: Iterative Processing

This is a straightforward string processing problem that can be solved by iterating through the string character by character. The core logic involves maintaining a running integer k which is updated based on whether the current character is a vowel or a consonant before being used to calculate the encoded value.

The logic is as follows:

Initialization: Start with the input string and the initial integer k. Create a list or another data structure to store the resulting encoded numbers.
Iteration: Loop through each character of the string from left to right.
Vowel/Consonant Check: For each character, determine if it is a vowel (a, e, i, o, u).
Update k:
- If the character is a vowel, increment the current value of k by 2.
- If the character is a consonant, increment the current value of k by 1.
Encoding: Multiply the ASCII value of the current character by the newly updated value of k.
Store Result: Add the calculated integer to your results list.
Final Output: After the loop finishes, join the numbers in the results list into a single string, separated by spaces.

#include <iostream>
#include <string>
#include <vector>

// Function to check if a character is a vowel
bool isVowel(char c) {
    return (c == 'a' |

| c == 'e' |
| c == 'i' |
| c == 'o' |
| c == 'u');
}

void solveEncipher(const std::string& s, int k) {
    std::vector<long long> results;
    for (char c : s) {
        if (isVowel(c)) {
            k += 2;
        } else {
            k += 1;
        }
        long long encoded_value = (long long)c * k;
        results.push_back(encoded_value);
    }

    // Print the results separated by spaces
    for (size_t i = 0; i < results.size(); ++i) {
        std::cout << results[i] << (i == results.size() - 1? "" : " ");
    }
    std::cout << std::endl;
}

// Example usage
// int main() {
//     std::string s = "hello";
//     int k = 1;
//     solveEncipher(s, k); // Expected output: 208 404 540 648 888
//     return 0;
// }

Complexity Analysis:

Time Complexity: O(L). Where L is the length of the input string. The algorithm iterates through the string once.
Space Complexity: O(L). Space is required to store the list of encoded integer results before printing.

ADD COMMENT • link 16 days ago ANIRUDH • 0

Entering edit mode

Problem 2: Maximum Prime Difference

Solution: Sieve of Eratosthenes and a Single Pass

The most efficient way to solve this problem is to first pre-compute all prime numbers up to the maximum possible value in the array (10^5) using the Sieve of Eratosthenes. After creating the sieve, a single pass through the input array is sufficient to find the first and last indices of prime numbers and calculate their difference.

The logic is as follows:

Sieve of Eratosthenes: Create a boolean array, isPrime, of size 100001 and initialize all entries to true. Iterate from 2 up to the square root of the limit. For each prime number found, mark all of its multiples as not prime. This step efficiently pre-computes primality for all numbers in the given range.
Find First and Last Prime Indices: Initialize two variables, first_prime_idx = -1 and last_prime_idx = -1.
Single Pass: Iterate through the input array from left to right. For each number, use the isPrime array to check if it's a prime in constant time.
- If a prime number is found and first_prime_idx is still -1, it means this is the first prime encountered. Set first_prime_idx to the current index.
- Whenever a prime number is found, always update last_prime_idx to the current index.
Calculate Result: After the loop, if first_prime_idx remains -1, no primes were found, so return -1. Otherwise, the maximum difference is last_prime_idx - first_prime_idx.

#include <iostream>
#include <vector>
#include <cmath>

const int MAX_VAL = 100001;
std::vector<bool> isPrime(MAX_VAL, true);

// Pre-compute primes using Sieve of Eratosthenes
void sieve() {
    isPrime = isPrime[1] = false;
    for (int p = 2; p * p < MAX_VAL; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i < MAX_VAL; i += p) {
                isPrime[i] = false;
            }
        }
    }
}

int solveMaxPrimeDiff(int n, const std::vector<int>& arr) {
    int first_prime_idx = -1;
    int last_prime_idx = -1;

    for (int i = 0; i < n; ++i) {
        if (isPrime[arr[i]]) {
            if (first_prime_idx == -1) {
                first_prime_idx = i;
            }
            last_prime_idx = i;
        }
    }

    if (first_prime_idx == -1) {
        return -1; // No primes found
    } else {
        return last_prime_idx - first_prime_idx;
    }
}

// Example usage
// int main() {
//     sieve(); // Pre-compute primes once
//     int n = 7;
//     std::vector<int> arr = {4, 8, 7, 6, 11, 12, 3};
//     std::cout << solveMaxPrimeDiff(n, arr) << std::endl; // Expected output: 4 (index of 3 is 6, index of 7 is 2 -> 6-2=4)
//     return 0;
// }

Complexity Analysis:

Time Complexity: O(M log(log M) + N). Where M is the maximum value of an array element (10^5) and N is the size of the array. The sieve takes O(M log(log M)) time. The main loop takes O(N) time. This is highly efficient for the given constraints.
Space Complexity: O(M). The space is dominated by the boolean array required for the sieve.

ADD COMMENT • link 16 days ago ANIRUDH • 0