hnrqbaggio
BAN USER- 0of 0 votes
AnswersGiven a two dimensional matrix of booleans, there is a function that returns the number of "true regions".
A region is a group of True values aligned vertically or horizontally.T T <= 1 region T F T F <= 2 regions F T
Question 1: How would you test a function that solve this problem, but is written by another developer. How many tests cases do you see?
- hnrqbaggio in United States for Office
Question 2: Now write the code to solve this problem. What are the time and space complexities?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays Data Structures Debugging Microsoft Testing - 1of 1 vote
AnswersGiven a string, find the start position of the largest block of repeated charactes.
- hnrqbaggio in United States for Office
After the solution, I was asked to write down as many test cases I could to test the function as if it was created by someone else.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Microsoft String Manipulation Testing - 1of 1 vote
AnswersGiven two arrays of ints that are sets, create a function to merge them to create a new set.
- hnrqbaggio in United States for Office
A set must pass on these three conditions:
- All values are positive
- Sorted
- Non-duplicates| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays Data Structures Debugging Microsoft - 0of 0 votes
AnswersTell me if a array of integers is a set.
- hnrqbaggio in United States for Office
A set must pass on these three conditions:
- All values are positive
- Sorted
- Non-duplicates
After the first solution, I was asked about time and space complexity and to create 5 test cases for my function.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Algorithm Arrays Data Structures Debugging Microsoft
@SL: the note about a[i] == b[j] is correct, because otherwise you'll end up with duplicates on the merge resultn, and then the result size could be less and n + m.
- hnrqbaggio January 26, 2013You have to count the number of contiguous true values in the array. A region is formed by true values that are next to each other either horizontally or vertically but not on the diagonal.
Some other examples. Tell me if is still not clear. On the whiteboard I could drew the regions to be sure.
T T T T T <= 3 regions, the first one has horizontal and
F F F T F vertical values
T T F F F
F F F F T
T F T F <= 2 regions
T F T F
T F T F <= 2 regions - look at the diagonal
T F T T
F T T T
This question is a complement of this one: 15273751
- hnrqbaggio January 24, 2013
Good solution.
- hnrqbaggio February 07, 2013With the STL vector there isn't the problem of the find the size of the merged set, and the effect the vector reallocation on the time complexity is negligible.
But in this case it's worth to note that the resulting container's type is not the same of the inputs'.