Ebay Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




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

You need to build a graph with an edge connecting two words which can be transformed to each other.
Once, you build the graph, start from the starting words, check if the second word is connected to the first word. We can do a BFS if we want the shortest path as well.

- Chintamani May 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks good
Chintamani can you please elaborate your algo with a small example.
you can use a adjacency matrix to represent the graph.

- DashDash May 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep, that's good sol. Basically you have to construct the graph in a way that each world is connected with worlds which has only one latter different. Then do BFS or DFS.

- Anonymous July 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution to this question is present in Cracking The Coding Interviews fifth edition, in the last chapter. The solution does not require pre-processing step, so there is no need to create a graph of the dictionary words. Complexity is O(nm) where n = length of start word and m = length of end word.

- inheritance November 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved using recursion
Please let me know if I have messed up somewhere here.

void FromTo(char *source, char *dest, char **stackofWords, int wordCount)
{
if(strcomp(source, dest) == 0)
{
print(stackofWords, wordcount);
return;
}
else
{
for(int i=0;i<strlen(source);i++)
{
for(int j=0;j<26;j++)
{
if((char)((int)'A' + j) != source[i])
source[i] = (char)((int)'A' + j);
else
continue;
stackofwords[wordcount] = source;
Fromto(source, dest, stackofWords, wordcount+1);
}
}
}

}

Algo

I am changing every letter with all the alphabets in the english dictionary and then comparing with the desitnation.

- DashDash May 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

according to this algo we can replace the character, which is in dictionary but how we can know that if it is makes any meaningful word or not?

- seema May 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh yes I forgot to add that logic.
You can use with a simple check in the beginning to know. Use a trie for the dictionary.

- DashDash May 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You need backtracking mechanism in it..else some mechanism to stop algorithm to go all the way around..
Take an example :
pit , pat,bat, cat and so on..how to know whether you are moving in right direction or not...

- Munir Mehta May 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I hope this link may help you
tianrunhe . wordpress . com/2012/06/10/transform-one-word-into-another-by-changing-only-one-letter-at-a-time/
remove the spaces and add http

- rasmiranjanbabu May 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pit, pat, mat, map

- coding.arya May 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve by first creating graph which connects one word to another if only one letter difference. So after creation of this graph we can find two words and find the shortest path among them.
Here two way graph can be generated. If its one time work then we can create adhoc basis and find only words which are similar letters and draw graph..

else if its for longer term purpose we can draw graph for all the words in dictionary save it and at the time of finding we just need to find the shortest path. This may save a lot of time..

- Munir Mehta May 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can preprocess the dictionary and create this graph, should look like:

stack jack
| |
| |
smack back -- pack -- pick
You can then have a mapping from the word to the node representing the word, for this you can use a hash table, height balanced BST ...

Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS or DFS.

So you can summarize the algorithm as:

preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
Not possible to convert
else
n1 = get_node(w1)
n2 = get_node(w2)

if(path_exists(n1,n2))
Possible and nodes in the path represent intermediary words
else
Not possible

- Putta May 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sites.google.com/site/spaceofjameschen/home/graph/find-a-way-that-each-intermediate-words-exists-in-a-given-dictionary

- Anonymous May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution by a BFS.

void doPath( vector<string> &path, map<string,string> &M, string s) {
	if(s == "-")
		return;
	doPath(path, M, M[s]);
	path.push_back(s);
}

vector<string> find(string &orig, string &dest, HashTable dic) {
	queue<string> Q;
	map<string,string> M;
	
	Q.push(orig);
	M[orig] = "-";
	
	bool can = false;
	while(Q.empty() == false) {
		string top = Q.top();
		Q.pop();
		if(top == dest) {
			can = true;	
			break;
		}
		for (int i = 0; i < top.size(); i++) {
			for (char c = 'a'; c <= 'z'; c++) {
				string ss = top;
				top[i] = c;
				if(M.find(ss) == M.end()) {
					Q.push(ss);
					M[ss] = top;
				} 
			}
		}
	}
	
	vector<string> path;
	if(can == false)
		return path;
	return doPath(path, M, dest);
}

- thiago.xth1 May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isValid(String word)
  {
    Set<String> dict = new HashSet<String>();
    dict.add("cat");
    dict.add("car");
    dict.add("tar");
    dict.add("tor");
    dict.add("toy");
    if (dict.contains(word))
      return true;
    return false;
  }

  public static void main(String[] args)
  {
    System.out.println(minTransforms(Arrays.asList(0, 1, 2), "cat", 0, "toy"));
  }

  public static int minTransforms(List<Integer> indxes, String word, int len, String dest)
  {
    if (word.equals(dest))
      return len;
    int lenT = Integer.MAX_VALUE;
    for (int i=0;i<word.length();i++)
    {
      if(word.charAt(i)==dest.charAt(i))continue;
      List<String> words = generateWords(i, word);
      List<Integer> ind = new ArrayList<>(indxes);
      for (String word_new: words)
      {
        if (!word_new.equals(word) && isValid(word_new))
        {
          //ind.remove(indx);
          lenT = Math.min(minTransforms(ind, word_new, len + 1, dest), lenT);
        }
      }
    }
    return lenT;
  }

  public static List<String> generateWords(int indx, String word)
  {
    List<String> words = new ArrayList<String>();
    char chr[] = word.toCharArray();
    for (char a = 'a'; a <= 'z'; a++)
    {
      chr[indx] = a;
      String str = new String(chr);
      words.add(str);
    }
    return words;
  }

- Koustav Chattterjee June 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Write a program to compute if one string is a rotation of another. For example, pit is rotation of tip as pit has same character as tip.

- Anonymous August 30, 2016 | 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