Microsoft
Greatest Common Divisor
Tue, 12/05/2006 - 01:05 — tekpoolQ: 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:
Singleton Pattern: Part 3 Double Checked Locking
Mon, 06/12/2006 - 08:52 — tekpoolSingleton Pattern: Part 3 Double Checked Locking
Binary Tree Searching: Improving Search Performance with Sentinels
Thu, 06/08/2006 - 07:29 — tekpoolA 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 — tekpoolBinary 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.
Singleton Pattern: Part 2 Thread-Safe implemenation
Mon, 04/17/2006 - 05:43 — tekpoolSingleton Pattern: Part 2 Thread-Safe implemenation
We looked into a trivial implementation of the singleton pattern in the previous post. The implementation was both lazy and non-thread safe. It’s lazy, because the singleton instance is created only when it’s required. The implementation was also not thread safe. So, if several calls were made into this method from a multi-threaded program, you could end up creating multiple instances of the class, and also mess up seriously since the system expects to have only one instance.
Singleton Pattern: Part 1 Trivial implemenation
Fri, 04/07/2006 - 08:07 — tekpoolSingleton Pattern: Part 1 Trivial implemenation
The purpose of a singleton pattern is to ensure a unique instance of the class and to provide global access to this. It falls under the Creational patterns category.
The class implementing the singleton pattern will have to do the following items:
- Provide an Instance Creation Method to the user.
- Maintain the unique instance throughout the life of the program(s) in which this class is created.
String Pattern Matching: Write a function that checks for a given pattern at the end of a given string
Sun, 12/11/2005 - 05:14 — tekpoolString Pattern Matching: Write a function that checks for a given pattern at the end of a given string
In other words, Write a function, a variant of strstr that takes in 2 strings str1 and str2 and returns true if str2 occurs at the end of the string str1, and false otherwise.
bool str_str_end(char * str1, char * str2)
{
// Store the base pointers of both strings
char* beginStr1 = str1;
char* beingStr2 = str2;
// Move to the end of the strings
while(*str1++);
while(*str2++);
Rectangle Intersection - Find the Intersecting Rectangle
Fri, 12/02/2005 - 10:18 — tekpoolQ: Rectangle Intersection - Find the Intersecting Rectangle
In the last post, we looked into methods to determine whether or not two given rectangles intersect each other. Lets go one step ahead this time and find the intersecting rectangle.
As in the previous post, I am basing the struct off of the Windows co-ordinate space, where the origin is on the top left of the screen. The x-axis moves towards the right and the y-axis moves towards the bottom.
Rectangle Intersection - Determine if two given rectangles intersect each other or not
Tue, 11/29/2005 - 04:09 — tekpoolQ: Rectangle Intersection: Determine if two given rectangles intersect each other or not
Definitions:
Intersect: Two Rectangles intersect each other if the share a common area.
Assumptions:
- Both the rectangles are aligned with the x and y axes.
- Rectangles just touching each other are considered as non-intersecting.
