Microsoft Interview Question for Software Engineer / Developers


Country: India




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

I guess we can put one string S2 characters into ascii char[256] array.
And 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'.

- Alice7 November 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- Ravi Hingarajiya November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- kratznick November 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Anonymous November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sathishperias November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- hanqingliu1989 November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Laxmi Narsimha Rao Oruganti November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think you can use those strXXX functions.

- appscan November 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
}

- Anonymous November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Nani November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think if we apply Boyer-Moore's algorithm with small modification, we can do it in one parse. This question seems like an application of StrStr(). I'll try to get the code working for the same thought.

- Victor November 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- kmrinalinipriyanka November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
                }
        }
}

- numa November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

- P November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kratznick November 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Kratznick: After reading most of the answers, it looks like that discussion is going on on 1st test case...

below is written a code by Anonymous

- Skataria December 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

- Anonymous December 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Any comment guys on this algo...also can we discuss order analysis on this??

- Skataria December 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- Sanjay Kumar December 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Sanjay Kumar December 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}
}
}

- Jatin May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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++;
}

- code_monkey November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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++;    
}

- code_monkey November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It looks like your complexity is m (s1 string length) * n (s2 string length)

- Ravi H November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think if we apply Boyer-Moore's algorithm with small modification, we can do it in one parse. This question seems like an application of StrStr().

- Victor November 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Its SubString Matching problem & Can be Done in linear time O(N) using KMP & Boyer-Moore's algorithm ins't it google it ?

Thanks
Shashank

- WgpShashank November 07, 2011 | 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