Microsoft Interview Question
Software Engineer in Tests<pre lang="" line="1" title="CodeMonkey1980" class="run-this"> public static List findSubStringIndex(String str, String substr) {
List<Integer> indexlist = new ArrayList<Integer>();
int j =0;
for(int i=0; i< str.length(); i++) {
if(str.charAt(i) == substr.charAt(j)) {
if(j + 1 == substr.length()) {
indexlist.add(i - j);
j=0;
} else
j++;
}
}
return indexlist;
}</pre><pre title="CodeMonkey1980" input="yes">
</pre>
#include <iostream>
#include <vector>
using namespace std;
int StringIndex(char *s, char *p, int start)
{
int i, j, k;
for(i = start; s[i] != '\0'; i++)
{
j = i;
k = 0;
while(s[j] != '\0' && (s[j] == p[k]))
{
j++;
k++;
}
if(k > 0 && p[k] == '\0')
return i;
}
return -1;
}
void patternOcurrences(char *s, char *p)
{
vector<int> positions;
int pos, start;
start = 0;
for(;;)
{
pos = StringIndex(s, p, start);
if(pos == -1)
break;
positions.push_back(pos);
start = pos+1;
}
vector<int>::iterator it = positions.begin();
while(it != positions.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
char *str = "xmpabcypstabcpqrabcst";
char *pattern = "abc";
patternOcurrences(str, pattern);
return 0;
}
public int[] PatternMatch(string s, string p){
int sLen = s.length();
int pLen = p.length();
if(sLen == 0 || pLen == 0)
return null;
else if(sLen <pLen)
retrun null;
else{
int k=0 n=0;
int[] match;
while(k<sLen - pLen ){
if(strcmp(s.substr(k, pLen-1), p){
match[n] = k;
n++
}
k++
}
return match;
}
}
- max August 09, 2011