Google Interview Question
SDE-2sCountry: United States
I think there is a way to do this with exclusive or but here is better but obviously not the best way:
public static int findTriangleType(int[] sideLengths) {
if(sideLengths.length != 3) {
return 4;
}
boolean pair1 = sideLengths[0] == sideLengths[1];
boolean pair2 = sideLengths[1] == sideLengths[2];
boolean pair3 = sideLengths[2] == sideLengths[0];
if(pair1 && pair2 && pair3) {
return 3;
}
else if (!pair1 && !pair2 && !pair3) {
return 1;
}
return 2;
}
Required test cases may include (100, 1, 2), (-2, -3, -4) and your solution will return 1 although they can't be triangle.
The first line of your code should be
if(sideLengths.length == 3 &&
sideLengths[0] > 0 && sideLengths[1] > 0 && sideLengths[2] > 0 &&
sideLengths[0] + sideLengths[1] > sideLengths[2] && sideLengths[1] + sideLengths[2] > sideLengths[0] && sideLengths[2] + sideLengths[0] > sideLengths[1]) { ...
and as you can see above, making variables have shorter name or assign them to variables (int a = sideLengths[0] etc.) may help.
Suppose the integers are a, b and c.
(1)int arr[3]; arr[0] = a; arr[1] = b; arr[2] = c;
(2)if(arr[0] > arr[1]) swap(arr, 0, 1);
if(arr[1] > arr[2]) swap(arr, 1, 2);
if(arr[0] > arr[1]) swap(arr, 0, 1);
(3)if(arr[0] <= 0 || arr[2] >= arr[0]+arr[1]) return error;
if(arr[0] == arr[1]){
if(arr[1] == arr[2]) return equilateral;
else return isosceles;
}
else if(arr[1] == arr[2]) return isosceles;
else return scalene;
triangle type detection code:
#include <algorithm>
int triangleType(int a, int b, int c)
{
enum ERet{
scalene = 1,
isosceles = 2,
equilateral = 3,
error = 4
};
if(a <= 0 || b <= 0 || c <= 0)
return error;
if(a == b && a == c)
return equilateral;
//sort a >= b >= c
if(a < b)
std::swap(a, b);
if(a < c)
std::swap(a, c);
if(b < c)
std::swap(b, c);
if(a - b >= c)
return error;
if(a == b || b == c)
return isosceles;
return scalene;
}
The test code is
#include <iostream>
int main()
{
//genTests();
const int kTestCase[][4] = { //generated by genTests()
{-1, -1, -1, 4},
{-1, -1, 0, 4},
{-1, -1, 1, 4},
{-1, -1, 2, 4},
{-1, -1, 3, 4},
{-1, -1, 4, 4},
{-1, 0, -1, 4},
{-1, 0, 0, 4},
{-1, 0, 1, 4},
{-1, 0, 2, 4},
{-1, 0, 3, 4},
{-1, 0, 4, 4},
{-1, 1, -1, 4},
{-1, 1, 0, 4},
{-1, 1, 1, 4},
{-1, 1, 2, 4},
{-1, 1, 3, 4},
{-1, 1, 4, 4},
{-1, 2, -1, 4},
{-1, 2, 0, 4},
{-1, 2, 1, 4},
{-1, 2, 2, 4},
{-1, 2, 3, 4},
{-1, 2, 4, 4},
{-1, 3, -1, 4},
{-1, 3, 0, 4},
{-1, 3, 1, 4},
{-1, 3, 2, 4},
{-1, 3, 3, 4},
{-1, 3, 4, 4},
{-1, 4, -1, 4},
{-1, 4, 0, 4},
{-1, 4, 1, 4},
{-1, 4, 2, 4},
{-1, 4, 3, 4},
{-1, 4, 4, 4},
{0, -1, -1, 4},
{0, -1, 0, 4},
{0, -1, 1, 4},
{0, -1, 2, 4},
{0, -1, 3, 4},
{0, -1, 4, 4},
{0, 0, -1, 4},
{0, 0, 0, 4},
{0, 0, 1, 4},
{0, 0, 2, 4},
{0, 0, 3, 4},
{0, 0, 4, 4},
{0, 1, -1, 4},
{0, 1, 0, 4},
{0, 1, 1, 4},
{0, 1, 2, 4},
{0, 1, 3, 4},
{0, 1, 4, 4},
{0, 2, -1, 4},
{0, 2, 0, 4},
{0, 2, 1, 4},
{0, 2, 2, 4},
{0, 2, 3, 4},
{0, 2, 4, 4},
{0, 3, -1, 4},
{0, 3, 0, 4},
{0, 3, 1, 4},
{0, 3, 2, 4},
{0, 3, 3, 4},
{0, 3, 4, 4},
{0, 4, -1, 4},
{0, 4, 0, 4},
{0, 4, 1, 4},
{0, 4, 2, 4},
{0, 4, 3, 4},
{0, 4, 4, 4},
{1, -1, -1, 4},
{1, -1, 0, 4},
{1, -1, 1, 4},
{1, -1, 2, 4},
{1, -1, 3, 4},
{1, -1, 4, 4},
{1, 0, -1, 4},
{1, 0, 0, 4},
{1, 0, 1, 4},
{1, 0, 2, 4},
{1, 0, 3, 4},
{1, 0, 4, 4},
{1, 1, -1, 4},
{1, 1, 0, 4},
{1, 1, 1, 3},
{1, 1, 2, 4},
{1, 1, 3, 4},
{1, 1, 4, 4},
{1, 2, -1, 4},
{1, 2, 0, 4},
{1, 2, 1, 4},
{1, 2, 2, 2},
{1, 2, 3, 4},
{1, 2, 4, 4},
{1, 3, -1, 4},
{1, 3, 0, 4},
{1, 3, 1, 4},
{1, 3, 2, 4},
{1, 3, 3, 2},
{1, 3, 4, 4},
{1, 4, -1, 4},
{1, 4, 0, 4},
{1, 4, 1, 4},
{1, 4, 2, 4},
{1, 4, 3, 4},
{1, 4, 4, 2},
{2, -1, -1, 4},
{2, -1, 0, 4},
{2, -1, 1, 4},
{2, -1, 2, 4},
{2, -1, 3, 4},
{2, -1, 4, 4},
{2, 0, -1, 4},
{2, 0, 0, 4},
{2, 0, 1, 4},
{2, 0, 2, 4},
{2, 0, 3, 4},
{2, 0, 4, 4},
{2, 1, -1, 4},
{2, 1, 0, 4},
{2, 1, 1, 4},
{2, 1, 2, 2},
{2, 1, 3, 4},
{2, 1, 4, 4},
{2, 2, -1, 4},
{2, 2, 0, 4},
{2, 2, 1, 2},
{2, 2, 2, 3},
{2, 2, 3, 2},
{2, 2, 4, 4},
{2, 3, -1, 4},
{2, 3, 0, 4},
{2, 3, 1, 4},
{2, 3, 2, 2},
{2, 3, 3, 2},
{2, 3, 4, 1},
{2, 4, -1, 4},
{2, 4, 0, 4},
{2, 4, 1, 4},
{2, 4, 2, 4},
{2, 4, 3, 1},
{2, 4, 4, 2},
{3, -1, -1, 4},
{3, -1, 0, 4},
{3, -1, 1, 4},
{3, -1, 2, 4},
{3, -1, 3, 4},
{3, -1, 4, 4},
{3, 0, -1, 4},
{3, 0, 0, 4},
{3, 0, 1, 4},
{3, 0, 2, 4},
{3, 0, 3, 4},
{3, 0, 4, 4},
{3, 1, -1, 4},
{3, 1, 0, 4},
{3, 1, 1, 4},
{3, 1, 2, 4},
{3, 1, 3, 2},
{3, 1, 4, 4},
{3, 2, -1, 4},
{3, 2, 0, 4},
{3, 2, 1, 4},
{3, 2, 2, 2},
{3, 2, 3, 2},
{3, 2, 4, 1},
{3, 3, -1, 4},
{3, 3, 0, 4},
{3, 3, 1, 2},
{3, 3, 2, 2},
{3, 3, 3, 3},
{3, 3, 4, 2},
{3, 4, -1, 4},
{3, 4, 0, 4},
{3, 4, 1, 4},
{3, 4, 2, 1},
{3, 4, 3, 2},
{3, 4, 4, 2},
{4, -1, -1, 4},
{4, -1, 0, 4},
{4, -1, 1, 4},
{4, -1, 2, 4},
{4, -1, 3, 4},
{4, -1, 4, 4},
{4, 0, -1, 4},
{4, 0, 0, 4},
{4, 0, 1, 4},
{4, 0, 2, 4},
{4, 0, 3, 4},
{4, 0, 4, 4},
{4, 1, -1, 4},
{4, 1, 0, 4},
{4, 1, 1, 4},
{4, 1, 2, 4},
{4, 1, 3, 4},
{4, 1, 4, 2},
{4, 2, -1, 4},
{4, 2, 0, 4},
{4, 2, 1, 4},
{4, 2, 2, 4},
{4, 2, 3, 1},
{4, 2, 4, 2},
{4, 3, -1, 4},
{4, 3, 0, 4},
{4, 3, 1, 4},
{4, 3, 2, 1},
{4, 3, 3, 2},
{4, 3, 4, 2},
{4, 4, -1, 4},
{4, 4, 0, 4},
{4, 4, 1, 2},
{4, 4, 2, 2},
{4, 4, 3, 2},
{4, 4, 4, 3},
{0x7ffffffd, 0x7ffffffd, 0x7ffffffd, 3},
{0x7ffffffd, 0x7ffffffd, 0x7ffffffe, 2},
{0x7ffffffd, 0x7ffffffd, 0x7fffffff, 2},
{0x7ffffffd, 0x7ffffffd, 0x80000000, 4},
{0x7ffffffd, 0x7ffffffe, 0x7ffffffd, 2},
{0x7ffffffd, 0x7ffffffe, 0x7ffffffe, 2},
{0x7ffffffd, 0x7ffffffe, 0x7fffffff, 1},
{0x7ffffffd, 0x7ffffffe, 0x80000000, 4},
{0x7ffffffd, 0x7fffffff, 0x7ffffffd, 2},
{0x7ffffffd, 0x7fffffff, 0x7ffffffe, 1},
{0x7ffffffd, 0x7fffffff, 0x7fffffff, 2},
{0x7ffffffd, 0x7fffffff, 0x80000000, 4},
{0x7ffffffd, 0x80000000, 0x7ffffffd, 4},
{0x7ffffffd, 0x80000000, 0x7ffffffe, 4},
{0x7ffffffd, 0x80000000, 0x7fffffff, 4},
{0x7ffffffd, 0x80000000, 0x80000000, 4},
{0x7ffffffe, 0x7ffffffd, 0x7ffffffd, 2},
{0x7ffffffe, 0x7ffffffd, 0x7ffffffe, 2},
{0x7ffffffe, 0x7ffffffd, 0x7fffffff, 1},
{0x7ffffffe, 0x7ffffffd, 0x80000000, 4},
{0x7ffffffe, 0x7ffffffe, 0x7ffffffd, 2},
{0x7ffffffe, 0x7ffffffe, 0x7ffffffe, 3},
{0x7ffffffe, 0x7ffffffe, 0x7fffffff, 2},
{0x7ffffffe, 0x7ffffffe, 0x80000000, 4},
{0x7ffffffe, 0x7fffffff, 0x7ffffffd, 1},
{0x7ffffffe, 0x7fffffff, 0x7ffffffe, 2},
{0x7ffffffe, 0x7fffffff, 0x7fffffff, 2},
{0x7ffffffe, 0x7fffffff, 0x80000000, 4},
{0x7ffffffe, 0x80000000, 0x7ffffffd, 4},
{0x7ffffffe, 0x80000000, 0x7ffffffe, 4},
{0x7ffffffe, 0x80000000, 0x7fffffff, 4},
{0x7ffffffe, 0x80000000, 0x80000000, 4},
{0x7fffffff, 0x7ffffffd, 0x7ffffffd, 2},
{0x7fffffff, 0x7ffffffd, 0x7ffffffe, 1},
{0x7fffffff, 0x7ffffffd, 0x7fffffff, 2},
{0x7fffffff, 0x7ffffffd, 0x80000000, 4},
{0x7fffffff, 0x7ffffffe, 0x7ffffffd, 1},
{0x7fffffff, 0x7ffffffe, 0x7ffffffe, 2},
{0x7fffffff, 0x7ffffffe, 0x7fffffff, 2},
{0x7fffffff, 0x7ffffffe, 0x80000000, 4},
{0x7fffffff, 0x7fffffff, 0x7ffffffd, 2},
{0x7fffffff, 0x7fffffff, 0x7ffffffe, 2},
{0x7fffffff, 0x7fffffff, 0x7fffffff, 3},
{0x7fffffff, 0x7fffffff, 0x80000000, 4},
{0x7fffffff, 0x80000000, 0x7ffffffd, 4},
{0x7fffffff, 0x80000000, 0x7ffffffe, 4},
{0x7fffffff, 0x80000000, 0x7fffffff, 4},
{0x7fffffff, 0x80000000, 0x80000000, 4},
{0x80000000, 0x7ffffffd, 0x7ffffffd, 4},
{0x80000000, 0x7ffffffd, 0x7ffffffe, 4},
{0x80000000, 0x7ffffffd, 0x7fffffff, 4},
{0x80000000, 0x7ffffffd, 0x80000000, 4},
{0x80000000, 0x7ffffffe, 0x7ffffffd, 4},
{0x80000000, 0x7ffffffe, 0x7ffffffe, 4},
{0x80000000, 0x7ffffffe, 0x7fffffff, 4},
{0x80000000, 0x7ffffffe, 0x80000000, 4},
{0x80000000, 0x7fffffff, 0x7ffffffd, 4},
{0x80000000, 0x7fffffff, 0x7ffffffe, 4},
{0x80000000, 0x7fffffff, 0x7fffffff, 4},
{0x80000000, 0x7fffffff, 0x80000000, 4},
{0x80000000, 0x80000000, 0x7ffffffd, 4},
{0x80000000, 0x80000000, 0x7ffffffe, 4},
{0x80000000, 0x80000000, 0x7fffffff, 4},
{0x80000000, 0x80000000, 0x80000000, 4}
};
for(int i = 0;i < sizeof kTestCase / sizeof kTestCase[0];++i)
if(kTestCase[i][3] != triangleType(kTestCase[i][0], kTestCase[i][1], kTestCase[i][2]))
std::cerr<<"triangle ["<<kTestCase[i][0]<<", "<<kTestCase[i][1]
<<", "<<kTestCase[i][2]<<"] is not "<<kTestCase[i][3]<<"\n";
}
All the test cases is generated by the following code
//generate test cases
void genTests()
{
//test case
for(int a = -1;a <= 4; ++a)
for(int b = -1;b <= 4; ++b)
for(int c = -1;c <= 4; ++c){
std::cout<<"{"<<a<<", "<<b<<", "<<c<<", "
<<triangleType(a, b, c)<<"},\n";
}
const int kMax = 0x7FFFFFFF;
for(int a = -2;a <= 1; ++a)
for(int b = -2;b <= 1; ++b)
for(int c = -2;c <= 1; ++c){
std::cout<<std::hex<<"{0x"<<(a + kMax)<<", 0x"<<(b + kMax)<<", 0x"<<(c + kMax)<<", "
<<triangleType(a + kMax, b + kMax, c + kMax)<<"},\n";
}
}
To see if it is an impossible triangle (or error): we need to check, for all sides, if one side of a triangle is less than the sum of the other two sides. If the check fails for any side, return error.
- Anonymous December 19, 2013Otherwise, put all sides into a hashmap and check the size.
If size = 3, return scalene
If size = 2 return isoceles
If size = 1 return equilateral
Also check for edge cases and things like negative integer values, non-integer inputs etc...