Microsoft Interview Report
- 1of 1 vote
AnswersThis problem is called Maximum contiguous sub sequence sum problem. I have been asked this question more than once at different interviews at Microsoft.
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.
Here was my solution.
- Daniel Johnson February 07, 2009maxsofar = 0 maxendinghere = 0 for i = [0, n) /* invariant: maxendinghere and maxsofar are accurate are accurate for x[0..i-1] */ maxendinghere = max(maxendinghere + x[i], 0) maxsofar = max(maxsofar, maxendinghere)
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm - 0of 0 votes
AnswersA binary tree contain integer values (both positive and negative) in its data field. Given a number N, find a path from root to leaf which sums to N.
- Daniel Johnson February 07, 2009
bool ContainsSum(btree *root, int N)
It was simple. By doing a iterative pre-order traversal, and keeping tab of sum of elements, we can easily determine if sum of elements from root to any of the leaves is equals to N.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Data Structures - 1of 0 votes
AnswersYou are creating a calculator for a second grader kids.
- Daniel Johnson February 07, 2009
Write a function:
int Calculate(char *in)
where char *in is a string that contains an expression like: "1+2" or "-234334-345345" and you return the results accordingly. It is given that there would be two operands and an operator between them.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test C++ Object Oriented Design