Amazon | Software Development Engineer (SDE) I | Online Assesment

I applied for the Amazon SDE 1 role and completed the online assessment (OA), which had a 4-hour time limit. The assessment included the following sections:

1. DSA Question: Medium to high difficulty level.
2. Software-Related Decision-Making Question
3. Behavioral Question
4. Honesty-Related Question
5. Optional Feedback Section


# Problem Statement: 1
Data scientists at Amazon are working on a utility for genome sequencing algorithms that look for specific patterns in DNA sequence strings. They have a string genome, which is a DNA sequence consisting of lowercase alphabets.

A substring of the DNA string genome is considered "special" if it satisfies either of the following conditions:

Special Substring Conditions:
1. The substring has exactly length 2, and both characters are equal
- i.e., genome[i] == genome[i + 1]

2. The substring has length ≥ 3, and:
- The first and last characters are equal, and
- The substring in between (i.e., genome[1 : n - 2]) contains exactly one distinct character.

Input:
A string genome of length n (1 ≤ n ≤ 10⁵), consisting of lowercase English letters.
Return
long int: the total number of special substrings in the DNA sequence

Example:
Given genome = "xyyx"

In the given string, "xyyx" and "yy" are the special substrings since "xyyx" holds the second condition true and "yy" holds the first condition true.

Hence, there are 2 special substrings.

Sample Case 0
Input
genome = "xyyx"
Output
2

Valid Special Substrings:

- "yy" → satisfies condition 1 (length 2 and both chars equal)

- "xyyx" → satisfies condition 2 (first and last equal, middle part "yy" has one distinct character)

Sample Case 1
Input
genome = "aabbaa"
Output
4

Sample Case 2
Input
genome = "pq"
Output
0

I wasn't able to get the Optimal Solution I wasn't able to get the Optimal Solution
CODE (Brute Logic)
10/15 Test Cases Run Sucessfully

java []<br>public class GenomeAnalyzer {<br><br> public static long countSpecialSubstrings(String genome) {<br> int n = genome.length();<br> long count = 0;<br><br> for (int i = 0; i < n - 1; i++) <br> {<br> // Case 1<br> if (genome.charAt(i) == genome.charAt(i + 1)) <br> count++;<br> }<br><br> // Case 2<br> for (int i = 0; i < n; i++) <br> {<br> for (int j = i + 2; j < n; j++) <br> {<br> if (genome.charAt(i) == genome.charAt(j)) <br> {<br> if (isMiddleOneDistinct(genome, i + 1, j - 1))<br> count++;<br> }<br> }<br> }<br><br> return count;<br> }<br><br> // check the middle section for 1 distinct char using early break<br> private static boolean isMiddleOneDistinct(String s, int start, int end) <br> {<br> if (start > end) return false;<br><br> char ref = s.charAt(start);<br> for (int i = start + 1; i <= end; i++) <br> {<br> if (s.charAt(i) != ref) <br> return false;<br> }<br> return true;<br> }<br><br> public static void main(String[] args) {<br> String genome = "aabbaa";<br> System.out.println("Total Special Substrings: " + countSpecialSubstrings(genome)); // Output: 4<br> }<br>}<br><br>


# Problem Statement: 2
Amazon is optimizing its delivery network. Each delivery zone is represented as an interval indicating the range of house numbers it covers. The delivery zones may overlap with one another.

You are given:

- Two integer arrays a and b, where each i-th delivery zone covers the interval (a[i], b[i]), inclusive.

- An integer k, which is the maximum allowed length of a new delivery zone that can be added.

You are allowed to add exactly one new delivery zone (x, y) such that:

- y - x ≤ k

Your goal is to minimize the number of disconnected delivery zones after adding this one new interval.

Definitions
- A connected set of delivery zones is a group of intervals where every house number in the continuous range from the minimum a[i] to the maximum b[i] is covered by at least one delivery zone.
- Two sets are disconnected if there is a gap between them that is not covered by any zone.


Input
a[n]: List of integers, the start of each interval.

b[n]: List of integers, the end of each interval.

k: Integer, the maximum length of the new interval that can be added.

Output
Return a single integer: the minimum number of connected delivery zone sets after optimally adding one interval of length ≤ k.

Input:
a = [1, 2, 5, 10]
b = [2, 4, 8, 11]
k = 2
Output :
2