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
 Nonduplicates 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
 Nonduplicates
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

hnrqbaggio
January 24, 2013 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'.