TP Interview Question
SDE1sCountry: United States
@ 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
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;
}
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.
- overload119 May 13, 2013