## Microsoft Interview Question for Software Engineer / Developers

Team: MS Office Platform
Country: India
Interview Type: In-Person

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

dyanamic programming word-break-problem

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

Lets say the string has N characters and we can search a substring from positions i to j in the dictionary in O(1) using the given function.

a) Create a boolean array V of size N and initialize its elements to false, except V[N] = true. Traverse the positions from end to beginning. V[i] will be true if we can reach position N from position i. We check all positions j (j > i) such that characters i..j-1 form a word from the dictionary. If V[j] is true, so is V[i]. The text can be converted if we reach position N. The time complexity is O(N^2). Space complexity is O(N).

b) Very similar to a) except that V will count the number of ways we can reach position N from i. V[N] is 1 and we sum the number of ways, V[j], for each valid j > i. The time complexity is O(N^2). Space complexity is O(N).

c) Very similar to b) except that we don't sum, but take the minimum. V[i] = min(V[j]+1) for all valid j or infinity if there is no valid j.

d) Save in an additional array Next the index of the minimum for each position.

e) Traverse Next, starting from 0 and jumping to the next position.

1) Greedy approaches will take a local optimum and may fail to find an existing solution. Simple example: string = "aab", dict = {"a", "aa", "ab"}. There is a solution "a ab" but the most common greedy algorithm will pick "aa" first and not find a solution because there is no "b" in dict.

2) Backtracking works but is extremely slow. There are 2^N possible splits and it would explore them all, yielding a O(2^N) solution.

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

Solution for c) part of the problem

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

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.

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

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