Amazon|SDE1|OA |QUESTIONS

Round 1

Questions:

Problem Statement: Substring with Swaps (Keyword Matching)

You are given a keyword string and a review string. Your task is to determine how many substrings in the review string can match the keyword string after performing at most one adjacent swap of characters in the substring.

Input:

• keyword: A string of length m, representing the target keyword.
• review: A string of length n, representing the review text.

Output:

• An integer indicating the number of substrings in the review string that can match the keyword after at most one adjacent swap.

Constraints:

1. 1 ≤ m ≤ n ≤ 10^5
2. Both strings consist of lowercase English letters.

Examples:

1. Input:
   keyword = "moon"
review = "monomon"
   Output:
   2
   Explanation:

   • Substrings "mono" and "moon" match the keyword after at most one adjacent swap.

2. Input:
   keyword = "java"
review = "jvaaajava"
   Output:
   3

---

Problem Statement: Maximize Sum of Skills

You are given a list of skills and their ratings for n individuals. Your task is to maximize the sum of ratings for exactly k individuals such that the chosen individuals' skill values are strictly less than the current individual's skill value.

Input:

1. skills: A list of n integers, where skills[i] represents the skill value of the i-th individual.
2. ratings: A list of n integers, where ratings[i] represents the rating of the i-th individual.
3. k: An integer representing the number of individuals to select.

Output:

• An integer representing the maximum possible sum of the ratings of the selected individuals.

Constraints:

1. 1 ≤ n ≤ 10^5
2. 1 ≤ k ≤ n
3. 1 ≤ skills[i], ratings[i] ≤ 10^9

Examples:

1. Input:
   skills = [4, 3, 5, 1]
ratings = [10, 20, 30, 40]
k = 2
   Output:
   50
   Explanation:

   • Choose individuals with skill values less than 4 (skill = 3, rating = 20) and 3 (skill = 1, rating = 40).
   • Maximum sum = 20 + 40 = 50.

2. Input:
   skills = [2, 4, 1]
ratings = [5, 10, 15]
k = 1
   Output:
   15
   Explanation:

   • Choose the individual with skill = 1 and rating = 15.

---

Followed by other behavioral and job-related assessments.