Home

tekpool's blog

Greatest Common Divisor

Tue, 12/05/2006 - 01:05 — tekpool

Q: Find the greatest common divisor of 2 numbers a and b and also find 2 numbers x and y such that ax + by = GCD(a,b)

Sol:

Find the Common Node in Intersecting Linked Lists

Wed, 11/15/2006 - 22:19 — tekpool

Q: You are given two singly linked lists, such that they start from two different nodes (head) and then, a few nodes down the list, they meet at a common node and then share all the nodes henceforth until the tail. The task is to find the first common node.

Sol:

Buffer Overruns

Mon, 09/25/2006 - 07:50 — tekpool

Buffer Overruns is one of top sources of security issues today.  These are typically caused by trusting input data to a function that is external and is unchecked. Most of the times, this is unintentionally invoked by bad sloppy code. However, when done intentionally by a hacker, this can cause havoc. Some of the most common, buffer overrun prone functions include strcpy, memcpy, strcat etc... In unintentional buffer overruns, this mostly results in writing to memory not owned by your processes address space.

const Correctness: Difference between Foo* const ptr, const Foo* ptr, const Foo* const ptr

Thu, 09/14/2006 - 04:40 — tekpool
  • Foo* const ptr: ptr is a const pointer to a Foo Object. The Foo object can be changed using the pointer ptr, but you can't change the pointer ptr itself.
  • const Foo* ptr: ptr points to a Foo object that is const. The Foo object can't be changed via ptr.
  • const Foo* const ptr: ptr is a const pointer to a const Foo object. Neiher can the pointer ptr be changed, nor can you change the Foo object using ptr.

Reading the declaration right to left is a easy way to remember what they mean.

Constructors: Error / Exception Handling in Constructors

Wed, 08/09/2006 - 01:59 — tekpool

Constructors do not have return type and so they cannot return error codes. How are errors or exceptions handled in constructors? What if the calls that you make in the constructor can actually throw exceptions? How do you let the caller know something bad happened in a constructor?

There are a few ways to do robust error/exception handling in constructors

Swapping variables without additional space

Wed, 07/19/2006 - 23:06 — tekpool

Swapping variables is a very common operation used it tons of algorithms like sorting etc. The most common and obvious technique is using of a temporary variable to swap values between two variables

void swap(int &i, int &j)
{
   int temp = i;
   i = j;
   j = temp;
}

Instead of writing a separate function for each data type, you could write a MACRO or templatize the function.

Swapping without using a temporary variable is an age old trick and there are a few ways to do this. You could use of the basic arithmetic operations like +,-,/,*

Singleton Pattern: Part 3 Double Checked Locking

Mon, 06/12/2006 - 08:52 — tekpool

Singleton Pattern: Part 3 Double Checked Locking

Binary Tree Searching: Improving Search Performance with Sentinels

Thu, 06/08/2006 - 07:29 — tekpool

A normal search across a BST (Binary Search Tree) would look like this


bool BinaryTree::Search (int data )
{
	Node *current = this->root;

	while ( current != NULL )
	{
		if (current->data < data)
		{
			current = current->left;
		}
		else if (current->data > data)
		{
			current = current->right;
		}
		else if ( current->data == data )
		{
			return true;
		}
	}

  return false;
}

Binary Tree Traversal: Breadth First aka Width First aka Level Order

Thu, 06/01/2006 - 07:07 — tekpool

Binary Tree Traversal: Breadth First aka Width First aka Level Order

This is the lesser know of the different kinds of binary tree traversals. Most beginner books and articles only cover the depth first searches. Breadth first traversals are an extremely important tool when working with Binary Trees. The idea is pretty nifty. Basically you work with a Queue, and push the root node into the Queue. Then do the following until you have visited all nodes in the tree.

123next ›last »
Syndicate content