## Trilogy Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Written Test

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

That won't get you the minimum number of moves, but the algorithmic approach of "bubble sort" isn't far off. For example, if you have:

ZYXA
ZYAX

Bubble sort would require: almost 2n^2 moves.

If your comparator function wasn't "alphabetical order" and instead matching string A, that should work.

Using String A as comparator. If a character in position i doesn't match (e.g. Ai != Bi) then swap.

``````public class TwoStringsMatching {

public static void main(String[] args) {
String A = "ZYXA";
String B = "ZYAX";

char[] aChar = A.toCharArray();
char[] bChar = B.toCharArray();
char temp;
System.out.println("A: " + String.valueOf(aChar));
System.out.println("B: " + String.valueOf(bChar));

int numMoves = 0;
int noSwaps = 0;
while(noSwaps != aChar.length-1) {
noSwaps = 0;
for (int i = 0; i < aChar.length-1; i++) { //currently ignore the last character
if (aChar[i] != bChar[i]) {
numMoves++;
temp = bChar[i];
bChar[i] = bChar[i+1];
bChar[i+1] = temp;
} else {
noSwaps++;
}
}
}
System.out.println("A: " + String.valueOf(aChar));
System.out.println("B: " + String.valueOf(bChar));
System.out.println("Number of swamps: " + numMoves);
}
}``````

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

``````public class MainTask {
public static int FindPos(char letter,char[] str) {
int retPos=0;
for(int i=0;i<=str.length-1;i++){
if(str[i]==letter){
retPos=i;
break;
}
}
return(retPos);
}
public static char[] MoveRight(char[] str,int pos,int npos)
{
char[] retArray;
char chTemp;
retArray=str.clone();
for(int i=pos;i<npos;i=i+1){
chTemp=retArray[i];
retArray[i]=retArray[i+1];
retArray[i+1]=chTemp;
}
return(retArray);
}
public static char[] MoveLeft(char[] str,int pos,int npos)
{
char[] retArray;
char chTemp;
retArray=str.clone();
for(int i=pos;i>npos;i=i-1){
chTemp=retArray[i];
retArray[i]=retArray[i-1];
retArray[i-1]=chTemp;
}
return(retArray);
}
public static void main(String[] args) {
String A = "NUMBERS";
String B = "ERUNMBS";
System.out.println("started");
char[] aChar = A.toCharArray();
char[] bChar = B.toCharArray();
System.out.println("A: " + String.valueOf(aChar));
System.out.println("B: " + String.valueOf(bChar));
int numMoves = 0;
int numPos=0;
for(int i=0;i<=aChar.length-1;i++)
{
if(aChar[i]!=bChar[i]){
numPos=FindPos(aChar[i],bChar);
if(numPos<i){
bChar=MoveRight(bChar,numPos,i);
}
if(numPos>i){
bChar=MoveLeft(bChar,numPos,i);
}
numMoves=numMoves+(numPos);
}
}
System.out.println("-----------------------------");
System.out.println("A: " + String.valueOf(aChar));
System.out.println("B: " + String.valueOf(bChar));
System.out.println("Number of swaps: " + numMoves);
}
}``````

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

Target word: A B C D E
Start word : E A C D B

Step1: A E C D B
Step2: A C E D B
Step3: A C D E B
Step4: A C D B E
then onwards....

Correct solution:
Step1: B A C D E
Step2: A B C D E

This solution was crafted in USA.

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

*** I am the miloslav. This solution is made in america ****

Step1: Take one word and call it source. Take the other and call is destination. initialize variable totalsteps = 0
Step2: Take the source and compute, for each letter, the swap distance between the letter in its current position and the letter in its correct target position. Don't forget about the wrap around.
Source: C D A B
Target: A B C D
Step 3: Define a badness metric which is the sum of swap distances for all letters of the given word. If badness metric is 0, you're done. Consider all possible single swaps for the given word, and compute the badness metric of these derivative words.
Source C(2) D (2) A(2) B(2) --> total edit distance is 8
Options to transition to: C (2) D(2) B(1) A(1), D (1) C(1) A(2) B(2), ......etc
Step4: If there exists a derivative word that has a badness metric that is less than the badness metric of the source, find the derivative word with the lowest badness metric and make it the new source and go to step 1. Flush the temporary cache (described below) and Increment total steps.

If there does not exist a derivative word that has a badness metric less than the badness metric of the source, there will always exist a word with the badness metric which is equal to the badness metric of the source. In this case, remember the source in a temporary cache, and choose a new source which we have not already visited (i.e., is not there in the temporary cache). Now go to step 1.

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

``````{
static void Main(string[] args)
{
string str1 = "A B C D E";

string str2 = "E A C D B";

Console.WriteLine(PrintMinSteps(str1, str2));

}

public static int PrintMinSteps(string str1, string str2)
{
if (str1 == str2)
return 0;

if (str1.Length == 0)
return str2.Length;

if (str2.Length == 0)
return str1.Length;

int len1 = PrintMinSteps(str1.Substring(1), str2) + 1;
int len2 = PrintMinSteps(str1, str2.Substring(1)) + 1;
int len3 = PrintMinSteps(str1.Substring(1), str2.Substring(1)) + (str1==str2?0:1) ;

return Math.Min(len1, Math.Min(len2, len3));
}
}``````

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

Scan both strings from left to right, let n be the index.

When you find a mismatch, then either A[n] char or B[n] must be replaced by the corresponding character in the other string. Find the nearest matching character to the right of n (either the nearest in A[n+1..] which matches B[n] or the nearest in B[n+1..] which matches A[n]). Move this character into the right place and continue.

For the first character, you can start searching from the end of the string, but once you have started matching characters then I cannot see how to use the "swap first and last characters" function to improve the result.

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

Here is my bubblesort-ish algo- O(n^2) :(

``````void makeSame(const std::string& orig, std::string& copy)
{
const int numLetters = orig.size();
for(int i = 0; i < numLetters; i++)
{
int iterIdx = i;

while(copy.at(i) != orig.at(i))
{
if((iterIdx + 1) < numLetters)
{
char& oldChar = copy.at(iterIdx);
iterIdx++;
char& newChar = copy.at(iterIdx);

char tmpChar = oldChar;
oldChar = newChar;
newChar = tmpChar;
}
else
{
// start swapping again
iterIdx = i;
}
}
}
}``````

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

Simply, we can use Bubble Sort technique, which swaps consecutive items.
In such a way, we have to sort both the strings, then it will be equal.

I think, this is the most simple and automated algorithm.

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.