Thursday, November 1, 2012

Efficient Data structure to store

Given a large number with many digits, propose a method or data structure to efficiently store them. Addition, subtraction, mult, division should be supported by your design.

Test type of triangle based on side lengths

Develop strategy and test type of triangle based on side lengths.

Strategy:
you're given sides a, b, and c.
let a <= b <= c.

for a = b = c, it's an equilateral tri.
for a = b < c or a < b = c, it's an isosceles tri.
for a < b < c, it's a scalene tri.

since we already said that a and b are the smallest 2 sides,
for a^2 + b^2 > c^2, it's an acute tri.
for a^2 + b^2 = c^2, it's a right tri.
for a^2 + b^2 < c^2, it's an obtuse tri.

equilateral triangle is always acute.
for a = b < c isosceles triangle, it IS an obtuse isosceles.
for a < b = c isosceles triangle, it IS an acute isosceles.

Also,

In an equilateral triangle, all three sides are the same length. An equilateral triangle is always equiangular.

In an isosceles triangle, two sides are the same length. An isosceles triangle may be right, obtuse, or acute.

In a scalene triangle, none of the sides are the same length. A scalene triangle may be right, obtuse, or acute.

In a right triangle, one of the angles is a right angle—an angle of 90 degrees. A right triangle may be isosceles or scalene.

In an obtuse triangle, one angle is greater than a right angle—it is more than 90 degrees. An obtuse triangle may be isosceles or scalene.

In an acute triangle, all angles are less than right angles—each one is less than 90 degrees. An acute triangle may be equilateral, isosceles, or scalene.

Writing Test Cases:
S.No.
Test case Name
Description
Expected Result
1
Check Scalene triangle
Enter input  as A=8, B=5 and C=7
Output should be scalene triangle
2
Check Scalene triangle
Enter input  as A=200, B=400 and C=900
Output should be scalene triangle
3
Check  isosceles triangle
Enter input  as A=8, B=10 and C=10
Output should be isosceles triangle
4
Check  isosceles triangle
Enter input  as A=800, B=700 and C=700
Output should be isosceles triangle
5
Check  equilateral triangle
Enter input  as A=15, B=15 and C=15
Output should be equilateral triangle
6
Check  equilateral triangle
Enter input  as A=190, B=190 and C=190
Output should be equilateral triangle
7
Check Negative values
Enter input  as A= -6, B=-15 and C=-14
Error message should be displayed
8
Check Negative values
Enter input  as A= 6, B=15 and C=-15
Error message should be displayed
9
Check Negative values
Enter input  as A= 6, B=-16 and C=-15
Error message should be displayed
10
Check Zero values
Enter input  as A= 6, B=16 and C=0
Error message should be displayed

Test a program that outputs factorial of a number

Given a simple program designed to take inputs of integers from 1-1000 and to output the factorial value of that number, how would you test this program? You do not have access to the code

Strategy:
This is a standard testing question. In professional world when you are testing anything, you are expected to automate the entire process. So in this case they do not expect you to check the factorial value returned each time. Rather first you have to write a routine that gives the correct factorial value for numbers between 1-1000. (There are no efficiency constraints)
Now you need to check for different test cases such as
1) It must return the correct value for the numbers in the range. You do not need to check for each number but can randomly pick 100 numbers (or whatever with the interviewer would be satisfied) from 1-1000 and check for them.
2) Then you must check what it gives for values out of the range and if it crashes or not.
3) You should also check for negative numbers and floating point. In all the cases the code should reject the input and not crash.

Try to think of as many as possible such test cases. Testing questions are an integral part of interviews because even if you are being selected for a Dev profile, you need to test your code thoroughly.
While answering testing questions you should be imaginative and speak out whatever weird condition/check that comes to your mind. They are testing you for your thoroughness and the understanding of what actually that code does.

Match two board configurations of tic-tac-toe problem

How will you match two board configurations of tic-tac-toe problem?

Strategy:

This is a quite unexpected interview question as it has nothing to do with your programming skills or algorithms. This is a plain simple question designed to check your problem solving skills.
The trick in this question is that any board configuration is rotation invariant and what we mean by that is

all three the configurations shown above are similar and must match in the logic we use for checking board configurations.
Any given configuration of the board can have 7 other configurations which will be identical to it in terms of rotation invariance. These can be obtained by rotating the matrix either left or right 4 times. And then taking the mirror image of the matrix and again rotating it.
So the entire problem breaks down to reducing the first board configuration to matrix and then rotating it one by one and matching it with the other configuration.
Rotation of the elements of a matrix can be done in multiple ways and we are going to discuss two methods here.
Method 1: Given a matrix we can take it's transpose and to rotate it left exchange the rows and to rotate right, exchange the columns.
           1) original matrix

             1 2 3

             4 5 6

             7 8 9

           2) transpose

             1 4 7

             2 5 8

             3 6 9

           3-a) change rows to rotate left

             3 6 9

             2 5 8

             1 4 7

           3-b) or change columns to rotate right

             7 4 1

             8 5 2

             9 6 3
Method 2: We can use the following pesudo-code which directly does the work which is being done while taking transpose and exchanging columns. This works for a given square matrix A of dimension NxN
  for n = 0 to N - 2
    for m = n + 1 to N - 1
        swap A(n,m) with A(m,n)

Test cases for overlap of rectangles

Given a function, func( rect a, rect b), which takes two rectangles as argument and tells if two rectangles overlap or not. Write all possible test cases for this.

Strategy:

This is a testing profile question asked by Microsoft in 2011. If you are being hired for testing profile you will face many such questions which aim at testing your ability to come up with interesting and unique test cases. You should think out of the box to suggest situations which can cause the function or a component to fail. If function responds correctly to all the cases, it is considered fit to be used.
Coming back to the question at hand, let's write all the test cases:
  1. Begin with the base cases i.e. putting NULL in place of either a, b or both. That means function must not fail if either of the arguments is empty. This is generally the case, since developers sometimes forget to keep check for this.
Next all the test cases are given with diagrams to make it easy to understand.
Test cases Test
cases
These are few test cases, there can be many more to this. But keep in mind to give the base or initial test case. That is from where interviewer judges your understanding and method you tackle the problem.