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:
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 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
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:
String 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++);
Q: 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.
Q: 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:
Q: Shuffling - Shuffle a deck of cards – Knuth Shuffle
Shuffling is a process where the order of elements in a data set is randomized to provide an element of chance. One of the most common applications of this is to shuffle a deck of cards.
Mathematically, the shuffling problem, is basically a problem of computing a random permutation of N objects, since shuffling a deck of cards is basically subjecting a deck of cards to a random permutation.
Q: Finding the first N Primes
Q: Finding the first N Primes
In the last post we looked into making some improvements over Trivial Approaches