## Amazon Interview Question

• 2

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

label each character in s2 with1 to n,
s2: bcdae
n2:12345
convert s1 to a array of number according to the labels,
s1: abcde
n1: 41235

the next is to sort 41235 using bubble sort （冒泡排序）:
41235
14235
12435
12345

Comment hidden because of low score. Click to expand.
0

@Mark Tang: will it give minimum number of steps?

Comment hidden because of low score. Click to expand.
0
of 0 vote

It still seems like a simple BFS where you only check possible cases (adjacent swaps only)

Comment hidden because of low score. Click to expand.
0

@anonymous: would you mind explaining how BFS would work here. Ideally BFS should work as we just need to transition from a to b state but how it will fit in here is a bit of concern.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>

void convertString(std::string& str1, std::string& str2) {
if (str1.empty() || str2.empty()) {
std::cout << "Empty String Input" << std::endl;
return;
}

if (str1.size() != str2.size()) {
std::cout << "Unequal String Size in Input" << std::endl;
return;
}

if (str1.compare(str2) == 0) {
std::cout << "Equal String in Input" << std::endl;
return;
}

std::string workStr1(str1);

for (int i=0; i<str2.size(); i++) {
int j=i;
while ((j < workStr1.size()) && (workStr1[j] != str2[i]))
++j;

std::cout << "j = " << j << " i = " << i << std::endl;

if (i ==j)
continue;

for (int k=j; k>i; k--) {
char c = workStr1.at(k);
workStr1.at(k) = workStr1.at(k-1);
workStr1.at(k-1) = c;

std::cout << workStr1 << std::endl;
}
}
}

int main() {
std::string str1("abcdea");
std::string str2("deaabc");

convertString(str1, str2);
}``````

Comment hidden because of low score. Click to expand.
0
of 6 vote

Java:

``````transpose("abcde".toCharArray(), "bcdae".toCharArray());

public static void transpose(char[] s1, char[] s2) {
int i = 0;
System.out.println(Arrays.toString(s1));
System.out.println(Arrays.toString(s2) + "\n");
while (i < s2.length) {
if (s2[i] == s1[i]) {
i++;
System.out.println(Arrays.toString(s1));
} else {
int j = i;
while (j < s1.length - 1 && s2[i] != s1[i]) {
char temp = s1[j];
s1[j] = s1[j + 1];
s1[j + 1] = temp;
j++;
}
}
}
System.out.println("\n" + Arrays.toString(s1));
System.out.println(Arrays.toString(s2));
}``````

You can also use .charAt() if you want to save some space but I think it's not the key in this question.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@thelineofcode: first of all what is the logic here? Second: will your algo gives you the minimum number of steps?

Comment hidden because of low score. Click to expand.
0

I think the algorithm here is that for an index i, if you position the desired char by swapping once with it's successor, then fine, proceed to the next char or else keep swapping until the character that was initially in the index i goes to the end of the string by swapping in the inner while loop. repeat this pushing to end, until that pushing unmatched chars to the end results in desired char automatically being pulled into position. Does that make sense? If it doesn't then what I'd do is, run this program with sample input and study each step to see what's happening.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private void transpose(String source, String destination) {

if(source.length() != destination.length()) {
return;
}
for(int i=0;i< source.length()-1;i++) {
char a= source.charAt(i);
char b = source.charAt(i+1);
if(checkCharOrder(a , b, destination)) {
}
if(source.equals(destination)) {
System.out.println("Strings match now " + source +  " "+ destination );
return;
}
}
}

private String swapAdjacent(int i, int j, String source) {
StringBuilder string = new StringBuilder(source);
char temp = source.charAt(i);
string.setCharAt(i, source.charAt(i+1));
string.setCharAt(i+1, temp);
System.out.println(string.toString());
return string.toString();
}

private boolean checkCharOrder(char a, char b, String destination) {
int indexOfA = destination.indexOf(a);
int indexOfB = destination.indexOf(b);
return ( indexOfA > indexOfB);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void swap(char *s,char *t)
{
char temp=*s;
*s=*t;
*t=temp;
}

void transpose(char s1[],char s2[])
{
int i=0,j=0,index=0;
printf("%s\t",s1);
while((s1[i]==s2[i]) && i<strlen(s2))
i++;
while(i<strlen(s2))
{
if(s1[i]==s2[i])
{
i++;
while((s1[i]==s2[i]) && i<strlen(s2))
i++;
}
else
{
j=i;
while(s1[i]!=s2[i] && j<strlen(s1)-1)
{
swap(&s1[j],&s1[j+1]);
printf("%s\t",s1);
j++;
}
}
}
printf("\n");``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SwapLikeAnagram {

public static void swapAnagram(String str) {

for (int i = 0; i < str.length(); i++) {
str = charValues(str, i);
}
}

public static String charValues(String str, int i) {
String newString = "";
char[] ch = str.toCharArray();
if (i < str.length() - 1) {
char ch1 = ch[i];
ch[i] = ch[i + 1];
ch[i + 1] = ch1;

for (Character ch5 : ch) {
System.out.print(ch5);
newString += ch5;
}
System.out.println();
}
return newString;
}

public static void main(String[] args) {

String str = "abcde";

swapAnagram(str);

}

}``````

Comment hidden because of low score. Click to expand.
0

Output-
bacde
bcdae
bcdea

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.