Skip to content

Instantly share code, notes, and snippets.

@ajtazer

ajtazer/DatasetOrderOptimization.md

Created December 7, 2025 12:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ajtazer/b7ef7246673f0e404783a2eda488eb8a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ajtazer/b7ef7246673f0e404783a2eda488eb8a to your computer and use it in GitHub Desktop.
Download ZIP
AMAZON OA CODE SOLUTIONS | ALL TEST CASES PASSED
Raw
DatasetOrderOptimization.md

Amazon Robotics is optimizing the dataset shipment process.
You are given a binary string shipmentData consisting only of '0' and '1'.

Process Definition: Start with an empty finalSequence.

For each character c in shipmentData from left to right:

  1. Append c to finalSequence
  2. Reverse the entire finalSequence

This continues until all bits are processed.

Goal: Determine the best ordering of bits in shipmentData that produces the lexicographically largest possible finalSequence.

Return that optimal ordering of shipmentData.

Example: Input: 0100 Output: 0001

Function Signature: string getDatasetOrder(string shipmentData);

Constraints: 1 ≤ shipmentData.length() ≤ 10^5 Characters are only '0' and '1'

Raw
getDatasetOrder.cpp
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
/*
* Complete the 'getDatasetOrder' function below.
*
* The function is expected to return a STRING.
* The function accepts STRING shipmentData as parameter.
*/
string getDatasetOrder(string shipmentData) {
int n = shipmentData.size();
int ones = 0;
for (char c : shipmentData) {
if (c == '1') ones++;
}
vector<int> F(n);
int idx = 0;
if (n % 2 == 0) {
for (int v = n - 1; v >= 1; v -= 2) F[idx++] = v;
for (int v = 0; v < n; v += 2) F[idx++] = v;
} else {
for (int v = n - 1; v >= 0; v -= 2) F[idx++] = v;
for (int v = 1; v < n; v += 2) F[idx++] = v;
}
vector<int> inv(n);
for (int pos = 0; pos < n; ++pos) {
inv[F[pos]] = pos;
}
string result(n, '0');
for (int i = 0; i < n; ++i) {
if (inv[i] < ones) result[i] = '1';
else result[i] = '0';
}
return result;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string shipmentData;
getline(cin, shipmentData);
string result = getDatasetOrder(shipmentData);
fout << result << "\n";
fout.close();
return 0;
}
Raw
getMinimumOperations.cpp
#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
#include <string>
#include <vector>
using namespace std;
/*
* Complete the 'getMinimumOperations' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING strValue as parameter.
*/
int getMinimumOperations(string strValue) {
int n = (int)strValue.size();
string T = strValue;
sort(T.begin(), T.end());
if (strValue == T) return 0;
int L = 0;
while (L < n && strValue[L] == T[L]) ++L;
int R = n - 1;
while (R >= 0 && strValue[R] == T[R]) --R;
if (!(L == 0 && R == n - 1)) {
string seg = strValue.substr(L, R - L + 1);
sort(seg.begin(), seg.end());
if (seg == T.substr(L, R - L + 1)) return 1;
return 2;
}
char mx = *max_element(strValue.begin(), strValue.end());
char mn = *min_element(strValue.begin(), strValue.end());
if (strValue[0] == mx && strValue[n-1] == mn
&& count(strValue.begin(), strValue.end(), mx) == 1
&& count(strValue.begin(), strValue.end(), mn) == 1) {
return 3;
}
return 2;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string strValue;
getline(cin, strValue);
int result = getMinimumOperations(strValue);
fout << result << "\n";
fout.close();
return 0;
}
Raw
Sorting With Proper Substring Operations.md

You are given a string strValue containing lowercase English letters only (a–z).

Allowed Operation: Choose any proper substring (not the entire string)
and sort that substring in non-decreasing order.

Goal: Return the minimum number of such operations required to transform strValue into a fully sorted (non-decreasing) string.

Examples: Input: zyxpqa Output: 3

Input: xabx Output: 1

Input: abcde Output: 0

Function Signature: int getMinimumOperations(string strValue);

Constraints: 3 ≤ strValue.length() ≤ 10^5 All characters are lowercase English letters (a–z) Must run efficiently (O(n log n) or better)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment