Trilogy Interview Question for Software Engineer / Developers


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);
    }
}

- Matt October 29, 2014 | Flag Reply
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);
	}
}

- Rost October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try your solution on this:
Target word: A B C D E
Start word : E A C D B

Your solution:
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.

- Darius Miloslav October 30, 2014 | Flag
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.

- Darius Miloslav October 30, 2014 | Flag Reply
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[0]==str2[0]?0:1) ;

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

- Anonymous October 30, 2014 | Flag Reply
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.

- Martin October 30, 2014 | Flag Reply
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;
            }
        }
    }
}

- Anonymous November 03, 2014 | Flag Reply
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.

- anroopak October 29, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More