Microsoft Interview Question for Software Engineer / Developers






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 ?

- abc September 10, 2007 | Flag Reply
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] = "";

- Anonymous September 19, 2007 | Flag Reply
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?

- Sucharita September 19, 2007 | Flag Reply
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.

- VP September 19, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sucharita September 20, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- J May 04, 2008 | Flag
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 ?

- VP September 20, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- vodangkhoa September 26, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vel November 02, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Temp February 23, 2008 | Flag
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)

- KSD October 10, 2007 | Flag Reply
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);
if( res==0 ) cout <<"not found";
else cout<<"position without empty string :"<<res;

}

- sandeep gupta October 14, 2007 | Flag Reply
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.

- Ak67 April 17, 2008 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More