Bloomberg LP Interview Question Software Engineer / Developers
Removed the redundant loop..
void chareq(char *s1, char *s2)
{
int alph[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
int n1=0,n2=0;
int i;
for(i=0;i<strlen(s1);++i)
{
if(s1[i]==s2[i]) ++n1;
else ++alph[s1[i]-'a'];
}
for(i=0;i<strlen(s2);++i)
{
if(alph[s2[i]-'a']!=0 ){ --alph[s2[i]-'a'];++n2;}
}
printf("%d %d\n",n1,n2);
}
Hi,
I know a modern 'smart' compiler would automatically avoid this problem, but for an interview it may matter.
for(i=0;i<strlen(s1);++i)
strlen takes O(n)
The for loop also takes O(n)
If strlen is computed for each comparison of the for loop, then the solution has become O(n^2) instead of O(n)
And the simple fix:
int length = strlen(s1);
for(i=0;i<length;++i)
void scan(string s1,string s2)
{
map<char, int> a;
int i1=0,i2=0;
int i=0;
for(;i<s2.size();i++)
a[s2[i]]+=1;
for(i=0;i<s1.size();i++)
{
if(i<s2.size()&&s1[i]==s2[i])
i1++;
if(i<s2.size()&&s1[i]!=s2[i])
if(a[s1[i]]>0)
i2++;
}
cout<<i1<<i2;
}
Hi,
I like the hashmap solution because it can handle lowercase and uppercase ANSI letters or any other characters. The present alph[] solution would attempt to index the array out of bounds on uppercase letters.
(I think this would be a question to ask the interviewer while you design the solution. Q. Should the solution be case sensitive or not?)
There was a bug in the hashmap solution. It kept counting all instances of a mismatched letter in string2, even when there were no more corresponding mismatched instances of the letter in string1.
It failed on this test by counting both b's in string2:
scan( "aba", "bab" );
Expected 0 2
Returned 0 3
Corrected solution below:
--a[ s1[i] ];//decrement used chars in string 1
void scan(string s1,string s2)
{
map<char, int> a;
int i1=0,i2=0;
int i=0;
for(;i<s2.size();i++)
a[s2[i]]+=1;
for(i=0;i<s1.size();i++)
{
if(i<s2.size()&&s1[i]==s2[i])
i1++;
if(i<s2.size()&&s1[i]!=s2[i])
if(a[s1[i]]>0)
{
i2++;
--a[ s1[i] ];//bug fix
}
}
std::cout << s1 << " " << s2 << " -> " << i1 << " " << i2 << "\n";
}
I agree I more check is required.
The codeymon code assumes that both strings contain the same chars , may be not in order.
But there needs to be a check in the second for before incrementing n2,if the char in s2 is present somewhere in s1.
If the char isnt present in s1 then n2 should not be incremented.
This one works.
void stringMatch(char *str1, char *str2, int *n1, int *n2)
{
int charSet[256];
memset(charSet, 0, sizeof(charSet));
int len1 = strlen(str1);
int len2 = strlen(str2);
int i;
for (i = 0; i < len2; i++)
charSet[str2[i]] = 1;
for (i = 0; i < len1; i++)
{
if (i<len2 && str1[i] == str2[i])
(*n1)++;
else if (i<len2 && str1[i] != str2[i])
{
if (charSet[str1[i]])
(*n2)++;
charSet[str1[i]] = 0;
}
}
}
n2 is wrong. Here is the code that works. (Ref. WIKI: longest common substring)
int stringMatch(char *s1, char *s2, int *n1, int *n2)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
char* pre=(char*)malloc (len2*sizeof(char));
char* cur=(char*)malloc (len2*sizeof(char));
char* swap;
if(!pre || !cur) {printf("Memory allocation error.\n"); return -1;}
memset(pre, 0, sizeof(pre));
memset(cur,0,sizeof(cur));
*n1=*n2=0;
for(i=0;i<len1;i++)
{
if(s1[i]==s2[i])
(*n1)++;
for(j=0;j<len2;j++)
{
if(s1[i]!=s2[j])
{
cur[j]=0;
}
else
{
if(i==0 || j==0)
cur[j]=1;
else
cur[j]=1+pre[j-1];
}
if(*n2<cur[j])
*n2=cur[j];
}
swap=cur;
cur=pre;
pre=swap;
}
free(pre);
free(cur);
return 0;
}
vector<int> char_match(const string s1, const string s2){
unordered_map<char, int> ch2int1, ch2int2;
int k(0);
for (int i = 0; i!= s1.size(); i++) {
ch2int1[s1[i] ]++;
if (s1[i] == s2[i] && i < s2.size()) {
k++;
}
}
for (int i = 0; i!= s2.size(); i++) {
ch2int2[s2[i] ]++;
}
int t(0);
for (unordered_map<char, int>::iterator miter = ch2int1.begin(); miter != ch2int1.end(); miter++) {
if (miter->second > ch2int2[miter->first]) {
t += ch2int2[miter->first];
} else{
t+= miter->second;
}
}
vector<int> ivec;
ivec.push_back(k);
ivec.push_back(t-k);
return ivec;
}
vector<int> char_match(const string s1, const string s2){
unordered_map<char, int> ch2int1, ch2int2;
int k(0);
for (int i = 0; i!= s1.size(); i++) {
ch2int1[s1[i] ]++;
if (s1[i] == s2[i] && i < s2.size()) {
k++;
}
}
for (int i = 0; i!= s2.size(); i++) {
ch2int2[s2[i] ]++;
}
int t(0);
for (unordered_map<char, int>::iterator miter = ch2int1.begin(); miter != ch2int1.end(); miter++) {
if (miter->second > ch2int2[miter->first]) {
t += ch2int2[miter->first];
} else{
t+= miter->second;
}
}
vector<int> ivec;
ivec.push_back(k);
ivec.push_back(t-k);
return ivec;
}
- codeyman February 24, 2007void chareq(char *s1, char *s2) { int alph[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; int n1=0,n2=0; int i; for(i=0;i<strlen(s1);++i) ++alph[s1[i]-'a']; for(i=0;i<strlen(s1);++i) { if(s1[i]==s2[i]) { --alph[s1[i]-'a'];++n1;} } for(i=0;i<strlen(s2);++i) { if(alph[s2[i]-'a']!=0 ){ --alph[s2[i]-'a'];++n2;} } printf("%d %d\n",n1,n2); }