Microsoft Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

Assuming the sentence consists of 26 alphabets(lowercase),take an array of size 26(bool)
-Set all the elements in array to 1 that are in the pattern (e.g. for x set 'x'-'a')
-Start parsing the sentence. If we get contiguous elements in the sentence till strlen(pattern) for which the corresponding element in array is set, return the starting location.
-else continue looking from the next element where we haven't found its corresponding element set in the array.
Time: O(n) Space: O(1) [Const]

- Anonymous November 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good one!

- KB September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can use modified version of Rabin-Karp algorithm to solve this. Basically if your hashing function is incremental and sorts the input (for small strings this is really O(1)) before calculating the hash then basically this problem reduces to just scanning the document and matching the hash.

- Ashish Kaila November 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

I did not get you. Can you please provide a bit detailed explanation. Sort the input. In the above example 'imt' is already sorted now if you match this with the content of the file. It will not get any match. But the word 'submitted' contains the match 'mit' which is one of the permutaion of imt.

- Anonymous November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Scan the input, keep track of last word index. Since the match is of 3 letters, For every next 3 letters compare its hash with that of the match. If they are equal return the last word index.

Not sure whether this is correct solution ? or high on time

- Anonymous November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why hash at all?

- eugene.yarovoi November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

to avoid checking whether next three letters r permutation of the match which might be expensive op.

- Anonymous November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hashing saves comparison time. Have a look at Rabin Karp algorithm. It uses incremental hash functions that can accommodate for sliding window problem in pattern matching. If you just modify the hash function so order of the characters do not matter then you are done.

- Ashish Kaila November 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There's a way to do this easily without hashing. Why not just, for each word, keep a sliding window of letter counts (use a map). You know the length of the search string (call it K). So start with that many letters in the word (count them using a map), then for each consecutive letter, add the next letter and subtract the letter K characters before in the string. If the map ever contains the exact characters in your search string, you've just matched the pattern. You can even avoid the O(K) map comparison each time by starting the map not empty but with the negative of the count of letters you're looking for. Then you just check if the map is empty each time (O(1)).

- eugene.yarovoi November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Eugene
I considered sliding window and that's why I suggested R-K algorithm. The map implementation will require you to compare n alphabets which is bad if strings differ by 1 letter in the worst case. Hash is fast and easy and you only compare n values if hashes match.

- Ashish Kaila December 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Solution of this problem using Rabin-Karp algorithm is very simple and optimistic. It only differs in one way from conventional brute force approach. In conventional brute force approach we will compare every substring with search string and find out the matches. But in Rabin-karp approach we just compare hash of both search string and substring and hash is nothing but assume just a sum of ascii values of characters of string.

So brute force approach produces complexity around O(nm) and with Rabin karp we can achieve O(n+m) which is significantly better.

One important optimization in Rabin Karp approach is computation of hash of a substring of length m in constant time. This is the only factor which let it achieve complexity of O(n+m) instead of O(nm).

- vikas maan November 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Vikas: I doubt if a plain Rabin-Karp algorithm will work. The question does talk about finding the permutation of the sequence in the given sentence. Don't we have to sort the sentence and the sequence in the alphabetical order before applying Rabin-Karp algorithm?

- nithish.m November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think Robin Carp is good algorithm. But it has a disadvantage where sum of ASCII code can be same for some other characters for ex. if the pattern is "is" hash of this word is same as with "om".
Please comment if you disagree.

- @Akash September 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How about XOR? Just XOR all characters in 'mit' (one occurrence during sliding-window) with all characters of the pattern 'imt'. If the result of XOR is 0, then we get a match. No need to permute. Every character in 'mit' will XOR out characters in 'imt'.

- neer300 January 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This qns is very similar to the one which requires finding the smallest substring containing all the characters of a given string (very well known qns). So, just scan the whole doc take each word and perform the above operation.

- Nascent Coder November 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anagram Finder..

- jackass November 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Nscent wrong approach here is a counter example.
the string is abcdefghi and the word to be searched is cef

now ur approach give the cdef which is the smallest substring containing cef which is wrong.

- kamal November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Kamal, the solution provided by Nascent just needs a little improvement.
Improvement: In the end if length of searching pattern matches that of a substring containing all the characters then you can say that you found the relevant word.
One more thing to add, that algo was on a word to search, here we have to search in sentence on words.... so more improvement required.

- Skataria November 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Kamal, the solution provided by Nascent just needs a little improvement.
Improvement: In the end if length of searching pattern matches that of a substring containing all the characters then you can say that you found the relevant word.
One more thing to add, that algo was on a word to search, here we have to search in sentence on words.... so more improvement required.

- Skataria November 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't we feed the permutaions of string to suffix tries. and check if it leading to some branch or not

- bharat July 25, 2013 | 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