character to integer

problem : implement atoi function

declaration : int atoi(char*s);

solution 1 : (left to right )

int atoi(char*s)
{
    int valuesofar=0;
    if(s)
    {    
	while(*s && *s>='0' && *s<='9')
   	{
       		valuesofar = valuesofar*10 + (*s-'0');
       		s++;
   	}
    }
   return valuesofar;
}

solution 2: (right to left )

int atoi(char*s)
{
    int valuesofar=0;
    int power=1;
    char*x;
    if(s)
    {   
	x = s;
	while(*x)
	x++;            // reach the end of the string
  
	while(x>=s&& *x>='0' && *x<='9')
   	{
       		valuesofar += (*x-'0') * power ;
       		x--;
		power*=10;           // adjust power
   	}
    }
   return valuesofar;
}

fair result from an unfair coin

you are given an unfair coin in which head has higher probability of occurring than tails.

solution :

assume

TH as head
HT as tail
TT, HH than toss again

now new head and tail have equal probabilities

Using bit vectors

a nice discussion on why one should use bit vectors and not integer arrays in some particular situations

bit vector

print a unsigned long int using putchar

problem : print an unsigned long integer using only putchar

solution : we'll have to break the number and print the individual digit, we can use % operation to get the digits

code :

void putlong(unsigned long n) {
  if (n < 10) {
    putchar(n + '0');
    return;
  }
  putlong(n / 10);
  putchar(n % 10 + '0');
}

reverse a string using recursion

problem : reverse a string using recursion

: solution

void print_reverse(char* str)
{
	if(*str=='\0')return;
	else
	print_reverse(str+1)
	putchar(*str);
}

permutation of parantheses

problem : generate all the permutations of valid parantheses

e.g.

input 1
output {}

input 2
output {}{}, {{}}

input 3
output: {}{}{}, {{{}}}, {{}{}}, {{}}{}, {}{{}}

solution :

note : number of permutation can be easily found by noticing that it is forming a catalan series, 1,2,5,... so nth term will be (2^n -n).

solution:

sorting O(nlogn)

earlier post on sorting covered sorting with complexity O(n2)

this post will cover the O(nlogn) case

1) Quick sort
// explanation : TODO


2) merge sort
TODO:

3) Heap Sort

Sorting

Some basic sorting algorithms {must know}

1) Bubble sort
2) Insertion sort
3) Selection sort

bubble sort :



> worst case time complexity : O(n^2)
> best case time complexity : O(n) { when list is already sorted }
> worst case space complexity: O(1) auxiliary

> not used anymore,

Insertion sort :
algotithm : assume a sorted array in the given array, select one of the card and insert it into its correct position in the sorted array .



> better than selection and bubble sort
> space complexity : O(1)
> worst case time complexity : O(n^2)
> best case time complexity : O(n) {when array is already sorted }
> it is stable : stability means that it does not change the order of elements with equal keys
> modified version : shell sort
> for small input, insertion sort may perform better than even quick sort

selection sort
simply select the element one by one in increasing order and insert them into their correct position



> worse (almost half ) than insertion sort.
> time complexity O(n2) { both worse and best }
> variant : heap sort

BackTracking

backtracking is used as a searching technique
so what are we searching basically ?
we are searching the tree for a particular goal leaf node/nodes.

How to apply backtracking
1) Make a choice
2) Compute the consequences
3) If the search is unsuccessful or needs to continue for some other reason,
4) Undo the consequences,
5) Undo the choice
6) Make a different choice
7) repeat from 2

Every language that supports loops, supports backtracking .

basic problem 1 : just by following the definition given above we can have a very trivial case where backtracking can be applied using just for loops and continue statement
problem : find the number of different Pythagoras triplets where hypotenuse is less than 100 .
solution :
1) make choice of sides in the three for loops
2) compute the condition for triplet, if condition fails, means we need to backtrack and stop processing further solution (printing in this case) so just continue; and start with new values of one of the sides and again repeat the above steps.

#include<stdio.h>
int main()
{
	int n = 100;
	int i,j,k,count=1;
	for(i=5;i<=n;i++)
	{
		for(j=1;j<i;j++)
		{
			for(k=1;k<=j;k++)
			{
				if((j*j + k*k )!= i*i)
				 continue;
				printf("%2d | %d %d %dn",count++,i,j,k);
			}
		}
	}
	return 0;
}

code on ideone :http://ideone.com/vDlB0
second problem : generate all the permutations of a string.

solution at : http://quickalgo.blogspot.com/2011/08/permutations-of-string.html
note: notice the tree in the above post, the solutions are the leaf nodes  and we are doing depth first traversal in that tree printing only the leaf nodes.
code :

#include <stdio.h>
#include <string.h>

void swap(char*a,char*b);
void permute(char* s, int i, int n);

int main()
{
	char s[] = "abc";    
	int n = strlen(s);
	permute(s,0,n);      
	return 0;
}
void swap(char*a,char*b)
{
	char t;
	t = *a;
	*a=*b;
	*b=t;
}

void permute(char* s, int i, int n)
{
	int j;
	if(i==n)   // reached the leaf node.
	{
		printf("%sn",s); // process solution  
	}
	else
	{
		for(j=i;j<n;j++)
		{
			swap((s+i),(s+j));  // choose an option and move forward
			permute(s,i+1,n);   // compute new solution
			swap((s+i),(s+j));  // backtrack after printing
		}
	}
}

third problem : 8 queens puzzle
solution is here : http://quickalgo.blogspot.com/2011/08/8-queens-problem.html
code for reference

#include<stdio.h>
#include<stdlib.h>
int t[8] = {-1};
int sol = 1;

void printsol()
{
	int i,j;
	char crossboard[8][8];
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			crossboard[i][j]='_';
		}
	}
	for(i=0;i<8;i++)
	{
			crossboard[i][t[i]]='q';
	}

	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			printf("%c ",crossboard[i][j]);
		}
		printf("n");
	}  
}
int empty(int i)
{
	int j=0;
	while((t[i]!=t[j])&&(abs(t[i]-t[j])!=(i-j))&&j<8)j++;
	return i==j?1:0;
}

void queens(int i)
{
	for(t[i] = 0;t[i]<8;t[i]++)
	{
		if(empty(i))
		{
			if(i==7){
				printsol();
				printf("n solution %dn",sol++);
			}
			else
			queens(i+1);
		}
	}
}



int main()
{
	queens(0);
	return 0;
}

problem 4: knight's tour problem
The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open http://en.wikipedia.org/wiki/Knight's_tour

explanation of problem :

what is a knight's tour ==>

sequence of moves (i.e., a tour) by a knight chess piece (which may only make moves which simultaneously shift one square along one axis and two along the other) such that each square of the board is visited exactly once.
solution : problem 5: Rat in a maze

problem 6: coloring a map

problem 7: sudoku puzzle

Linked List

Implemented using pointers,

typedef struct node{
    int value;
    struct node* next;
}listnode;

listnode*head = NULL;
listnode*tail = NULL;

Primary operations :

1) searching
2) insertion
3) deletion

Searching can be done in two ways , either iteratively or recursively recursive code : simple
if-else recursive method. type : tail recursive. base case -> either list is empty or value found at head

listnode* search(listnode*head,int x)
{
    if(head==NULL)
        return;
    else if(head->value==x)
        return head;
    else
    return search(head->next,x);
}

time complexity : O(n) space complexity: O(1)

Insertion in a list :


important cases :
1) list can be empty, so head pointer will have to be adjusted,
2) pass address of the head and tail pointer in addnode() function.
3) otherwise simply insert at the tail of the list and update the tail pointer.

void addnode(listnode**head,listnode**tail,int value)
{
	listnode* temp = (listnode*)malloc(sizeof(listnode));
	temp->value = value;
	temp->next = NULL;
	
	if(*head == NULL) //list was empty
	{
		*head = temp;
		*tail = *head;   // adjust tail pointer
	}
	
	else
	(*tail)->next = temp;   // add at the end of tail
	*tail = (*tail)->next;  // adjust tail pointer
	return ;
}

Deletion : find the pointer to the node that is to be deleted and remove the desired node from the list. 

Why linked list is preferred ?:
1) insertions and deletions are simple as compared to arrays where number of elements have to be shifted
2) linked list are recursive objects : cut the first element , and what we have is another linked list. 

Important operations and questions about linked lists

1) reverse a linked list
 a) recursive
b) iterative

2) sort a linked list
a) using bubble sort technique
b) using merge sort {best way under normal condition}

3) doubly linked list {repeat 1, and 2 for the doubly linked list }

4)detect whether a linked list contain a loop or not, find and remove the loop

5) find the middle of the linked list 6) find the nth node from the last in a linked list

7) reverse alternate k nodes in a singly linked list 

8) remove duplicates from sorted/unsorted singly linked list

9) print a linked list in reverse order

10) given two linked list , find their point of intersection

11) generate doubly linked list from a binary search tree

12) insert nodes into the list in sorted fashion

13) given a linked list of characters, check whether it is palindrome or not

// todo :

C precedence table

C Operator Precedence Table