Recently, I appeared for the OA round at Expedia Group foe SDE2. The assessment had 3 questions: 1 easy and 2 medium level. Here are the questions.

Question 1 :

You are given a list of item prices at a market. The store has a special discount rule:

1. The first item is purchased at full price.
2. For every subsequent item, the discount applied is equal to the lowest price among all previously purchased items.
3. The final price of an item cannot go below O.
4. Items must be purchased in the given order.
   Your task is to calculate the total cost of buying all items under this pricing rule.

Example
Suppose there are n = 4 prices: prices = 12, 5, 1, 41.
Output: 8

• First item costs 2 (no discount applies to the first item)
• Second item costs 5 - 2 = 3 (minimum previous price was 2)
• Third item costs max - min(2, 5), O) = max(1 - 2, 0) = 0
• Fourth item costs 4 - 1 = 3 (minimum previous price was 1)

Suppose n = 4, and prices = [4, 9, 2, 3)
Output: 10

• First item costs 4 (no discount applies to the first item
• Second item costs 9 - 4 = 5 (minimum previous price was 4)
• Third item costs max(2 - min(4, 9), 0) = max(2 - 4, 0) = 0
• Fourth item costs 3 - 2 = 1 (minimum previous price was 2)
  Constraints
• 1 <= n <= 10^6
• 1 & prices[i] ≤ 10^7, where 0 <= i <= n

Question 2 :

A palindrome reads the same forwards and backwards, eg. "mom", "a", or "radar". You are given an array of n strings consisting of lowercase English letters. In one operation, you can swap any two letters from any two distinct strings in the array. Determine the maximum number of palindromic strings that can be obtained by performing any number of these operations.

In other words, choose 4 integers, x,y,i,j such that 1 <= x,y <= n, 1 <= i <= length(arr[x]), 1 <= j <= length(arr[y]) and swap arr[x][i] and arr[y][j] using 1-based indexing.

Example
n = 4
arr = ["pass", "sas", "asps", "df"]

An optimal solution produces 3 palindromes:

1. Select x=1,y=3,i=3,j=1, swap(arr[x][i], arr[y][j])
   Result: arr = ["paas", "sas", "ssps", "df"]
2. Select x = 1,y = 3,i = 4,j = 3, swap(arr[x][i], arr[y][j])
   Result: arr = ["paap", "sas", "ssss", "df")
   Now we have 3 palindromic strings: "paap", "sas", and "ssss Therefore, return 3.

Constraints
• 1 <= n <= 1000.
• 1 <= length(arr[i]) <= 1000
• All strings consist of lowercase English letters only onfidential

Question 3 :

A class has students with various talents, each represented by an integer from 1 to talentsCount. You need to form teams for a quiz competition, where each team must have at least one member with each talent.
Teams must be formed from consecutive students in the array. For each possible starting position, determine the minimum number of students needed to form a valid team. If it is not possible to form a team with all talents from a particular starting position, return -1 for that position.

Example
talentsCount = 3
talent = [1, 2, 3, 2, 1]
• Starting at position 1: [1, 2, 3] includes all talents, minimum size = 3
• Starting at position 2: [2, 3, 2, 1] is the smallest subarray with all talents, minimum size = 4
• Starting at position 3: [3, 2, 1] includes all talents, minimum size = 3
• Starting at positions 4 and 5: Cannot form a team with all talents, return -1

The result is [3, 4, 3, -1, -1].

Return : at each index, the minimum size subarray required, or -1 if an appropriate subarray does not

Constraints
• 1 ≤ n, talentsCount ≤ 10^5
• 1 ≤ talent[i] <= talentsCount