## Microsoft Interview Question for Software Engineer in Tests

Team: Office
Country: United States
Interview Type: Phone Interview

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

KMP algorithm/ Z algorithm.

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

Just a doubt ...

will it be better if we use Tries here...? As according to the question the main string appears to be fixed and we are checking for different short strings.

So using tries will provide a solution ~ O("lenght of SHOTR string") <<O(n)

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

@PiysuhRai: May be that is true. But KMP is space efficient too. With Tries, I'm assuming you'll need O(n^2) space since you'll have to store substrings starting at each position starting from 0 to (n-1). So I guess it is a compromise.

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

Here is the code for this algorithm
Main function

``````public static void StringSearchOptimized(string inputStr, string patternStr)
{
if(string.IsNullOrEmpty(inputStr) || string.IsNullOrEmpty(patternStr))
{
throw new Exception("Input is not valid");
}
int patternLength = patternStr.Length;
var longestPrefixSuffix = FindLongestPrefixSuffix(patternStr);
int inputStrLength = inputStr.Length;
int i=0,j = 0;
bool isFound = false;
while(i < inputStrLength)
{
if(patternStr[j] == inputStr[i])
{
j++;
i++;
}
if(j == patternLength)
{
Console.WriteLine("The pattern string is found between {} and {} of input string", i-patternLength,i);
j = longestPrefixSuffix[j-1];
isFound = true;
}
else if(i < N && patternStr[j] != inputStr[i])
{
if(j == 0)
{
i++;
}
else
{
j = longestPrefixSuffix[j-1];
}
}
}
if(isFound == false)
{
}
}``````

Longest prefix and suffix finder function

``````public static int[] FindLongestPrefixSuffix(patternStr)
{
int patternLength = patternStr.Length;
int[] longestPrefixSuffix = new int[patternLength];
longestPrefixSuffix[0] = 0;
int j;
for(int i = 1; i < patternLength; i++)
{
j = longestPrefixSuffix[i-1];
while(patternStr[i] != patternStr[j+1] && j > 0)
{
j = longestPrefixSuffix[j];
}

if(j == 0 && patternStr[i] != patternStr[j+1])
{
longestPrefixSuffix[i] = 0;
}
else
{
longestPrefixSuffix[i] = j + 1;
}
}
return longestPrefixSuffix;
}``````

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

int substring()
{
char s[]="AmitPratapSingh";
char sub[] = "ra";
int i,j;
bool flag = false;
int str_len1,str_len2;
i = j = 0;
str_len1 = strlen(sub);
str_len2 = strlen(s);
for(j=0;j<str_len2;j++)
{
if(sub[i] == s[j])
{
if( i == str_len1-1)
{
flag = true;
break;
}
i++;
continue;
}
else
{
i = 0;
}
}

if(flag)
printf("It is Substring\n");
else
printf("Not Substring\n");
return 0;
}

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

The above code will not work for below test
char s[] ="hellotest";
char[] sub="lo";
there is slightly modification in else part

else
{
if (i > 0)
{
j--;
i = 0;
}
else
{
i = 0;
}
}

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

mr.kalai ur suggestion is also not useful.
because ur code will not work for main string aaabcdef and substring is aab so slight change of ur code is
else
{
if (i > 0)
{
j-=i-1;
i = 0;
}
else
{
i = 0;
}
}

Comment hidden because of low score. Click to expand.
1
of 3 vote

``````string str1 = "hello world";
string str2 = "world";

int index = 0;

for (int i = 0; i < str1.Length; i++)
{
if (index < str2.Length)
{
if (str1[i] == str2[index])
index++;
else
{
index = 0;
if (str1[i] == str2[index])
index++;
}
}
}

if (index == str2.Length)
Console.WriteLine("Is Substring");
else
Console.WriteLine("Is not Substring");``````

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

This does NOT work. Ex, str1="abcabcabd", str2="abcabd".

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

I was able to solve it with O(n^2), but not with O(n). Also I dont think we can do it in O(n). Correct me if I'm wrong. However the interviewer did not even tell me if there exists an O(n) solution, after the interview.

this was my code:

``````public bool issubstring(string main, string sub)
{
char[] m = main.ToCharArray();
char[] s = sub.ToCharArray();
int i=0, j=0, k;
bool issubstr = false;

for (i=0;i<m.Length;i++)
{
k=i;
for(j=0;j<s.Length;j++)
{
if(m[k] == s[j])
{
k++;
issubstr = true;
continue;
}
else
{
issubstr = false;
break;
}
}
}
if (issubstr == true)
return issubstr;
else
return issubstr;
}``````

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

Did you try to execute this code? It doesn't work with simple strings even - issubstring("Apple","ple").

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

Don't assume that if you don't know the algorithm then it won't exist. Try to look out the two algorithms i mentioned in my comment ( both are almost same ).

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

Thanks, i'm looking into those algorithms. I didn't assume there cant be better solution than mine :), it's just that I was not aware how we can do this with a linear solution.

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

Since the string is "short", say abc, compute the DFA for .*abc.* and run the big string through it.

KMP is apparently an optimization of this approach.

Z algorithm is neat, and a dynamic programming algorithm.

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

All the given algo are O(n*m) where n is length of input and M length of substring.

A more efficient algorithm is building a Trie out of the long input string O(n) and once that is done, existence test is done in O(m) where m is length of substring.

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

string parent = "abcdef";
string substr = "cde";
bool isSubstr = false;
int parentcount = parent.Length;
int substrcount = substr.Length;

char[] parentarr = parent.ToCharArray();
char[] substrarr = substr.ToCharArray();
int j = 0;

for (int i = 0; i < parentcount; i++)
{
if (parentarr[i] == substrarr[j])
{
j++;
if (j == substrcount)
{
Console.WriteLine("This is a sub string");
isSubstr = true;
break;
}
}
else
{
j = 0;
}

}

if (!isSubstr)
{
Console.WriteLine("This is not a sub str");
}

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

public class StringExam2 {

public static void main(String[] args) {

String s1="thulalsi";

String s2="lal";
String s3=s1.substring(3, 6);
if(s2.equals(s3)){
System.out.println("equals");
}
substringfinding(s1,s2);
}

private static void substringfinding(String s1, String s2) {

int i=0;
int len=s1.length();
int j=s2.length();
System.out.println(j);
for(i=0;i<len-1&&j<len;i++){
if(s2.equals(s1.substring(i, j))){
System.out.println("true");
}
else{
//System.out.println("j value is"+j+"i value is"+i);
j++;
}
}
}
}

please tell me if any wrong

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

``````// this function will return the beginning index of substring otherwise return -1
public static int indexOfSubString(String str, String target){
int index = -1;
int runner = 0;  //running index for target string
if(str == null || target == null || target.length() > str.length)
return index ;

char[] strChars = str.toCharArray();
char[] targetChars = target.toCharArray();
for(int i=0;i<strChars .length ; i++){
if(chars[i] == targetChars[runner]){
if(runner == 0)
index = i;
runner++;
if(runner == targetChars.length)  //is sub string
{
return index;
}
}
else{
runner = 0;
index = -1;
}
}
return index;
}``````

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

// Question clearly says a big string and a small string. No need for any complex algo like KMP.

``````int isasubstring(char *big, char *small, int big_l, int small_l) {
int i = 0, j = 0;
if (big == NULL || small == NULL || big_l == 0 || small_l == 0)
return 0;
for(i=0;i<big_l;i++) {
if(big[i] == small[j]) {
if (j == small_l - 1)
return 1;
++j;
} else {
j = 0;
}
}
return 0;
}``````

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

``````def findSubString (short_str,long_str):
if len(short_str) > len(long_str):
return False

s = 0
l = 0
scanning = False
found = False

while l < len(long_str):
if scanning:
if long_str[l] != short_str[s]:
scanning = False
s = 0
else:
s = s + 1
else:
if long_str[l] == short_str[s]:
scanning = True
s = s + 1

l = l + 1

if (s == len(short_str)):
found = True
break

return found``````

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

we can create a temp array to sore the occurrence of each char in the given string, and then start matching the count with the given string.

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

there's this Knuth Morris Pratt's algo of substring matching that would solve this prob in linear time by using a prefix function and a string matcher..

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

KMP

``````int kmp()
{
int i;
kmptable();
int k=-1;
for(i=0;i<m;i++)
{
while(k>-1&&pattern[k+1]!=text[i])
{
k=table[k];
}
if(text[i]==pattern[k+1])
{
k++;
}
if(k==n-1)
{
return i-k+1;
}
}
return -1;
}

void kmptable()
{
int k=-1;
int i=1;
table[0]=k;
for(i=1;i<n;i++)
{
while(k>-1&&pattern[k+1]!=pattern[i])
{
k=table[k];
}
if(pattern[i]==pattern[k+1])
{
k++;
}
table[i]=k;
}
}``````

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

I am beginner, tried something..looks like it works

``````public static void main(String[] args){

String str1=new String();
String str2=new String();

Scanner s= new Scanner(System.in);

System.out.println("Enter the String");

str1 = s.nextLine();

System.out.println("Enter the Substring");

str2= s.nextLine();

int index=0;

for(int i=0; i< str1.length();i++){

if(str1.charAt(i)== str2.charAt(index)){

if(index==str2.length()-1)   {

System.out.println("String found");
break;
}

else{
index++;

}
}

else{

i=i-index;
index=0;

}

}

}``````

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

i m a beginner..tried something, looks like it works

``````public static void main(String[] args){

String str1=new String();
String str2=new String();

Scanner s= new Scanner(System.in);

System.out.println("Enter the String");

str1 = s.nextLine();

System.out.println("Enter the Substring");

str2= s.nextLine();

int index=0;

for(int i=0; i< str1.length();i++){

if(str1.charAt(i)== str2.charAt(index)){

if(index==str2.length()-1)   {

System.out.println("String found");
break;
}

else{
index++;

}
}

else{

i=i-index;
index=0;

}

}

}``````

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

``````public class ShortStringIsPartOfMainString {

public static void main(String[] args) {
String mainStr="abcabcabd";
String shortStr="abcabd";
int j = 0;
boolean bool=false;
if(mainStr.length()>shortStr.length()){
for(int i=0;i<mainStr.length();i++){
if(j<shortStr.length()&&mainStr.charAt(i)==shortStr.charAt(j)){
j++;
if(j==shortStr.length()){
System.out.println("Yes string is present in main");
bool=true;
break;
}
}else{
j=0;
}

}
if(!bool)
System.out.println("String not present in main");
}else
System.out.println("Main string is smaller than short one");
}

}``````

Complexity is O(n)

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

I have got to solve it in O(N). Please let me know if you think this will not work in any scenario.

``````public static void main(String[] args) {
String s1="abfghifghijcdehuj";
String s2="fghij";
isStringContainsSubstring obj = new isStringContainsSubstring();
int index = obj.findIndexOfSubsting(s1,s2);
System.out.println("Starting index of substring is "+index);
}

int findIndexOfSubsting(String s1,String s2){
int i=0,j=0;
while(i<s1.length()){
if(s1.charAt(i)==s2.charAt(j)){
i++;
j++;
if(j==s2.length()){
return i-j;
}
}
else{
if(j==0)
i++;
j=0;
}
}
return -1;
}``````

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

``````public static void checkIfSubString(){
String substr="sea".toLowerCase();
int j=0;
for(int i=0;i<main.length()&&j<substr.length();i++){
if(main.charAt(i)==substr.charAt(j)){
j++;
continue;
}else
j=0;
}
if(j==substr.length()){
System.out.println("is sub string");
}else
System.out.println("is not sub string");``````

}

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

public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String s1 = "abcabcabd";
String s2 = "ca";
boolean flag = true;
char ch = s2.charAt(0);
int k = s1.indexOf(ch);
System.out.println("k111= "+k);

while(k != -1 && k < s1.length())
{
StringBuffer sb = new StringBuffer();
int p = 0;
if(s1.length() - k >= s2.length())
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j) == s1.charAt(k))
{
flag = true;
k++;
}
else
{
flag = false;
k = ++p;
break;
}
}
if(flag == true)
{
System.out.println("Substring is found");
break;
}
else
if(flag == false)
{
for(int i = k;i<s1.length();i++)
{
sb.append(s1.charAt(i));
}
s1 = sb.toString();
k = s1.indexOf(s2.charAt(0));
}
}
else
{
System.out.println("size of Substring is bigger than actual String");
break;
}

}

if(flag == false)
}

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

Test Data -
"abcabcabd" -> "bbc";
"abcabcabd" -> "abcabd"
"abcabcabd" -> "d"
"abcabcabd" -> "b"
"abcabcabd" -> "ca"
"apple" -> "ple"
"apple" -> "pal"
"apple" -> "ppleapple"
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
String s1 = "abcabcabd";
String s2 = "ca";
boolean flag = true;
char ch = s2.charAt(0);
int k = s1.indexOf(ch);
while(k != -1 && k < s1.length())
{
StringBuffer sb = new StringBuffer();
int p = 0;
if(s1.length() - k >= s2.length())
{
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j) == s1.charAt(k))
{
flag = true;
k++;
}
else
{
flag = false;
k = ++p;
break;
}
}
if(flag == true)
{
System.out.println("Substring is found");
break;
}
else
if(flag == false)
{
for(int i = k;i<s1.length();i++)
{
sb.append(s1.charAt(i));
}
s1 = sb.toString();
k = s1.indexOf(s2.charAt(0));
}
}
else
{
System.out.println("size of Substring is bigger than actual String");
break;
}

}

if(flag == false)
}

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

``````string text = "This is the text";
string sub = "is";

for (int i = 0; i <= (text.Length - sub.Length); i++) {
if (sub == text.Substring(i, 2)) {
Console.WriteLine ("Found!");
}
}``````

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

def shortstringinBigString(main,sub):
lenm = len(main)
lens = len(sub)
for i in range(lenm):
if main[i:i+lens] == sub:
print True
break
else:
print false

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public class CheckIfAStringIsASubstringOfAMainString {

private static String shortStr = "aba"; // m characters
private static String mainStr = "this is an abaacus"; // n characters

static Map<String, Integer> hMap = new HashMap<String, Integer>();

public static void main(String[] args) {

int lShort = shortStr.length();
int lMain = mainStr.length();

if(lShort > lMain)
{
System.out.println(shortStr + " - is not a SubString of - " + mainStr);
System.exit(0);
}

hMap.put(shortStr, 1);
for(int i = 0; i <= lMain-lShort; i++ ) // O(n-m) where n > m
{
String substring = mainStr.substring(i, i+lShort);
if(hMap.containsKey(substring)) // O(1)
{
System.out.println(shortStr + " is a SubString of \"" + mainStr + "\" starting at position " + i );
System.exit(0);
// net time complexity of this search is O(n-m+1) === O(n)
}
}
System.out.println(shortStr + " - is not a SubString of - " + mainStr);
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void subStringinMainString(String mainstr,String substr)
{
String newstr = "";
for (int i = 0; i <= mainstr.Length - substr.Length;)
{
newstr = mainstr.Substring(i, substr.Length);
if(newstr==substr)
{
Console.WriteLine(newstr +" is substring");
break;
}
else { i++; }
}

if (newstr != substr)
{
Console.WriteLine(substr + " is not substring");
}
}``````

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

shouldn't use SubString. That's what we are supposed to code.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

I believe the complexity of my solution is O(N). In this code is used a hash function to avoid compare strings.

``````#include <string.h>
#include <stdio.h>
#include <ctype.h>

int val(char c) {
}

/* Compute hash of a string of size n
*  Use base B and modulo M
*/
int hash(char *s, int n, int B, int M) {
int h = 0;
int p = 1;
for (int i = n - 1; i >=0 ; i--) {
int v = val(s[i]);
h += (v * p) % M; // v * B ^ (n - i - 1)
h %= M;

p *= B; // p = B ^ (n - i - 1) % M
p %= M;
}
return h;
}

/* Check if two strings are equal */
bool check(char *a, char *b, int m) {
for (int i = 0; i < m; i++)
if(a[i] != b[i])
return false;
return true;
}

/* This algorithm searches for a text substring that is equals
* a given pattern. This algorithm uses  strings hash to avoid
* string comparations (This idea is similar a Rabin-Karp algorithm).
* For calculate the hash is necessary a base B (number of symbols in
* the alphabet) and a number M (preferably a prime number) to get
* modulo by M.
* Expected complexity of this algorithm is  O(N).
*/
int _find(char *text, char *pattern, int B, int M) {
int i;
int m = strlen(pattern);
int n = strlen(text);
int hp = hash(pattern, m, B, M);
int ht = hash(text, m, B, M);

// bm = B^(m - 1) % M
int bm = 1;
for (i = 0; i < m - 1; i++) {
bm *= B;
bm %= M;
}

// Check if strings are equal, First case
if(hp == ht && check(text, pattern, m)) {
return 0;
}

for ( i = 1; i <= n - m; i++) {
/* Update the hash in constant time
* H(i) =(B *(H(i-1) - text_(i-1) * B^(m-1)) - text_(i + m -1) ) %M
*/
ht = B * (ht - (val(text[i - 1]) * bm) % M) + val(text[i + m - 1]);
ht %= M;
ht = (ht + M) % M;

// If hash's are equal, do check
if(hp == ht && check(text + i, pattern, m)) {
return i;
}
}

//Don't find pattern in text
return -1;
}

int find(char *t, char *p) {

return _find(t, p, 26, 2111);
}

int main() {

char t[100], p[100];

scanf("%s %s", t, p);

int r = find(t, p);

printf("Position of pattern in text : %d\n", r);

}``````

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.

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

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

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