code / Common Tail

Find the common tail of two lists in C, for a job interview

Download

I was recently asked to complete some code questions for a job interview. The first question was worded slightly confusingly, but it involved an ancestor tree, where each leaf node had a pointer to the parent node. By following the pointers from any leaf, you would eventually end up at the ancestor node for the entire tree. So exactly the opposite of a directory tree. In fact, the entire tree is a collection of linked lists with a common tail.

The challenge was to find the first common parent of any two leaf nodes. What this boils down to is finding the common tail of two linked lists, which is a typical student assignment. It gets a bit more complicated in C, But then there are also some fun optimisations available in C. I'll get to that next post.

The standard way to solve this common-tail-of-linked-lists problem is to get the length of both lists, chop the front off the longer list to make both lists the same length, then walk along them comparing the elements pairwise from both lists. If any of the elements are equal, then the two lists merge, and they have a common tail (and thus the leaves have a common ancestor).

There are some issues with this naive approach, like the fact that getting the length of a linked list requires us to visit every element of the list. This means we walk along each list twice. This is a problem for long lists, and it is also not the absolute best solution, which is an important consideration for getting job interviews!

The task also had an extra condition: I couldn't declare any new Classes (the task was actually for java programmers), and I couldn't modify any existing classes. I interpreted that to mean no new structures in C, and not changing the provided structure, which heavily limited my possible answers.

So here it is, the simple, rather dull way of doing it. Next up, I make it a bit faster, and much more confusing.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/*One item in the linked list*/
typedef struct TreeNodeStruct { 
	struct TreeNodeStruct* parent;
} TreeNode;

/*Return the length of the linked list*/
int branchLength ( TreeNode* A) {
	int lengthA;
	for (lengthA=1; A->parent!=NULL; A=A->parent) {
		lengthA++;
	}

	return lengthA;
}

/* Move along the linked list by <length> elements */
TreeNode* drop (TreeNode* T, int length) {
	int i;

	for (i=0; i<length; i++) {
		T=T->parent;
	}

	return T;
}

/* Take two leaf nodes, traverse towards the root node until we find a common node (if any) */
TreeNode* findFirstCommonAncestor (TreeNode* A, TreeNode* B) {
	int lengthA,lengthB, diff;
	TreeNode* C;

	if (!(A&&B)){return NULL;}

	lengthA = branchLength(A);
	lengthB = branchLength(B);
	diff = lengthA-lengthB;

	/*Drop the front of the longest list to make both lists the same length */
	if (diff>=0) {
		A=drop(A,diff);
	} else {
		B=drop(B,-diff);
	}
	
	/* Now compare the lists element by element.  If the elements are the same, we have found the common ancestor */
	for (A=A; A!=NULL; A=A->parent) {
		if (A==B) { return A;}
		B=B->parent;
	}
	return NULL;
}

/* Test function: Create a linked list to test our functions on */

TreeNode* makeBranch (TreeNode* parent, int length) {
	int i;
	TreeNode* t;
	TreeNode* prev_t = parent;

	for (i=0;i<length; i++) {
		t = (TreeNode*) calloc(1,sizeof(TreeNode));
		t->parent = prev_t;
		prev_t=t;
	}
	return t;
}

void test () {

	TreeNode* R = (TreeNode*) calloc(1,sizeof(TreeNode));
	TreeNode* Rbranch = makeBranch(R,200);
	TreeNode* A = makeBranch(NULL, 10);
	TreeNode* B = makeBranch(NULL, 5);
	TreeNode* C = makeBranch(R, 10);
	TreeNode* D = makeBranch(R, 5);
	TreeNode* E = makeBranch(Rbranch, 1000);
	TreeNode* F = makeBranch(Rbranch, 500);

	int i;
	for (i=0; i<1000000; i++) {

		//Check we handle NULL correctly
		TreeNode* res = findFirstCommonAncestor(NULL, NULL);
		assert(res==NULL);
		
		//Check branches from different trees (no common root)
		res = findFirstCommonAncestor(A,B);
		assert(res==NULL);

		//Check branches are separate up to the tree root
		res = findFirstCommonAncestor(C,D);
		assert(res==R);

		//Check degenerate case
		res = findFirstCommonAncestor(R,R);
		assert(res==R);

		//Check a real case
		res = findFirstCommonAncestor(E,F);
		assert(res==Rbranch);

		//Check branchLength(B)>branchLength(A)
		res = findFirstCommonAncestor(F,E);
		assert(res==Rbranch);
	}
}


int main(int argc, char* argv[])
{
		test();
}