TP Interview Question for SDE1s


Country: United States




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

I'm not entirely sure of the question, in particular, what qualifies as strings to be "swapped" with each other?

Here is an algorithm that finds the largest set of strings based on their length, and it resolves the test case you provided.

var arr = ['mat', 'rat', 'groom', 'broom', 'cat'];

function getSwappable(arr) {
  var wordLengths = {};
  for (var i = 0; i < arr.length; i++) {
    var word = arr[i];
    var key = word.length;
    if (wordLengths[key]) {
      wordLengths[key].push( word );
    } else {
      wordLengths[key] = [ word ];
    }
  }

  var maxKey = 0;
  var maxResult = [];
  for (var key in wordLengths) {
    if (wordLengths[key].length > maxKey) {
      maxKey = wordLengths[key].length;
      maxResult = wordLengths[key];
    }
  }

  return maxResult;
}

getSwappable(arr);

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

@ EK MACHCHAR
Assuming the definition of words likely to be swapped to be words with maximum of one letter difference, I give the below algorithm. Let me know if I have missed anything.

1) Define a method isSwappable, which accepts two words, counts the number of letters in both the words and returns true if both of the words have a maximum of one letter

This can be done by maintaining a hash (array of size 26) to keep track of the count of each letter in the word.

2) Make the calls to the isSwappable method from inside of a nested loop

This compares the current word from the list to rest of the list

3) Maintain a pointer currentInsertion (by default, this points to currentPosition + 1). If two words are swappable, swap the jth element with currentInsertion and increment currentInsertion. Continue next iteration where i equals currentInsertion with rest of the list.

for (int i = 0; i < list.length; i = currentInsertion){
	for (int j = i+1; j < list.length; j++) {
		if (isSwappable(list[i], list[j]) {
			temp = list[j];
			list[j] = list[currentInsertion];
			list[currentInsertion]  = temp;
			currentInsertion++;
		}
	}
}

4) While grouping swappable elements, keep track of the following

a) count of elements in current swappable group
b) count of elements in max swappable group and
c) starting index of swappable group with largest count.

If current count is greater than max count, replace max count with current count and assign starting index of current group to corresponding pointer.

5) Print count of elements in largest swappable group from its starting index

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

The following code finds minimum distance between the strings. I think this can be used for the likeliness. The lesser the value the more likely being swapped. If it is zero then the strings both are same, highest likeliness.
The code also takes care of case difference, by converting the strings to lower case.

class testString:public string
{
public:
	testString():string(){}
	testString(string& s):string(s){}
	testString(char *s):string(s){}
	int difference(testString& s)
	{
		int diff = 0;
		int pos = 0;
		int i;
		if(length() == s.length())
		{
			for(i=0;i<length();i++)
				diff += (abs(at(i)-s.at(i))?1:0);
			return diff;
		}
		
		if(length()>s.length())
		{
			int* diffArr = new int[length()-s.length()+1];
			int j;
			for(j=0;j<length()-s.length()+1;j++)
			{
				diff = 0;
				for(i=0;i<s.length();i++)
					diff += (abs(at(i+j)-s.at(i))?1:0);
				diffArr[j] = diff;
			}
			diff = s.length();
			for(j=0;j<length()-s.length()+1;j++)
			{
				if(diff>diffArr[j])
					diff = diffArr[j];
			}
			diff = length()-s.length()+diff;
			return diff;
		}
		if(length()<s.length())
		{
			int* diffArr = new int[-length()+s.length()+1];
			int j;
			for(j=0;j<-length()+s.length()+1;j++)
			{
				diff = 0;
				for(i=0;i<length();i++)
					diff += (abs(at(i+j)-s.at(i))?1:0);
				diffArr[j] = diff;
			}
			diff = length();
			for(j=0;j<(int)(-length()+s.length()+1);j++)
			{
				if(diff>diffArr[j])
					diff = diffArr[j];
			}
			diff = -length()+s.length()+diff;
			return diff;
		}
	}
};
void dist(testString& s,testString &t)
{
	int i;
	for(i=0;i<s.length();i++)
	{
		if(s.at(i) >= 'A' && s.at(i) <= 'Z')
		s.at(i) = s.at(i)+'a'-'A';
	}
	for(i=0;i<t.length();i++)
	{
		if(t.at(i) >= 'A' && t.at(i) <= 'Z')
		t.at(i) = t.at(i)+'a'-'A';
	}
	cout<<"input\t"<<s<<"\t"<<t<<endl;
	cout<<s.difference(t)<<endl;
}

- dadakhalandhar May 14, 2013 | 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