Microsoft Interview Question for Software Engineer / Developers

• 0

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

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

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

To understand the question better,
does the array look like

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] = "";

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

Considering 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?

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

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.

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

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] = "";

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

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

That's not necessarily true. We can use a hash function to dynamically calculate the hash int for each string and then build the hash table. It saves a bit space but costs more time.

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

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 ?

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

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.

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

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

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

During the single pass, you can as well search the string linearly. Why would you create another structure and then search in the second pass.

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

Build a Suffix Tree using the strings and then find your string till the end of it... WCC is O(logN)

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

#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);
else cout<<"position without empty string :"<<res;

}

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

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.

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.