## Microsoft Interview Question for Software Engineer in Tests

• 0

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

``````// Rabin-Karp algorithm

/**
* Write a function that takes an input string and a pattern string and returns a collection
* of indices of occurences of pattern within the input string.
*
* N - 'base' string length
* M - 'pattern' string length
*
*/
public final class RabinKarpStringMatcher {

public RabinKarpStringMatcher(String base, String pattern) {
if( base == null || pattern == null ){
throw new IllegalArgumentException("NULL 'base' or 'pattern' string passed: base = '" + base + "', pattern = '" + pattern + "'");
}

this.base = base;
this.pattern = pattern;
this.patternLength = pattern.length();
this.baseLength = base.length();
this.patternHash = calculateHash(pattern, 0, patternLength-1);
}

/**
* Time: O(N+M)
*/
public List<Integer> findMatches(){

if( matchedIndexes == null ){

matchedIndexes = new ArrayList<Integer>();

final int lastIndex = baseLength - patternLength + 1;

BigInteger baseValue = null;
int baseHash = 0;

for( int i = 0; i < lastIndex; i++ ){

if( i == 0 ){
baseValue = calculateValue(base, 0, patternLength-1);
}
else {
baseValue = recalculateValue(base, baseValue, i-1, i+patternLength-1);
}

baseHash = baseValue.mod( BigInteger.valueOf(MODULO) ).intValue();

if( baseHash == patternHash && isBaseEqualToPattern(i) ){
}
}
}

return matchedIndexes;
}

//==== PRIVATE ====

private final String base;
private final String pattern;
private final int patternLength;
private final int baseLength;
private final int patternHash;

private static final int MODULO = 307;
private static final int BASE = 32;
private static final int BASE_SHIFT = 5; // pow(2, BASE_SHIFT) = BASE

private List<Integer> matchedIndexes;

/**
* Time: O(M)
*/
private boolean isBaseEqualToPattern(int from){
for(int j = 0; j < patternLength; j++ ){
if( base.charAt(from+j) != pattern.charAt(j) ){
return false;
}
}
return true;
}

/**
* Time: O(M)
*/
private BigInteger calculateValue(String str, int from ,int to){

BigInteger value = BigInteger.valueOf(0);

for( int i = from; i < to+1; i++ ){
value = value.multiply( BigInteger.valueOf(BASE) ).add( BigInteger.valueOf(str.charAt(i)) );
}

return value;
}

/**
* Time: O(M)
*/
private int calculateHash(String str, int from ,int to){

int hash = 0;

for( int i = from; i < to+1; i++ ){
hash = ( hash * BASE + str.charAt(i) ) % MODULO;
}

return hash;
}

/**
* Time: O(1)
*/
private BigInteger recalculateValue(String str, BigInteger hash, int from ,int to){

final int h = 1 << ( BASE_SHIFT * (to-from-1));

BigInteger newHash = hash.subtract( BigInteger.valueOf(str.charAt(from)).multiply( BigInteger.valueOf(h) ) );
newHash = newHash.multiply( BigInteger.valueOf(BASE) );

return newHash;
}
}``````

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

Or do KMP - a little trickier to implement but faster

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

Yes with the help of Kmp we can do this in O(n) time :)

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

Or use finite automate.)))

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

how to implemenet using Finite automata . Can you explain the logic with examples

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

<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()) {
j=0;
} else
j++;
}
}

return indexlist;
}</pre><pre title="CodeMonkey1980" input="yes">
</pre>

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

int *find(string str,string pattern){
int p=0,i;
int arr[20];//initialised to 0
for(i=0;i<str.length()-pattern.length();i++){
int j=0;
int k=i;
while(str[i]==pattern[j]){
k++;
j++;
}
if(j==pattern.length()){
arr[p]=i;
p++;
i=k-1;
}
}
return arr;
}

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

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

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

Use a suffix tree and return the indices!

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

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

}

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.