Amazon Interview Question
Software Engineer / DevelopersRemoval is basically a substring search operation. Use the Knuth Morris Pratt Algorithm O(n) or Boyer Moore O(n/m)
void stringRemove (char * str1, char * toRemove)
{
//put the in array
int a[256], index =0;
for (int i=0; i<255; i++)
a[i]=0;
for (int i=0; i<strlen(toRemove); i++)
a[toRemove[i]]=1;
for (int i=0; i<strlen(str1); i++)
{
if ( a[str1[i]] == 1) // to remove
continue;
else
str1[index++] = str1[i];
}
str1[index] = '\0';
}
std::string removechars(std::string one, std::string two){
int hashtable[26];
memset(hashtable,0,26*sizeof(int));
transform(one.begin(), one.end(), one.begin(), tolower);
int i=0;
while(i<one.length()){
hashtable[static_cast<int> (one[i])-97]++;
i++;
}
i=0;
transform(two.begin(), two.end(), two.begin(), tolower);
while(i<two.length()){
if(hashtable[static_cast<int> (two[i])-97]>0)
two.erase(i,1);
i++;
}
return two;
}
The idea is to use a unordered_set in c++ and remove all the characters which are present in the set.
Implemenation:
#include<bits/stdc++.h>
using namespace std;
void removecharacters(string str1, string str2){
unordered_set<char> s;
for(int i = 0; i < str2.length(); i++)
s.insert(str2[i]);
string st = "";
for(int i = 0; i < str1.length(); i++){
if(s.find(str1[i]) == s.end())
st += str1[i];
}
cout<<st<<endl;
}
int main()
{
char str[] = "geeksforgeeks";
char mask_str[] = "mask";
removecharacters(str, mask_str);
return 0;
}
If string1 is quite large and string2 is also big then this is one of the good solutions:
int charArr[257];
void PopulateArray(char* pszStr)
{
if(pszStr == NULL)
return;
char *ptr = pszStr;
::memset(charArr,0,(sizeof(charArr)/sizeof(charArr[0])));
while(*ptr)
{
charArr[*ptr] = 1;
ptr++;
}
}
char* DeleteChar(char *str1, char* str2)
{
char* szOp = new char [strlen(str1)+1];
char* ptr = str1;
char* ptr2 = szOp;
::memset(szOp,0,(sizeof(szOp)/sizeof(szOp[0])));
while(*ptr)
{
if(charArr[*ptr])
ptr++;
else
{
*ptr2++ = *ptr++;
}
}
return szOp;
}
int _tmain(int argc, _TCHAR* argv[])
{
char arr[]= "today is Monday";
char arr2[] = "om";
PopulateArray(arr2);
printf("the output is %s",DeleteChar(arr,arr2));
return 0;
}
The answer is pretty simple ONE_LINE code in python. Assuming we're given the two strings namely str1 and str2 and we want to remove all the chars of str1 from str2, this is the way:
NB: Its not asked to write the code in C/C++/Java etc so we can use python
- Reema August 31, 2009