## Microsoft Interview Question

Software Engineer / DevelopersConsidering the array looks like the one below:

a[0] = "a" ;

a[1] = "akb" ;

a[2] = "axnm";

a[3] = "" ;

a[4] = "b";

a[5] = "batman" ;

a[6] = "c" ;

a[7] = "d" ;

a[8] = "dimple" ;

a[9] = "";

Soln 1) build a hashtable with key as each string value as the number of occurance of the string, assuming a string could occur more than once. Scan the hashtable for a given string.

A linear time algorithm however downside is additional space needed to build the hashtable.

Soln 2) would be to use a binary search however, I am confused on how to proceed with the comparison when you hit the empty string.

Any better ideas?

I think building a hash table or creating a BST would be an over-head, considering that the array is already sorted.

I think the algorithm to find the string would be something like:

1) Take the first character from the search string.

2) Go through the array linearly till the first character matches with the first character in the array element strings.

3) From here, check for first character match and each complete string match.

4) Terminate when:

entire string matches

or

first character mismatch is reached.

Null strings should not be a problem for string comparison. They will simply give a string mismatch.

VP,

Your algorithm looks pretty good except that for the following scenario it would fail.

Searching for "dkdfd"

a[6] = "c" ;

a[7] = "d" ;

a[8] = "dimple" ;

a[9] = "";

a[10] = "djdhd"

a[11] = "dkdfd"

a[12] = "";

According to your solution,

1) you try to match the first character of the given string with the first character of each array element and once you found the match

2) you search for the entire string and terminate your search when first character of the search string does not match the first character of the individual array element.

In the above scenario it would stop searching after the code hits a[9] = "";

You will need to modify your solution to ignore null strings you encounter while you linearly traverse the array element.

Plus, the fact that array is presorted, we do not need to continue our search until the first character mismatch is found. Rather,

while(first character matched)

{

if(array element > element to be searched) break;

}

Hi Sucharita,

Yes you are right. Null strings need to be ignored, and the terminating condition given by you is much better.

Khoa, What's the right answer? Any ideas ?

You can use Binary Search for this example. Whenever you hit a empty spot, just traverses left or right until you find a string. Use this string to determine where you're going next.

Is there any restriction that the array shoule not be modified ..

how abt moving all the null strings to the end of the array in a single pass and then performing a binary search in the second pass..

#include<iostream.h>

#include<conio.h>

#include<string.h>

int bsearch ( int low, int high, string item, string string1[] )

{

int mid=((low+high)/2);

int res;

if( strcmp(string1[mid],item)==0 ) // if middle is the serached

{

res=mid;

}

else if( low==high ) // if the input array has only one string and that is not the search string

{

res=0;

}

else if( strcmp( item,string1[mid] ) < 0 ) //item is smaller than mid

{

res= bsearch(low,mid-1,item,string1);

}

else if( strcmp( item,string1[mid] ) > 0 )

{

res= bsearch( mid+1, high, item,string1);

}

return (res);

}

int findstr(string string1[],int size,string item )

{

char new[size][20];

//removing all empty strings

int j=0;

for(int i=0; i<size;i++)

{

new[j]=string1[i];

while( string1[i]=="")

i++;

j++;

}

//if you do not want to remove the empty string leave the above loops

return bsearch(0, j-1 ,item,string1);

}

void main()

{

string string1[]={"a","","","","b","","","C",""};

string item="b";

int size= 9;

int res=findstr(string1,size,item);

if( res==0 ) cout <<"not found";

else cout<<"position without empty string :"<<res;

}

I guess the real question here is "can you do better than O(n)?" In the worst case the answer seems to be "no". But in the average case should be possible to get close to O(log(n)):

Start by looking at the middle element, just like in binary search. If it's an empty string, start to "fan out" left and right looking at a[mid-1], a[mid+1], a[mid-2], a[mid+2] and so on until you find a non-empty string. Compare that with the search value and throw away the part of the array where the search value cannot be. Repeat until search value is found.

This approach gets close to O(n) as the number of empty strings in the array grows.

Khoa, the question is not very clear. Is it reqd to find a given string in this array ?

- abc September 10, 2007