Panda Guru LogoPanda
Guru
Panda Guru LogoPanda
Guru

Amazon OA question

10/10/2024
Open in leetcode

Round 1

Questions: You are given a binary string, binary, consisting only of characters '0' and '1'. You are allowed to perform the following operation zero or more times:

  1. Choose any subsequence of binary.
  2. Sort this subsequence.
  3. Replace the chosen subsequence in binary with its sorted version.

Additionally, you are given an array arr of length n, where each element of arr is a string of the same length as binary. Each string in arr consists of characters '0', '1', and the wildcard character '?'. The '?' character can be replaced with either '0' or '1' arbitrarily.

For each string in arr, after replacing every '?' character with either '0' or '1', you need to determine whether it is possible to rearrange the binary string into the modified string using the sorting operation described above. If it is possible, store "YES" as the corresponding answer; otherwise, store "NO".

Example:

Consider the binary string binary = "101100" and the array arr = ["?110?1", "111???"].

  1. For arr[0] = "?110?1", you can replace the '?' characters to form the string "011001". It is possible to rearrange the binary string into "011001" using the sorting operations:

    • Choose the subsequence {0, 2}, and sorting it transforms binary to "011100".
    • Choose the subsequence {3, 4, 5}, and sorting it transforms binary to "011001". The answer for this element is "YES".

  2. For arr[1] = "111???", no valid replacement of '?' characters allows the binary string to be rearranged to match the resulting string. Therefore, the answer is "NO".

Thus, the output for this case would be ["YES", "NO"].

Candidate's Approach

To solve this problem, we can follow these steps:

  1. Count the number of '0's and '1's in the binary string.
  2. For each string in arr, replace '?' with both '0' and '1' to check all possible combinations.
  3. For each modified string, count the number of '0's and '1's.
  4. Compare the counts with those from the binary string to determine if rearrangement is possible.
  5. If the counts match, store "YES"; otherwise, store "NO".

Challenges include efficiently handling the '?' replacements and ensuring all combinations are checked without excessive computation.

Interviewer's Feedback

No feedback provided.