Microsoft Interview Question for Software Engineer / Developers
- 0of 0 votes
Round 4( 2h 30 min)- dutta.dipankar08 May 19, 2014 in India for MS Office Platform
Q1. You are given a Text, where all space, full stop and all punctuation mark is removed. You want to reconstruct the text by putting spaces between words.
A dict is given and following API < bool isInDect(word) > is also given.
a) Decide if the text can be converted a sentence with valid words or NOT.
b) Find how many way you can do the reconstruction of the text
c) Find what is the minimum number of space can be used for this reconstruction.
d) For case (c) find out the indexes where you suppose to put a space.
e) Now recover the text to sentence in place .
1. Why Greedy technique will not work for this
2. yes ! Backtracking will work, what is the problem of using backtracking
3. Illustrate and explain how the solution is contracted from the Dynamic table.
4. Write the correct working code for (c),(d),(e).
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
Interview Type: In-Person
Open Chat in New Window