Epic Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
It is not exactly bubble sort. Here is implementation:
public static void main(String[] args) {
//char[] s1 = "eoksb".toCharArray();
//char[] s2 = "sboek".toCharArray();
char[] s1 = "TEHUNOOL".toCharArray();
char[] s2 = "ONLEHTUO".toCharArray();
transpose(s1, s2);
}
public static void transpose(char[] s1, char[] s2) {
int i = 0;
while (i < s2.length) {
if (s2[i] == s1[i]) {
i++;
continue;
} else {
for (int j = i; j < s1.length - 1; j++) {
char temp = s1[j];
s1[j] = s1[j + 1];
s1[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(s1));
System.out.println(Arrays.toString(s2));
}
#include <stdio.h>
int main()
{
char s2[] = "abcdef";
char s1[] = "dfebac";
int i=0;
int len2 = strlen(s2);
int len1 = strlen(s1);
while(i < len2)
{
if (s1[i] == s2[i])
i++;
else
{
/*send the character at the end of the first string */
for (int j=i; j < len1-1; j++)
{
int tmp = s1[j];
s1[j] = s1[j+1];
s1[j+1] = tmp;
}
}
}
printf(" %s %s", s1, s2);
}
Toughy, the only way I can think to do this one is to do a Breadth First Search (BFS) on all the possible swaps of string A, and look for the optimal number of swaps that will transpose A to B.
Then do the swaps :)
#include<stdio.h>
#include<string.h>
char str1[] = "abcde";
char str2[] = "edcab";
int count=0;
int swap(int i){
char temp = str1[i];
str1[i]=str1[i+1];
str1[i+1]=temp;
}
void transpose(int n){
int i;
for(i=n-1; i>=count; i--){
swap(i);
printf("%s\n",str1);
}
}
int main(){
int i,j;
for(i=0; i<strlen(str2); i++){
for(j=count; j<strlen(str1); j++){
if(str2[i]==str1[j]){
transpose(j);
count++;
}
}
}
return 0;
}
This is a valid solution given that the intermediate strings do not need to be valid words.
#include<stdio.h>
#include<string.h>
char str1[] = "abcde";
char str2[] = "edcab";
int count=0;
int swap(int i){
char temp = str1[i];
str1[i]=str1[i+1];
str1[i+1]=temp;
}
void transpose(int n){
int i;
for(i=n-1; i>=count; i--){
swap(i);
printf("%s\n",str1);
}
}
int main(){
int i,j;
for(i=0; i<strlen(str2); i++){
for(j=count; j<strlen(str1); j++){
if(str2[i]==str1[j]){
transpose(j);
count++;
}
}
}
return 0;
}
#include<stdio.h>
#include<string.h>
char str1[] = "abcde";
char str2[] = "edcab";
int count=0;
int swap(int i){
char temp = str1[i];
str1[i]=str1[i+1];
str1[i+1]=temp;
}
void transpose(int n){
int i;
for(i=n-1; i>=count; i--){
swap(i);
printf("%s\n",str1);
}
}
int main(){
int i,j;
for(i=0; i<strlen(str2); i++){
for(j=count; j<strlen(str1); j++){
if(str2[i]==str1[j]){
transpose(j);
count++;
}
}
}
return 0;
}
public static string Transpose(string input)
{
char[] str = input.ToCharArray();
for (int i = 0; i < input.Length - 1; i++)
{
for (int k = 0; k < input.Length - 1 - i; k++)
{
if (str[k] != str[k + 1])
{
char temp;
temp = str[k];
str[k] = str[k + 1];
str[k + 1] = temp;
}
}
}
return new string(str);
}
package programs;
import java.util.Scanner;
import java.util.HashMap;
public class program8 {
public static void swap(int[]x,int i,int j)
{
int temp = x[i];
x[i] = x[j];
x[j] = temp;
}
public static void swap(char[]x,int i,int j)
{
char temp = x[i];
x[i] = x[j];
x[j] = temp;
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String source,destination;
System.out.println("Enter the source string: ");
source = (in.next().toString()).toLowerCase();
System.out.println("Enter the destination string: ");
destination = (in.next().toString()).toLowerCase();
System.out.println("Source= "+source+" Destination= "+destination);
char [] s = source.toCharArray();
char [] d = destination.toCharArray();
int [] dint = new int[d.length];
for(int i=0;i<d.length;i++)
{
dint[i]=256;
}
HashMap h1 = new HashMap();
//HashMap h2 = new HashMap();
for(int i=0;i<s.length;i++)
{
h1.put(i,s[i]);
//h2.put(s[i],i);
}
for(int i=0;i<d.length;i++)
{
for(int j=0;j<h1.size();j++)
{
if((Character)h1.get(j)==d[i] && dint[i]==256)
{
dint[i] = j;
}
}
}
System.out.println(new String(d));
for(int i=0;i<dint.length;i++)
{
for(int j=0;j<dint.length-i-1;j++)
{
if(new String(d).compareTo(new String(s))==0)
break;
else
{
if(dint[j]>dint[j+1])
{
swap(dint,j,j+1);
swap(d,j,j+1);
System.out.println(new String(d));
}
}
}
}
}
}
import java.util.Arrays;
public class Transpose {
public static void transpose(char[] source, char[] destination) {
// detect whether two array could be transposed to the other
char[] src_copy = new char[source.length];
char[] dest_copy = new char[destination.length];
int i = 0;
for (char n : source) {
src_copy[i++] = n;
}
i = 0;
for (char n : destination) {
dest_copy[i++] = n;
}
Arrays.sort(src_copy);
Arrays.sort(dest_copy);
if (!Arrays.equals(src_copy, dest_copy)) {
System.out.println("Couldn't transpose!");
return;
}
for (i = 0; i < source.length; i++) {
if (source[i] == destination[i]) {
continue;
} else {
change(source, i, destination[i]);
}
}
}
private static void change(char[] source, int i, char target) {
int index;
for (index = i; i < source.length; index++) {
if (target == source[index]) {
break;
}
}
swap_helper(source, i, index);
}
private static void swap_helper(char[] source, int start, int end) {
for (int index = end; index > start; index--) {
char tmp = source[index - 1];
source[index - 1] = source[index];
source[index] = tmp;
}
}
public static void main(String[] args) {
char[] src = {'a','f','d','c','e','b'};
char[] dest = {'a','b','c','d','e','f'};
transpose(src,dest);
System.out.println(src);
}
}
import java.util.Arrays;
public class swapTwoString {
public static void main(String[] args) {
String input="dcraeb";
String des="abcde";
StringBuffer output=swap(input,des);
System.out.print(output);
}
private static StringBuffer swap(String input, String des) {
char[] tempin=input.toCharArray();
char[] tempde=des.toCharArray();
StringBuffer o=new StringBuffer();
Arrays.sort(tempin);
Arrays.sort(tempde);
if(!Arrays.equals(tempin,tempde)){
System.out.println("they can not be swaped!");}else{
o=change(input, des);}
return o;
}
private static StringBuffer change(String input, String des) {
char[] in=input.toCharArray();
char[] de=des.toCharArray();
for(int i =0;i<in.length;i++){
if(in[i]!=de[i]){
char value=de[i];
for(int j=i;j<de.length;j++){
if( in[j]==value){
char temp;
temp=in[i];
in[i]=value;
in[j]=temp;
}
}
}
}
StringBuffer sb=new StringBuffer();
for(char i:in){
sb.append(i);
}
return sb;
}
}
import java.util.Arrays;
public class Transpose {
public static void transpose(char[] source, char[] destination) {
// detect whether two array could be transposed to the other
char[] src_copy = new char[source.length];
char[] dest_copy = new char[destination.length];
int i = 0;
for (char n : source) {
src_copy[i++] = n;
}
i = 0;
for (char n : destination) {
dest_copy[i++] = n;
}
Arrays.sort(src_copy);
Arrays.sort(dest_copy);
if (!Arrays.equals(src_copy, dest_copy)) {
System.out.println("Couldn't transpose!");
return;
}
for (i = 0; i < source.length; i++) {
if (source[i] == destination[i]) {
continue;
} else {
change(source, i, destination[i]);
}
}
}
private static void change(char[] source, int i, char target) {
int index;
for (index = i; i < source.length; index++) {
if (target == source[index]) {
break;
}
}
swap_helper(source, i, index);
}
private static void swap_helper(char[] source, int start, int end) {
for (int index = end; index > start; index--) {
char tmp = source[index - 1];
source[index - 1] = source[index];
source[index] = tmp;
}
}
public static void main(String[] args) {
char[] src = {'a','f','d','c','e','b'};
char[] dest = {'a','b','c','d','e','f'};
transpose(src,dest);
System.out.println(src);
}
}
#include<stdio.h>
#include<string.h>
#include<conio.h>
void main()
{
char str1[10], str2[10],temp[10];
int i,n;
printf("\n Enter the string.");
scanf("%s",str1);
n=strlen(str1);
strcpy(temp,str1);
strcpy(str2,strrev(temp));
while(strcmp(str1,str2)!=0)
{
for(i=0;i<n-1;i++)
{
temp[i]=str1[i];
str1[i]=str1[i+1];
str1[i+1]=temp[i];
printf("\n %s",str1);
}
n--;
}
printf("\n Final reveresed string is %s",str1);
getch();
}
this is in c#
namespace CnsTransposeCSharp
{
class Program
{
static void Main(string[] args)
{
// on these, it took 36 iterations
//string s1= "abcde";
//string s2= "edcab";
// on these, it took about 106 iterations
//string s1 = "TEHUNOOL";
//string s2 = "ONLEHTUO";
string s1 = Console.ReadLine();
string s2 = Console.ReadLine();
char[] charAr1 = s1.ToCharArray();
char[] charAr2 = s2.ToCharArray();
int i=0;
int len1 = s1.Length;
int len2 = s2.Length;
int iter = 0;
if (len1 != len2)
Console.WriteLine("Cannot Transpose strings: {0}, {1}", s1, s2);
else
{
while (i < len2)
{
if (charAr1[i] == charAr2[i])
{
i++;
iter++;
}
{
/*send the character at the end of the first string */
for (int j = i; j < len1 - 1; j++)
{
char tmp = charAr1[j];
charAr1[j] = charAr1[j + 1];
charAr1[j + 1] = tmp;
iter++;
}
}
}
string s1a = new string(charAr1);
Console.WriteLine(" {0}, {1}", s1a, s2);
Console.WriteLine("# of interation: {0}", iter);
} //else
}
}
}
this is in c#
namespace CnsTransposeCSharp
{
class Program
{
static void Main(string[] args)
{
// on these, it took 36 iterations
//string s1= "abcde";
//string s2= "edcab";
// on these, it took about 106 iterations
//string s1 = "TEHUNOOL";
//string s2 = "ONLEHTUO";
string s1 = Console.ReadLine();
string s2 = Console.ReadLine();
char[] charAr1 = s1.ToCharArray();
char[] charAr2 = s2.ToCharArray();
int i=0;
int len1 = s1.Length;
int len2 = s2.Length;
int iter = 0;
if (len1 != len2)
Console.WriteLine("Cannot Transpose strings: {0}, {1}", s1, s2);
else
{
while (i < len2)
{
if (charAr1[i] == charAr2[i])
{
i++;
iter++;
}
{
/*send the character at the end of the first string */
for (int j = i; j < len1 - 1; j++)
{
char tmp = charAr1[j];
charAr1[j] = charAr1[j + 1];
charAr1[j + 1] = tmp;
iter++;
}
}
}
string s1a = new string(charAr1);
Console.WriteLine(" {0}, {1}", s1a, s2);
Console.WriteLine("# of interation: {0}", iter);
} //else
}
}
}
using a slightly different, gives the correct results
public class Transpose {
public static void main(String[] args) {
char[] s1 = "TEHUNOOL".toCharArray();
char[] s2 = "ONLEHTUO".toCharArray();
transpose(s1,s2);
}
static void transpose(char[] s1, char[] s2) {
int i = 0;
while (i < s1.length) {
if (s2[i] == s1[i]) {
i++;
continue;
} else {
int j = i+1;
while (j < s2.length && s2[j] != s1[i]) {
j++;
}
while(j>i) {
char temp=s2[j-1];
s2[j-1]=s2[j];
s2[j]=temp;
j--;
}
}
}
for(int k=0;k<s2.length;k++)
System.out.print(s2[k]);
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int count=0;
char s1[100],s2[100];
void swap(int n)
{
char temp;
for(int i=n-1;i>=count;i--)
{
temp=s1[i+1];
s1[i+1]=s1[i];
s1[i]=temp;
printf("%s\n",s1);
}
}
void solve()
{
for(int i=0;i<strlen(s2);i++)
for(int j=0;j<strlen(s1)&&i<strlen(s2);j++)
{
if(s1[j]==s2[i])
{
swap(j);
count++;
i++;
}
}
}
int main()
{
scanf("%s%s",s1,s2);
printf("%s\n",s1);
solve();
return 0;
}
/* Start ----------------------------------- [3] */
public static String transpose(Char[] s1, Char[] s2)
{
String Output = "";
Int32 i, j;
for (i = 0; i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
for (j = i; j < s1.Length; j++)
{
if (s1[j] == s2[i])
{
//Swap
Char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
Console.WriteLine("Swapping : " + i + ", " + j);
break;
}
}
}
}
return Output;
}
public static void transposeInvoker()
{
char[] s1 = "TEHUNOOL".ToCharArray();
char[] s2 = "ONLEHTUO".ToCharArray();
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
transpose(s1, s2);
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
}
/* End of ---------------------------------- [3] */
public static String transpose(Char[] s1, Char[] s2)
{
String Output = "";
Int32 i, j;
for (i = 0; i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
for (j = i; j < s1.Length; j++)
{
if (s1[j] == s2[i])
{
Char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
break;
}
}
}
}
return Output;
}
public static void transposeInvoker()
{
char[] s1 = "TEHUNOOL".ToCharArray();
char[] s2 = "ONLEHTUO".ToCharArray();
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
transpose(s1, s2);
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
}
/* Start ----------------------------------- [3] */
public static String transpose(Char[] s1, Char[] s2)
{
String Output = "";
Int32 i, j;
for (i = 0; i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
for (j = i; j < s1.Length; j++)
{
if (s1[j] == s2[i])
{
//Swap
Char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
Console.WriteLine("Swapping : " + i + ", " + j);
break;
}
}
}
}
return Output;
}
public static void transposeInvoker()
{
char[] s1 = "TEHUNOOL".ToCharArray();
char[] s2 = "ONLEHTUO".ToCharArray();
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
transpose(s1, s2);
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
}
/* End of ---------------------------------- [3] */
and
/* Start ----------------------------------- [3] */
public static String transpose(Char[] s1, Char[] s2)
{
String Output = "";
Int32 i, j;
for (i = 0; i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
for (j = i; j < s1.Length; j++)
{
if (s1[j] == s2[i])
{
//Swap
Char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
Console.WriteLine("Swapping : " + i + ", " + j);
break;
}
}
}
}
return Output;
}
public static void transposeInvoker()
{
char[] s1 = "TEHUNOOL".ToCharArray();
char[] s2 = "ONLEHTUO".ToCharArray();
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
transpose(s1, s2);
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
}
/* End of ---------------------------------- [3] */
and
/* Start ----------------------------------- [3] */
public static String transpose(Char[] s1, Char[] s2)
{
String Output = "";
Int32 i, j;
for (i = 0; i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
for (j = i; j < s1.Length; j++)
{
if (s1[j] == s2[i])
{
//Swap
Char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
Console.WriteLine("Swapping : " + i + ", " + j);
break;
}
}
}
}
return Output;
}
public static void transposeInvoker()
{
char[] s1 = "TEHUNOOL".ToCharArray();
char[] s2 = "ONLEHTUO".ToCharArray();
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
transpose(s1, s2);
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
}
/* End of ---------------------------------- [3] */
/* Start ----------------------------------- [3] */
public static String transpose(Char[] s1, Char[] s2)
{
String Output = "";
Int32 i, j;
for (i = 0; i < s2.Length; i++)
{
if (s1[i] != s2[i])
{
for (j = i; j < s1.Length; j++)
{
if (s1[j] == s2[i])
{
//Swap
Char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
Console.WriteLine("Swapping : " + i + ", " + j);
break;
}
}
}
}
return Output;
}
public static void transposeInvoker()
{
char[] s1 = "TEHUNOOL".ToCharArray();
char[] s2 = "ONLEHTUO".ToCharArray();
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
transpose(s1, s2);
Console.WriteLine("\n" + new String(s1) + "\n" + new String(s2));
}
/* End of ---------------------------------- [3] */
do bubblesort on the first string ( since bubble sort only swaps consecutive items).
- dead.rabbit March 11, 2012only difference than the regular one is that the comparison is be made by the positions of those characters in the second string.
Need some extra work for allowing multiple occurances of a character