Amazon SDE 2 OA

Round 1

Questions:

1. Problem 1: You are given a binary string, s, consisting of characters 'O' and '1'. Transform this string into a palindrome by performing some operations. In one operation, swap any two characters, s[i] and s[j]. Determine the minimum number of swaps required to make the string a palindrome. If it is impossible to do so, then return -1.

   • Note: A palindrome is a string that reads the same backward as forward, for example, strings "O", "111", "010", "10101" are palindromes, but strings "001", "10", "11101" are not.
   • Example: Let string s = "0100101". The following shows the minimum number of steps required. It uses 1-based indexing.
     • Swap characters with indices (4, 5)

2. Problem 2: AWS provides a range of servers to meet the deployment needs of its clients. A client wants to choose a set of servers to deploy their application. Each server is associated with an availability factor and a reliability factor. The client defines the stability of a set of servers as the minimum availability amongst the servers multiplied by the sum of reliabilities of all the servers. Given two arrays of integers, availability, and reliability, where availability[i] and reliability[i] represent the availability and reliability factors of the ith server, find the maximum possible stability of any subset of servers. Since the answer can be large, report the answer modulo (10^9 + 7).

   • Example: Consider the set of servers where reliability = [1, 2, 2] and availability = [1, 1, 3].
     • The possible subsets of servers are:
       • Indices: [0], Stability: 1 * 1 = 1
       • Indices: [1], Stability: 1 * 2 = 2
       • Indices: [2], Stability: 3 * 2 = 6
       • Indices: [0, 1], Stability: min(1, 1) * (1 + 2) = 3
       • Indices: [0, 2], Stability: min(1, 3) * (1 + 2) = 3
       • Indices: [1, 2], Stability: min(1, 3) * (2 + 2) = 4
       • Indices: [0, 1, 2], Stability: min(1, 1, 3) * (1 + 2 + 2) = 5
     • So answer is maximum stability for the set of index {2}, answer = 6 % 1000000007 = 6.

Candidate's Approach: