Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Your proposal solution complexity is m(s1 string length) + n(s2 string length).
It works with only ACSII character. How about with non ACSII character ?
I have a doubt in the proposed complexity. When copying, the worst case could be when we are copying (n-1) times [i.e. the first two characters of the strings - S1,S2 match]. The length of copying characters may decrease as we proceed. So, what I am getting as the complexity is m(S2 string length) + n*n(n is S1 string length). Please reply.
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
char *strMinus(char *s1, char *s2)
{
char *p;
size_t s2_size;
if (!(p = strstr(s1, s2)))
return s1;
s2_size = strlen(s2);
while (p = strstr(s1, s2)) {
*p = '\0';
strcat(s1, p + s2_size);
}
return s1;
}
This program is simple and clear. Thats why C or C++ are good to use than C#. We can write clear programs with less loops.
I dont understand this part:
strcat(s1, p + s2_size);
I think this wont work. Can anyone explain me how to remove s2 occurring from s1 and return s1.
Actually it does work :)
I use strstr(s1, s2) here to return a pointer which points to the start of s2 in s1. In the example, it points to 'b' in 'abcdB'. Then change it to '\0' turns s1 to 'a' only because 'a' is followed by '\0'.
p+s2_size is a pointer which points to 'c' in 'abcdB'. Therefore, strcat(s1, p + s2_size) changes s1 to 'a'+'cdB', which is the correct answer.
strcat, strcpy, memcpy - All these behave undeterministically when the src and target memory regions overlap. In case of mem* API, memmove is designed to work correctly with overlapping regions. I dont think there is something called strmove which would take care of overlapping regions. Again, you might find this working on one particular implementation, but that is not guarenteed across all platforms and processors.
Thanks,
Laxmi
void subStringMinus(char* s1,char* s2){
int j=0, attemptAtIndex;
for(int i=0; s1[i]!='\0';i++){
cout << "checking for: " << i << " " << j << endl;
if(s1[i] == s2[j]){
attemptAtIndex = i;
while( s1[i++] == s2[j++]){
if(s1[i] == '\0' || s2[j] == '\0')
break;
}
if(s2[j] == '\0' && (s1[i-1] == s2[j-1]) ){ //substring is present in s1 starting at i=i-j.
i=i-j;
int k;
for(k=0;s1[i+k]!='\0';k++){
s1[i+k] = s1[i+k+j];
}
}
else
i = attemptAtIndex; // attempt Failed! start from next position...
}
j=0;
}
}
private static String removeString(String s1, String s2)
{
int i = 0;
String result = "";
int s1Length = s1.length();
int s2Length = s2.length();
while(i < s1Length)
{
boolean flag = false;
if(s1.charAt(i) == s2.charAt(0) && i + s2Length <= s1Length)
{
flag = true;
int j = 1;
while(j < s2Length)
{
if(s1.charAt(i + j) == s2.charAt(j))
j++;
else
{
flag = false;
break;
}
}
}
if(flag)
{
i += s2.length();
}
else
{
result += s1.charAt(i);
i++;
}
}
return result;
}
Complexity is O(s1.length * s2.length)
I guess this is one more possible way of implementing s1 minus s2.
main()
{
char a[] = "abcd";
char b[] = "bc";
int i =0, j=0, k = 0;
int m = strlen(a);
int n = strlen(b);
while(j<n && i<m)
{ while(i<m)
{ if(a[i] == b[j])
{ key = a[i];
for(k=i;k<m-1;k++)
a[k] = a[k+1];
a[k] = '\0';
m--;
break;
}else i++;
} j++;
}
printf("Here is the final array\n");
printf("%s" , a);
}
bool matches(std::string::iterator it1, std::string::iterator e1, const std::string& s2)
{
typedef std::string::const_iterator I;
I it2 = s2.begin();
I e2 = s2.end();
for( ; it1 != e1 && it2 != e2; ++it1, ++it2) {
if(*it1 != *it2) {
return false;
}
}
return it2 == e2;
}
void remove_occurences(std::string& s1, const std::string& s2)
{
if(s2.size() > s1.size()) { //for optimization
return;
}
typedef std::string::iterator I;
for(I it = s1.begin(); it != s1.end(); ) {
if(matches(it, s1.end(), s2)) {
it = s1.erase(it, it + s2.size());
} else {
++it;
}
}
}
void Remove(string& s1, string& s2) {
char *p1 = *p2 = s1;
char *p3, *p2temp;
int len = strlen(s2);
while (p2 != '/0') {
p3 = s2;
p2temp = p2;
count = 0;
while (*p2temp++ = *p3++)
count++;
if (count == len)
p2=p2temp;
*p1=*p2;
p1++;
p2++;
}
//Discard rest of the string
*p1 = '/0';
++p1;
while(p1!='/0')
free(p1++);
}
Complexity: O(len(s1))
I am a bit confused with the given test data and question. Please tell me for which test cases, the given question is appropriate :
Syntax : the first two lines contain strings S1 and S2 respectively. And third line contains S1-S2.
TEST CASE
1)
abcdB
bc
adB
2)
abcdB
bB
acd
3)
abcdB
pBq
abcd
4)
abcdB
bcB
ad
<pre lang="" line="1" title="CodeMonkey40642" class="run-this">import java.util.regex.Matcher;
import java.util.regex.Pattern;
public final class RegexTest {
private static String REGEX = "RemoveMe";
private static String INPUT = "YourRemoveMeName";
private static String REPLACE = "";
public static void main(String[] args) {
Pattern p = Pattern.compile(REGEX);
Matcher m = p.matcher(INPUT);
StringBuffer sb = new StringBuffer();
while (m.find()) {
m.appendReplacement(sb, REPLACE);
}
m.appendTail(sb);
System.out.println(sb.toString());
}
}
</pre><pre title="CodeMonkey40642" input="yes">
</pre>
what about this... ?
# include <conio.h>
# include <stdio.h>
#include <string.h>
int main ()
{
char s1[]="sanjay kumar", s2[]="y k";
char *s3; int i,len;
s3=strstr(s1,s2);
strncpy(s3,s3+strlen(s2),strlen(s3+strlen(s2)));
len=strlen(s1)-strlen(s2);
for(i=strlen(s1);i>=len;i--)
s1[i]='\0';
printf("%s",s1);
getch();
}
Above one replace only the first occurance.. this one replace all..
# include <conio.h>
# include <stdio.h>
#include <string.h>
int main ()
{
char s1[]="sanjay kumar", s2[]="a";
char *s3; int i,len;
s3=strstr(s1,s2);
while (1)
{
if(s3==NULL)
{
break;
}
strncpy(s3,s3+strlen(s2),strlen(s3+strlen(s2)));
len=strlen(s1)-strlen(s2);
for(i=strlen(s1);i>=len;i--)
s1[i]='\0';
s3=strstr(s1,s2);
}
printf("%s",s1);
getch();
return 0;
}
void stringMinus()
{
char[] s1={'a','b','c','d','a','x','y'};
char[] s2 = { 'a' };
int i, j;
int a = 0;
bool match = false;
for (i = 0; i < s2.Length; i++)
{
match = false;
a = 0;
while(!match)
{
if (s2[i] == s1[a])
{
match = true;
for (j = a; j < s1.Length - 1; j++)
{
s1[j] = s1[j + 1];
}
}
a++;
}
}
}
Use 2 indices 'i' and 'j'. Put 'i' at the beginning of s1 and 'j' at the beginning of s2.
Increment i everytime we don't get a match. If we do get a match run a temp from i to i+j to see if a match occurs.
If we get a match, set the flag to 1.
Here's a basic pseudo-code:
while(i!=strlen(s1))
{
if(s1[i]==s2[j])
{
//here we write a loop to compare each character of s1 and s2 till s2 runs out linearly
//Break if a mismatch occurs if we reach the end of s2, set flag = 1.
if (flag == 1)
{
for temp : from i to strlen(str1)
s1[temp]=s1[temp+1];
s1[temp]='\0';
}
}
j = 0;
i++;
}
Use 2 indices 'i' and 'j'. Put 'i' at the beginning of s1 and 'j' at the beginning of s2.
Increment i everytime we don't get a match. If we do get a match run a temp from i to i+j to see if a match occurs.
If we get a match, set the flag to 1.
Here's a basic pseudo-code:
while(i!=strlen(s1))
{
if(s1[i]==s2[j])
{
//here we write a loop to compare each character of s1 and s2 till s2 runs out linearly
//Break if a mismatch occurs if we reach the end of s2, set flag = 1.
if (flag == 1)
{
for temp : from i to strlen(str1)
s1[temp]=s1[temp+1];
s1[temp]='\0';
}
}
j = 0;
i++;
}
I guess we can put one string S2 characters into ascii char[256] array.
- Alice7 November 01, 2011And use two pointers on S1 and keep on checking the ascii values for S1 and if they are found then continue else copy and final character '\0'.