Amazon Interview Question
Country: India
It still seems like a simple BFS where you only check possible cases (adjacent swaps only)
#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);
}
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.
@thelineofcode: first of all what is the logic here? Second: will your algo gives you the minimum number of steps?
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.
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)) {
source = swapAdjacent(i,i+1,source);
}
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);
}
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");
}
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);
}
}
label each character in s2 with1 to n,
- Mark Tang February 09, 2014s2: 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