Microsoft Interview Question Software Engineer in Tests
Team: Office
Country: United States
Interview Type: Phone Interview
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)
@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.
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)
{
Console.WriteLine("The pattern string is not found in input string");
}
}
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;
}
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;
}
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;
}
}
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");
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;
}
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");
}
Console.ReadLine();
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
// 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;
}
// 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;
}
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
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;
}
}
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;
}
}
}
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;
}
}
}
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)
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;
}
public static void checkIfSubString(){
String main="GoogleSearchPage".toLowerCase();
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");
}
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)
System.out.println("Substing is not found");
}
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)
System.out.println("Substing is not found");
}
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);
}
}
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");
}
}
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) {
return tolower(c) - 'a';
}
/* 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);
}
KMP algorithm/ Z algorithm.
- Cerberuz May 18, 2013