Flood Fill Algorithm

Flood Fill Algorithm

We might have encountered this at many places. Paint tool is one such example, when we say fill with color in paint, it fills the neighboring areas with the same color.
For examples in the below image when we do a fill color on the white area, we would want all the neighboring white areas to be colored.

The algorithm is very simple. We start with the user selected grid, fill it with color and then check the top, bottom, right and left grid and fill them as well. We do this recursively to achieve the end result.

Below is the procedure

floodFill(vector<vector<int>grid>, x, y, oldColor, newColor)

• If x or y is outside the grid, then return.
• If color of grid[x][y] is not same as oldColor, then return
• do the same for top, down, right and left.

    floodFillUtil(grid, x+1, y, oldColor, newColor);
    floodFillUtil(grid, x-1, y, oldColor, newColor);
    floodFillUtil(grid, x, y+1, oldColor, newColor);
    floodFillUtil(grid, x, y-1, oldColor, newColor); 

Lets see a C++ implementation for this algorithm

	#include<vector>
	#include<iostream>
	using namespace std;
	void floodFill(vector<vector<int>>&grid, int x, int y, int oldColor, int newcolor)
	{
	//check boundary conditions
	if (x < 0 || y < 0 || x >= grid.size() || y >= grid.size())
	return;
	//check if current point is previouscolor
	if (grid[x][y] != oldColor)
	return;
	if (grid[x][y] == newcolor)
	return;
	grid[x][y] = newcolor;
	//left
	floodFill(grid,x-1,y,oldColor, newcolor);
	//right
	floodFill(grid, x +1, y, oldColor, newcolor);
	//top
	floodFill(grid, x, y -1, oldColor, newcolor);
	//bottom
	floodFill(grid, x, y + 1, oldColor, newcolor);
	}
	void printgrid(vector<vector<int>>&grid)
	{
	for (int x = 0; x < grid.size(); x++)
	{
	for (int y = 0; y < grid.size(); y++)
	{
	cout << grid[x][y];
	}
	cout << endl;
	}
	}
	int main()
	{
	vector<vector<int>>grid =
	{
	{ 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 1, 0, 0 },
	{ 1, 0, 0, 1, 1, 0, 1, 1 },
	{ 1, 2, 2, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 2, 2, 0 },
	{ 1, 1, 1, 1, 1, 2, 1, 1 },
	{ 1, 1, 1, 1, 1, 2, 2, 1 },
	};
	int x = 4;
	int y = 4;
	printgrid(grid);
	//convert all 2s to 9
	floodFill(grid,x,y,grid[x][y],9);
	printgrid(grid);
	return 0;
	}

view raw FloodFill.cpp hosted with ❤ by GitHub

Multithreading:6.Print odd and even numbers using two threads

In this program we are going to look into how to print odd numbers using one thread and even numbers using another thread, the numbers have to be printed in order.
In the below code we have added two methods one to print odd numbers and the other to print even numbers, we call one from t1 and another from t2.

	#include <iostream>
	#include <string>
	#include <thread>
	#include <mutex>
	#include <condition_variable>
	using namespace std;
	std::mutex mu;
	std::condition_variable cv;
	std::string data;
	bool odddone = false;
	bool evendone = true;
	int num = 0;//lets start the number with 0;
	void print_odd()
	{
	while (num < 100)
	{
	// Wait until main() sends data
	unique_lock<mutex> lock(mu);
	cv.wait(lock, [] {return evendone; });//wait till evendone is made true by main thread
	//thread is adding numbers to data
	cout << ++num << endl;
	// Send data back to main()
	odddone = true;
	evendone = false;
	// Manual unlocking is done before notifying, to avoid waking up
	// the waiting thread only to block again
	lock.unlock();
	cv.notify_all();
	}
	}
	void print_even()
	{
	while (num < 100)
	{
	// Wait until main() sends data
	unique_lock<mutex> lock(mu);
	cv.wait(lock, [] {return odddone; });//wait till evendone is made true by main thread
	//thread is adding numbers to data
	cout << ++num << endl;
	// Send data back to main()
	evendone = true;
	odddone = false;
	//unlocking before notifying
	lock.unlock();
	cv.notify_all();
	}
	}
	int main()
	{
	thread t1(print_odd);
	thread t2(print_even);
	t1.join();
	t2.join();
	return 1;
	}

view raw oddevenmultithread.cpp hosted with ❤ by GitHub

Multithreading:5.condition_variable

Many a times we would want a thread to execute some commands based on some conditions. For this we are going to use std:: condition_variable. This class methods such wait, notify which would either make a thread wait or notify other threads. That is exactly the functionality we would need.

To go into code, we would want to understand to basic methods in the class std::condition_variable. One is wait and the other is notify

Wait 
void wait( std::unique_lock<std::mutex>& lock );
lock:an object of type std::unique_lock<std::mutex>, which must be locked by the current thread. Need not be locked till notify

template< class Predicate >
void wait( std::unique_lock<std::mutex>& lock, Predicate pred );
Pred: predicate which returns ​false if the waiting should be continued.

Notify
void notify_all() noexcept;
Unblocks all threads currently waiting for *this.

In the below code we want the main thread to print abcdef and the thread t1 to print 123456.
For this to happen, we want the main thread to start printing the alphabets and t1 to wait till the main completes its job. And we need some variable to tell that the main is done with this job, in this case we are using a bool alphadone.

	#include <iostream>
	#include <string>
	#include <thread>
	#include <mutex>
	#include <condition_variable>
	std::mutex mu;
	std::condition_variable cv;
	std::string data;
	bool alphadone = false;
	bool numericdone = false;
	void print_number()
	{
	// Wait until main() sends data
	std::unique_lock<std::mutex> lk(mu);
	cv.wait(lk, [] {return alphadone; });//wait till alphadone is made true by main thread
	//thread is adding numbers to data
	data += " 123456";
	// Send data back to main()
	numericdone = true;
	// Manual unlocking is done before notifying, to avoid waking up
	// the waiting thread only to block again
	lk.unlock();
	cv.notify_one();
	}
	int main()
	{
	std::thread t1(print_number);
	//main is adding alphabets to data
	data = "abcdef";
	// send data to the t1 thread
	{
	//print_number thread will wait till alphadone is made true
	std::lock_guard<std::mutex> lk(mu);
	alphadone = true;
	}
	cv.notify_all();
	// wait for print_number
	{
	std::unique_lock<std::mutex> lk(mu);
	cv.wait(lk, [] {return numericdone; }); //wait for numericdone to be made true
	}
	std::cout << data << '\n';
	t1.join();
	return 1;
	}

view raw conditional_variable.cpp hosted with ❤ by GitHub

Multithreading:4.Deadlock

Suppose we want to protect our resource doubly and we introduce two mutex to guard the resource.
Here in the below code we are locking m1 first in thread t1 and m2 first in thread t2. Now to lock m2 in thread t1 it will be waiting for t2 to unlock, which never happens. That is a deadlock situation.

	#include<thread>
	#include<mutex>
	#include<iostream>
	using namepspace std;
	void print(const std::string &s)
	{
	cout << s << endl;
	}
	int main() {
	std::mutex m1;
	std::mutex m2;
	std::thread t1([&] {
	print("From T1");
	m1.lock(); //locking m1 first
	print("From T1");
	m2.lock(); //locking m2 second
	});
	std::thread t2([&] {
	print("From T2");
	m2.lock(); //lcoking m2 first
	print("From T2");
	m1.lock(); //locking m1 second
	});
	t1.join();
	t2.join();
	}

view raw deadlock.cpp hosted with ❤ by GitHub

To avoid this situation

• Prefer locking single mutex at a time 
• Avoid locking a mutex and then calling a user provided function, because the user provided function might crash and we may never be able to unlock it. 
• Use std::lock() to lock more than one mutex. 
• Lock the mutex in same order.

Multithreading: 3.Mutex

When we execute the below code. The output would appear random. We are trying to print 1 to 9 from main and 10 to 19 from the thread.

	#include<thread>
	#include<iostream>
	using namespace std;
	void print()
	{
	//printing frm thread
	for (int i = 10; i < 20; i++)
	{
	cout <<"thread"<< i << endl;
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	for (int i = 1; i <10; i++)
	{
	cout << "Main" << i << endl;
	}
	if (t.joinable()) //check if the thread is joinable
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw datarace.cpp hosted with ❤ by GitHub

The output looks like below

threadMain101
threadMain112
threadMain123
threadMain134
threadMain145
threadMain156
threadMain167
threadMain178
threadMain189
thread19

The output looks haphazard and not understandable. This is because both the main thread and the thread t are fighting for the common resource cout. We have to make a change in our code to control the access of cout. meaning if one thread is accessing cout, other thread has to simply wait for access.
We use std::mutex lock and unlock methods to do that.

	void customcout(std::string&str, int i)
	{
	mut.lock();//locks access
	cout << str << i << endl;
	mut.unlock();//releases access
	}
	void print()
	{
	//printing frm thread
	for (int i = 10; i < 20; i++)
	{
	customcout(string("thread:"), i);
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	for (int i = 1; i <10; i++)
	{
	customcout(string("Main:"), i);
	}
	if (t.joinable()) //check if the thread is joinable
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw mutex.cpp hosted with ❤ by GitHub

below is the output after using mutex

thread:10
thread:11
thread:12
thread:13
thread:14
thread:15
thread:16
thread:17
thread:18
thread:19
Main:1
Main:2
Main:3
Main:4
Main:5
Main:6
Main:7
Main:8
Main:9

Multithreading: 2.Join and Joinable

Most of the times the main thread may execute in a shorter period of time than the child threads.
If the main thread completes before the child thread, then the child thread will be orphaned.
The main thread needs to wait for the child thread to complete.
We need to call t1.join() on the thread instance to make the main thread wait till t1 execution is complete.

	#include<thread>
	#include<iostream>
	using namespace std;
	void print()
	{
	for (int i = 1; i <= 10; i++)
	{
	cout << i << endl;
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw jointhread.cpp hosted with ❤ by GitHub

Also we need to check if a thread is joinable (thread with active code of execution), before calling join.

	#include<thread>
	#include<iostream>
	using namespace std;
	void print()
	{
	for (int i = 1; i <= 10; i++)
	{
	cout << i << endl;
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	if (t.joinable()) //check if the thread is joinable
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw Joinable.cpp hosted with ❤ by GitHub

Multithreading :1.Create thread

We will be using std::thread class to create threads.
std:thread is introduced in C++11.
We can start creating threads by including the thread header file. To create a thread, we need to pass the code that needs to be executed in the constructor of the thread.
As soon as the thread object is created, a new thread is launched, which will execute the code passed to the constructor.


The constructor takes

• a function object
• a function pointer
• a  lambda expression

	#include<thread>
	#include<iostream>
	using namespace std;
	class print_obj {
	public:
	void operator()(int max)
	{
	cout << "Thread with function object" << endl;;
	for (int i = 0; i < max; i++)
	{
	cout << i << endl;
	}
	}
	};
	void main()
	{
	//creating a thread with a function pointer
	thread t1(print, 50);
	//creating a thread with a function object
	thread t2(print_obj(), 100);
	//below is a lambda expression
	auto printlambda = [](int max) {
	cout << "thread with lambda function" << endl;
	for (int i = 0; i < max; i++)
	cout << i << endl;
	};
	//creating a thread with a lambda
	thread t3(printlambda, 150);
	}

view raw createthread.cpp hosted with ❤ by GitHub

Polymorphism

Polymorphism

Polymorphism meaning having many forms.

In C++ there are two types of polymorphism

• Compile-time polymorphism
• Run-Time polymorphism

Compile time polymorphism 

The binding happens at compile time, meaning based on the arguments the compiler tries to interpret the function call.

It can be observed with function overloading. Based on the type of arguments passed, the compiler decides which function to call. 

	int add(int a, int b) {
	return a + b;
	}
	int add(int a, int b, int c) {
	return a + b + c;
	}
	void main()
	{
	/*depending on the number of the arguments passed
	compiler decides which method to call
	*/
	add(1,2);
	add(1,2,3);
	}

view raw polymorphism.cpp hosted with ❤ by GitHub

Run time polymorphism 

The binding happens at run time. Function over-riding is an example of Run-time polymorphism.
Here is a simple example of Run-time polymorphism.

	class Animal {
	public:
	//remove the virtual keyword here to avoid dynamic binding
	virtual void sound() {
	}
	};
	class Cat :public Animal {
	void sound() {
	cout << "Meow" << endl;
	}
	};
	class Dog :public Animal {
	void sound() {
	cout << "Woof" << endl;
	}
	};
	void makesound(Animal*ptr)
	{
	ptr->sound();
	}
	int main()
	{
	Animal*catptr = new Cat();
	Animal*dogptr = new Dog();
	makesound(catptr);
	makesound(dogptr);
	return 0;
	}

view raw RT_polymorphism.cpp hosted with ❤ by GitHub

In the above example, based on the type of the object the pointer is holding we would want the function to be called. If it is Dog pointer, then the Dog class's sound method is executed. This feature of the compiler to identify the type of object at run time and call the correct method is called Run time polymorphism. For this to occur the base class should have atleast one virtual function.

Casting

Implicit casting:
when we assign a float to integer, compiler implicitly casts it

Explicit casting.
We tell the compiler that I want this type to cast to another type, and we are aware of data loss that might occur.

const_cast
Used to cast away constness of a variable.
We can change non-const class member inside const member function.
We can pass const data to a function that wont take constant.
Undefined behaviour on modifying variable declared as const
It is safer

static_cast

	int i = 9;
	char c = 'a';
	int* q = (int*)&c; // pass at compile time, may fail at run time
	int* p = static_cast<int*>(&c); //fails at compile time
	float f = static_cast<float>(i); // convert object from one type to another
	Base* pd = static_cast<Base*>(new Derived()); // convert pointer/reference from one type
	// to a related type (down/up cast)

view raw staticcast.cpp hosted with ❤ by GitHub

Casting a float to int using static_cast.
It is compile-time cast
It performs a strict type checking.
Cannot cast incompatible types
Gives compilation error if matching types not casted

dynamic_cast

	class Base {
	virtual void fun() { }
	};
	class Derived :public Base {
	void fun() { }
	};
	int main()
	{
	Derived*pDerived = new Derived();
	Base*pbase = new Base();
	Base*pbase2 = pDerived;// this compiles alright
	pbase = static_cast<Base*>(new Derived());//derived to base
	pDerived = static_cast<Derived*>(new Base());//base to derived works fine, works on non polymorphic
	pbase = dynamic_cast<Base*>(new Derived());//derived to base
	pDerived = dynamic_cast<Derived*>(new Base());//base to derived returns null pointer works only if polymorphic
	return 0;
	}

view raw casting.cpp hosted with ❤ by GitHub

Can be used only with pointers and references to objects.
Always successful from derived to base
Base to derived is not allowed unless for polymorphic
dynamic_cast checks RTTI to return the complete valid object
Returns nullpointer in case it is not able to return the valid object
Throws bad_cast exception in case of reference.
Can cast void pointer to any class (even unrelated)
Can cast any type of pointer to void pointers

reinterpret_cast
Converts any type of pointer to any other type (whether related or not)

InsertionSort

Insertion sort is similar to sorting playing cards.
Start with second element and keep in correct location to its left.
Only difference in programming is all the other elements need to be moved to the right to make place for the incoming element.
It is particularly useful for partially sorted array.

Time complexity : O(n2)
Extra Memory:θ(1)
Stable : Yes

	#include<iostream>
	using namespace std;
	void print(int*arr, int size)
	{
	for (int i = 0; i < size; i++) {
	cout << arr[i] << " " ;
	}
	cout << endl;
	}
	void insertionsort(int*arr, int size)
	{
	for (int i = 1; i < size; i++)
	{
	int key = arr[i];
	int j = i - 1;
	while (j >= 0 && arr[j] > key) {
	arr[j + 1] = arr[j];
	j--;
	}
	arr[j + 1] = key;
	print(arr, size); //just to see what happens after every iteration
	}
	}
	int main()
	{
	int arr[] = { 5,4,3,2,1 };
	insertionsort(arr, 5);
	return 0;
	}

view raw insertionsort.cpp hosted with ❤ by GitHub

Singleton Design Pattern

In singleton design pattern, we restrict the instantiation of the object to only one. We make the constructor private and create a static method to control the instantiation

	class Singleton {
	Singleton() {};//make the constructor private
	static Singleton* _obj;// private object so that access is restricted
	public:
	//method to create object
	static Singleton*Getinstance() {
	if (_obj == NULL)
	_obj = new Singleton();
	return _obj;
	}
	//method to delete the object
	static void DeleteInstance()
	{
	if (_obj)
	{
	delete _obj;
	_obj = NULL;
	}
	}
	};
	//initialize the object
	Singleton* Singleton::_obj = NULL;
	int main()
	{
	//usage
	Singleton*pobj = Singleton::Getinstance();
	Singleton::DeleteInstance();
	return 0;
	}

view raw Singleton.cpp hosted with ❤ by GitHub

Quick Union/Lazy Union

	//Lazy union
	class QuickUnion
	{
	int* arr;
	public:
	QuickUnion(int num)
	{
	size = num;
	arr = new int[num];
	//N array access
	for (int i = 0; i < num; i++)
	arr[i] = i;
	}
	int root(int i)
	{
	while (arr[i] != i) //depth of i array accesses
	i = arr[i];
	return i;
	}
	bool Find(int p, int q)
	{
	if (root(p) == root(q))//depth of p and q array accesses
	return true;
	return false;
	}
	void Union(int p, int q) //change the root of p to point to root q
	{
	int i = root(p);
	int j = root(q);
	arr[i] = j;
	}
	//2N+2 array access
	int size;
	};

view raw quickunion.cpp hosted with ❤ by GitHub

Quick Find

This is a Quick Find algorithm

	//Union find
	//dynamic connectivity
	//reflexive: P is connected to P
	//symmetric: if p is connected to Q then Q is connected to P
	//transitive: if P is connected to Q and Q is connected to R then P is connected to R
	//connected components {0} {1 2 3}
	//Quick Find
	//eager algorithm
	//check if p and q have same id
	class QuickFind
	{
	int* arr;
	public:
	QuickFind(int num)
	{
	size = num;
	arr = new int[num];
	for (int i = 0; i < num; i++)
	arr[i] = i;
	}
	bool Find(int p, int q)
	{
	if (arr[p] == arr[q])
	return true;
	return false;
	}
	void Union(int p, int q)
	{
	int pid = arr[p];//1
	int qid = arr[q];//1
	for (int i = 0; i < size; i++)
	{
	if (arr[i] == qid)//N
	{
	arr[i] = pid;//N
	}
	}
	}
	//2N+2 array access
	int size;
	};

view raw QuickFind.cpp hosted with ❤ by GitHub