Posts Tagged ‘code’

Triangle Identification – C++ solution and test code

Tuesday, September 23rd, 2008

Here is another interview coding question that I have heard of.

You have to write a function to identify the triangle type. You have to return a number between 1 or 4 to identify either a valid triangle type or an error.

The solution is very simple requiring only one condensed line of code to identify each triangle type. Two lines of code identify error cases. One of the error cases identifies input with 0 or negative lengths. The other error case identifies line lengths that don’t make a triangle or which make a segment (thanks to Yabba for pointing out these error cases).

As an exercise you could try to extend the solution to identify right-angled triangles as well.

const int SCALENE = 1;
const int ISOSCELES = 2;
const int EQUILATERAL = 3;
const int ERROR = 4;
int TriangleType(int x, int y, int z)
{
	if ((x + y <= z) || (x + z <= y) || (z + y <= x)) return ERROR;
	if (x<=0 || y<=0 || z<=0) return ERROR;
	if (x == y && y == z) return EQUILATERAL;
	if (x == y || y == z || z == x) return ISOSCELES;
	return SCALENE;
}

The more interesting code comes from testing the function. To test the function I pass in a series of triangle side lengths. I also pass in the expected result. If the actual result matches the expected result then the test passes.

The test data is written in a way that allows each test to be defined in a single line of code which makes it very easy to extend.

This easy extendibility was fortunate as my original version of this solution missed out the cases where the line lengths don’t make a triangle (e.g. 1, 1, 5), and where the line lengths make a segment (e.g. 2, 2, 4).

void TriangleTest()
{
const int testDataSize = 14;
int testData[testDataSize][4] = {
	{9, 9, 9, EQUILATERAL},
	{4, 5, 5, ISOSCELES},
	{5, 4, 5, ISOSCELES},
	{5, 3, 3, ISOSCELES},
	{0, 0, 0, ERROR}, // 0 number checks
	{0, 1, 2, ERROR},
	{1, 0, 2, ERROR},
	{1, 2, 0, ERROR},
	{-1, -1, -1, ERROR}, // negative number checks
	{-1, 1, 2, ERROR},
	{1, -1, 2, ERROR},
	{1, 2, -1, ERROR},
	{2, 2, 4, ERROR}, // line segment not a triangle
	{1, 1, 5, ERROR} // not a triangle
};
for (int i=0; i<testDataSize; ++i)
{
	int result = TriangleType(
		testData[i][0], testData[i][1], testData[i][2]);
	if (result == testData[i][3])
	{
		cout << " Pass: triangleType("
			<< testData[i][0] << ", "
			<< testData[i][1] << ", "
			<< testData[i][2] << ")==" << result << endl;
	}
	else
	{
		cout << "!Fail: triangleType("
			<< testData[i][0] << ", "
			<< testData[i][1] << ", "
			<< testData[i][2] << ")==" << result
			<< " Expected: " << testData[i][3] << endl;
	}
}
}


Reverse a linked list – C++ source code

Monday, July 21st, 2008

Reversing a linked list is a simple programming problem, which is often an interview question. In this case I’m referring to a singly linked list. I’ll provide the C++ solution and the C++ test code.

One of the easiest ways to reverse the linked list is to create a new head pointer, iterate through the list removing each item in turn and then inserting them at the beginning of the new list.

Here is the definition of my linked list node and the code to reverse the list.

class Node
{
public:
	Node(int value) : value(value), next(NULL) {}
public:
	int value;
	Node* next;
};
Node* reverseList(Node* head)
{
	Node* newList = NULL;
	Node* current = head;
	while (current)
	{
		Node* next = current->next;
		current->next = newList;
		newList = current;
		current = next;
	}
	return newList;
}

Below is the code I used to test this. This is what it does:

  1. It creates a simple linked list.
  2. Prints it out – output should be ‘12345’.
  3. Reverses it.
  4. Prints it out – output should be ‘54321’.
  5. Reverses it again.
  6. Prints it – output should be ‘12345’.
  7. Deletes the list.
void listTests()
{
	Node* one = new Node(1);
	Node* two = new Node(2);
	Node* three = new Node(3);
	Node* four = new Node(4);
	Node* five = new Node(5);
	one->next = two;
	two->next = three;
	three->next = four;
	four->next = five;
	Node* head = one;
	printList(head);
	head = reverseList(head);
	printList(head);
	head = reverseList(head);
	printList(head);
	// cleanup memory
	Node* current = head;
	while (current)
	{
		Node* next = current->next;
		delete current;
		current = next;
	}
}
void printList(Node* head)
{
	Node* current = head;
	while (current)
	{
		cout << current->value;
		current = current->next;
	}
	cout << endl;
}

This should be the output:

12345
54321
12345

If you are interested in other linked list related code I have a post about picking the 5th from last element from a singly linked list, and one on selecting random numbers from a stream or linked list. Both of these are based on programming interview questions.