reverse a list recursively and nonrecursively

reverse(h)
{

/*

* 1->2->p ...

* 2->1->p ...

*/

if(!h && !h->next)
return

t = h->next
h->next = NULL
while(t)
{
next = t->next
t->next = h
h = t
t = next
}
}



reverse(h)
{
/*
* 1->2->3->4
* 4->3, 1->2->3
* 4->3->2, 1->2
* 4->3->2->1
*/
if(!h && !h->next)
return

first = h
next = first->next

reverse(next)

first->next->next = first
fisrt->next = 0
h = next
}

remove a given node from a list

remove(h, a)
{
if(h == 0 || a== 0)
return ;

if(h == a)
{
a = a->next
delete h
h = a
return
}

t=h
while(t->next)
{
if(t->next == a)
{
k = t->next->next
delete t->next
t->next = k
return
}

t = t->next
}

}

construct mirror of a given binary tree

mirror(a)

if(!a)
return 0

mirror(a->left)
mirror(a->right)

swap(a->left, a->right)

check if a tree is a binary search tree (BST)

isBST(a)
{
if(!a)
return true

if( a->left && minVal(a->left) > a->num)
return false

if( a->right && maxVal(a->right) < a->num)
return false

if(!isBST(a->left) && !isBST(a->right))
return false

return true

}

serialize and deserialize a binary tree

serialize(a, list)
{
static int level = 0;
if(!a)
{
list[level++] = -1;
return
}

list[level++] = a->num;

serialize(a->left, list)
serialize(a->right, list)
}

deserialize(a, list)
{
static int level = 0;

if(list[level] == -1)
{
level++
return 0
}

a = createNode()
a->num = list[level++]
a->left = deserialize(a, list)
a->right = deserialize(a, list)
}

reverse a binary tree such that the child's left points to parent

reverse(a)
{
if(!a)
return 0

if(!a->left && !a->right)
return a

l = reverse(a->left)
if(l)
l->left = a

r = reverse(a->right)
if(r)

r->left = a;

return a
}

print all root to leaf path of a binary tree

printpath(a)
{
int path[MaxLength]
printpathrec(a, path, 0)
}

printpathrec(a, path, pathlen)
{
if(!a)
{
for i 1 to pathlen
print path[i]
}

path[pathlen] = a->num

printpathrec(a->left, path, pathlen+1)
printpathrec(a->right, path, pathlen+1)
}

count unique binary trees those can be formed from n numbers

counttrees(n)
if(n <= 1)
return 1

sum = 0

for i 1 to n
{
l = counttrees(i-1)
r = counttrees(n-i)
sum += l + r
}
return sum

find least common ancestor of a binary tree

lca(a, p, q)

if(!a)
return 0

if(a == p || a == q)
return a

l = lca(a->left, p, q)
r = lca(a->right, p, q)

if(l && r)
return a

if(l)
return l

if(r)
return r

return 0

find the maximum depth of a binary tree

maxdepth(a)
if(!a)
return 0

return 1 + max(maxdepth(a->left), maxdepth(a->right)

find the size of a tree

size(a)
if(!a)
return 0

return 1+size(a->left)+size(a->right)

remove duplicate characters from a sorted string

void removeDup(int a[], int& len)
{
int j=1;
for(int i=0, k=1; i< len && k< len; i++, k++)
{
//cout << a[i] << " " ;
if(a[i] != a[k])
{
a[j] = a[k];
j++;
}
}

len =j;
}

print a matrix in spiral order

void printSpiral(int a[][10], int rows, int columns)
{
int count = rows * columns;

int columnMax = columns-1;
int columnMin = 0;
int rowMax = rows - 1;
int rowMin = 0;

while(count)
{
for(int i=columnMin; i<=columnMax; i++, count--)
cout << a[rowMin][i] << "->";

rowMin++;

for(int i=rowMin; i<=rowMax; i++, count--)
cout << a[i][columnMax] << "|";

columnMax--;

for(int i=columnMax; i>=columnMin; i--, count--)
cout << a[rowMax][i] << "<-";

rowMax--;

for(int i=rowMax; i>=rowMin; i--, count--)
cout << a[i][columnMin] << "^";

columnMin++;

}
}

create a binary search tree and add a node, traverse inoder, breadth first search, find fourth smallest

const int MaxN = 50;

class node;

class queue
{
public:
queue() {begin = end = -1;}
void enque(node* n)
{
if(empty())
begin = 0;
elem[++end] = n;
}

node* deque()
{
node* t;
if(begin == -1)
return 0;

if(begin == end)
{
t=elem[begin];
begin = end = -1;
}
else
t=elem[begin++];
return t;
}

int empty() { return (begin == -1)? 1: 0;}

private:
node* elem[MaxN];
int begin;
int end;
};

class node
{
public:
int n;
node* l;
node* r;
};

class bst
{
public:
bst() {r= NULL;}
void addnode(int n);
void traverseinorder() {traverseinorder(r);}
void bfs() {bfs(r); }
void fourthsmallest() {fourthsmallest(r);}
private:
void addnode(node* p, int n);
void traverseinorder(node* r);
void bfs(node* r);
void fourthsmallest(node* p);
node* r; //root
};

void bst::addnode(int n)
{
if(!r)
{
r = new node();
r->n = n;
r->l = NULL;
r->r = NULL;
return;
}
addnode(r, n);
}

void bst::addnode(node* p, int n)
{
if(n < p->n)
{
if(p->l)
addnode(p->l, n);
else
{
p->l = new node();
p->l->n = n;
p->l->l = NULL;
p->l->r = NULL;
return;
}
}
else
{
if(p->r)
addnode(p->r, n);
else
{
p->r = new node();
p->r->n = n;
p->r->l = NULL;
p->r->r = NULL;
return;
}
}
}

void bst::traverseinorder(node* p)
{
if(!p)
return;
traverseinorder(p->l);
cout << p->n << " ";
traverseinorder(p->r);
}

void bst::fourthsmallest(node* p)
{
static int count=0;
if(!p)
return;
fourthsmallest(p->l);
count++;
if(count == 4)
cout << "4th smallest = " << p->n < fourthsmallest(p->r);

}

void bst::bfs(node* p)
{
if(!p)
return;

queue t;
t.enque(p);

node dummy;
dummy.n = -1;

cout << "\n\n breadth first traverse\n";
t.enque(&dummy);

while(!t.empty())
{
node* k = t.deque();
while(k && k->n == -1)
{
cout << endl;
k = t.deque();
}

cout << k->n << " ";
if(k->l)
t.enque(k->l);
if(k->r)
t.enque(k->r);

t.enque(&dummy);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
bst tr;
cout << "enter numbers to create a BST (-1 as end of input)\n";
while(1)
{
int n;
cin >> n;
if(n < 0)
break;
tr.addnode(n);
}

cout << "inorder: ";
tr.traverseinorder();

tr.bfs();

tr.fourthsmallest();
return 0;
}

reverse a linked list

/*
* A NDROID -> NA DROID -> DNA ROID -> RDNA OID -> ORDNA ID -> IORDNA D -> DIORDNA
* temp = head2->next // D
* head2->next = temp->next // A->ROID
* temp->next = head1 // D->NAROID
* head1 = temp; //(DNA)ROID
*/
List* rev_list(List* head)
{
List* head1 = head;
List* head2 = head;

List* temp;
while(head2->next)
{
temp = head2->next;
head2->next = temp->next;
temp->next = head1;
head1 = temp;
//print_list(head1);
}

return head1;
}

find maximum sum of a sub arrary

void maxsumsubarray(int a[], int n)
{
int sum=0;
int maxsofar = 0;
int start =0;
int end=0;
int count =0;
for(int i=0;i< n;i++)
{
if(maxsofar + a[i] > 0)
{
maxsofar += a[i];
count++;
}
else
{
maxsofar = 0;
count =0;
}

if(sum < maxsofar)
{
sum = maxsofar;
end = i;
start = end - count + 1;
}
}
cout << "maxsum = " << sum ;
cout << " start = a[" << start << "] = " << a[start] << " end = a[" << end << "] = " << a[end] << endl;
}

sort an array using heapsort

void max_heapify(int* u, int i, int size)
{
//push down the ith element in the max tree
int l = 2*i+1;
int r = 2*i+2;
int largest =i;
if(l<=size && u[l]>u[largest])
largest = l;
else
largest = i;
if(r<=size && u[r]>u[largest])
largest = r;
if(i != largest)
{
//exchange i and largest and call recurse max_heapify
int t=u[i];
u[i] = u[largest];
u[largest] = t;
max_heapify(u, largest, size);
}
}

void build_max_heap(int* u, int size)
{
for(int i=size/2; i>=0; i--)
{
max_heapify(u, i, size);
}
}

void heap_sort(int* u, int size)
{
build_max_heap(u, size);

cout << "max heap: ";
print_arr(size);

int hsize = size;
for(int i=0; i< size; i++)
{
hsize--;
int t= u[0];
u[0] = u[hsize];
u[hsize] = t;
max_heapify(u, 0, hsize-1);
}
}

sort an array using mergesort

void merge_sort(int* u, int size)
{
if(size==1)
{
return;
}
//divide the array into 2
//sort each
merge_sort(u, size/2);
merge_sort(u+(size/2), size-(size/2));

int* t=(int*)malloc(sizeof(int)*(size));

for(int i=0,anext=0,bnext=0; i< size; i++)
{
if(anext==size/2)
{
t[i] = *(u+(size/2)+bnext);
bnext++;
}
else if(bnext == size-(size/2))
{
t[i] = *(u+anext);
anext++;
}
else
{
if(*(u+anext) < *(u+(size/2)+bnext))
{
t[i] = *(u+anext);
anext++;
}
else
{

t[i] = *(u+(size/2)+bnext);
bnext++;
}
}
}

//copy back to org array
for(int i=0;i< size;i++)
{
*(u+i) = *(t+i);
}


delete t;
}

find kth smallest element in an array

void kthsmallest(int k, int l, int u)
{
if(l>= u)
return;

//partition
int m=l;
for(int i=l+1; i<= u; i++)
{
if(arr[i] < arr[l])
{
//swap them
int t=arr[i];
arr[i]=arr[m+1];
arr[m+1]=t;
m++;
}
for(int j=0;j< 8;j++)
cout << " " << arr[j];
cout << " m= " << m << " i= " << i << endl;
}
//swap l, m
int t=arr[m];
arr[m]=arr[l];
arr[l]=t;

for(int i=0;i< 8;i++)
cout << " " << arr[i];
cout << " [" << arr[m] << "] is now correctly placed at position " << m ;
cout << endl;
/*
if(m==k)
cout << k << "th smallest element is " << arr[m] << endl;
*/
//recursively call qsort
if(k< m)
kthsmallest(k, l, m-1);
if(k> m)
kthsmallest(k, m+1, u);
}

//program end

sort an array using quicksort

#include <iostream>
using namespace std;

void mquicksort(int A[], int l, int u)
{
    if(l>=u)
        return;
        
    int m=l;
    
    for(int i=l+1; i<u; i++)
    {
        if(A[i] < A[l])
        {
            int t=A[i];
            A[i] = A[m+1];
            A[m+1]=t;
            m++;
        }
    }

    int t=A[l];
    A[l] = A[m];
    A[m]=t;

    mquicksort(A, l, m-1);
    mquicksort(A, m+1, u);
}

int main() {
    // your code goes here
    int A[20];
    int n;
    cout << "enter number of elements(<=20) to be sorted:";
    cin >> n;
    cout << "\nenter " << n << " elements now\n";
    for(int i=0;i<n;i++)
    {
        cin >> A[i];
    }
    mquicksort(A, 0, n);
    
    cout << "\n\nsorted numbers: ";
    for(int i=0;i<n;i++)
    {
        cout << A[i] << " ";
    }

    return 0;
}

Reverse the order of words in a sentence

int index[20] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

//output: word by word sentence this reverse
//order : O(n/2) + O(n) + O(w)*O(wlen/2)

//find indexes of words' start
void revsentence(char* src, int len)
{
for(int i=0; i< len/2; i++)
{
char temp = src[i];
src[i] = src[len-i-1];
src[len-i-1] = temp;
}

int j=1;
for(int i=0; i< len; i++)
{
if(src[i] == ' ')
index[j++] = i;

}
index[j++] = len; //last index = src:'\0'

//reverse the words

for(int i=0; i< j; i++)
{
int startindex = index[i] + 1;
int endindex = index[i+1]-1;
int wlen = endindex - startindex +1;
for(int k=0; k< wlen/2; k++)
{
char temp = src[startindex+k];
src[startindex+k] = src[endindex-k];
src[endindex-k] = temp;
}

}

}
int _tmain(int argc, _TCHAR* argv[])
{
char src[200];
cout << "enter a string to reverse word by word: " ;
cin.getline(src,200);
revsentence(src, strlen(src));

cout << "\noutput: " << src << endl;
return 0;
}

Generate k unique random numbers ranging from 1 to n

void genrandomnum(int k, int n)
{
cout << "algo1: ";
int arr[100];
for(int i=0;i < 100;i++)
arr[i] = 0;

int i=0;
while(i!=k)
{

int rnd = (rand()%n) + 1; //random num in 1,n
if(arr[rnd] == 0)
{
arr[rnd] = -1;
arr[i] = rnd;
i++;
}
else
{
if(arr[rnd] > 0)
{
arr[rnd] = -arr[rnd]; //mark
arr[i] = rnd;
i++;
}
}

}

for(int i=0;i < k;i++)
if(arr[i]<0)
arr[i]=-arr[i];

for(int i=0;i < k;i++)
cout << " " << arr[i];

cout << endl << endl;
}

//Knuth's Algo

void genrandomnum1(int k, int n)
{
cout << "algo2: " ;
for(int i=0; i < n; i++)
{
if((rand()%(n-i)) < k)
{
cout << i << " ";
k--;
}
}

cout << endl << endl;
}

move largest node to the end of a linked list

class list
{
public:
int n;
list* next;
};

void movelargesttoend(list*& p)
{
if(!p)
return;

if(!p->next)
return;

list* l = p;
list* cur = p;

list* prev = p;

while(cur->next)
{
if(l->n < cur->next->n)
{
l = cur->next;
prev = cur;
}
cur = cur->next;
}

//head is largest
if(l == p)
{
cur->next = p;
p = p->next;
cur->next->next = NULL;
}
else if(l != cur)
{
prev->next = l->next;
cur->next = l;
l->next = NULL;
}
}

insertion sort of a linked list

void insertionsort(list*& p)
{
cout << "sorting...\n"; list* res = NULL; while(p) { list* next = p->next;
sortedinsert(res, p);
p = next;
}

p = res;
}

insert a node in sorted order into a sorted linked list

void sortedinsert(list*& head, list* p)
{
//case for head node
if((!head) || (p->n < head->n))
{
p->next = head;
head = p;
return;
}

//intermediate case
list* cur = head->next;
list* prev = head;
while(cur)
{
if(p->n > cur->n)
{
prev= cur;
cur = cur->next;
}
else
break;
}

//tail case
if(!cur)
{
prev->next = p;
p->next = NULL;
}
else
{
p->next = cur;
prev->next = p;
}

}

Merge two sorted linked lists

class list
{
public:
int n;
list* next;
};

list* merge_sorted_lists(list* a, list* b)
{
list* t1;
list* t2;
list* head;
if(!a || !b)
return NULL;

// t1 points to the smallest number
if(a->n < b->n)
{
t1 = a;
t2 = b;

head = a;
}
else
{
t1=b;
t2=a;

head =b;
}

while(t1 && t2)
{
cout << t1 << " " << t2 << endl;
if(t1->next && (t1->next->n < t2->n))
{
t1 = t1->next; //move to next element in smaller list
}
else
{
list* t=t1->next;
list* k=t2->next;
t1->next = t2;
t2->next = t;
t2 = k;
t1 = t1->next;
}
}

return head;
}

find maximum length of space in given text

void maxlenofspaces(char a[])
{
int count = 0;
int maxcount = 0;
int start = 0;
for(int i=0; a[i] != '\0'; i++)
{
if(a[i] == ' ')
{
if(!count)
start = i;
count++;
if(count > maxcount)
maxcount = count;
}
else
{
start = i-count-1;
count = 0;
}

}

cout << "\nstart index=" << start << " max spaces length=" << maxcount << endl;
}

Delete a character set present in a given string

char* strdel(char* s1, int len1, char* s2, int len2)
{
int bitmapvec[8]; //bit[n] = 1 if s1[i] == n else 0
for(int i=0; i<8; i++)
bitmapvec[i] = 0;

for(int i=0; i {
bitmapvec[ (s1[i] / 32) ] |= (1 << (s1[i] % 32)) ;
}

int j=0;
for(int i=0; i< len2; i++)
{
if(!(bitmapvec[s2[i]/32] & (1 << (s2[i] % 32))))
{
s2[j] = s2[i];
j++;
}
}

s2[j] = '\0';

return s2;
}

Find Substring in a given String

int findsubstr(char* src, char* trg, int srclen, int trglen)
{
if((srclen < trglen) (srclen < 1) (trglen < 1) (!src) (!trg))
return -1;

for(int i=0; i < srclen-trglen+1; i++)
{
//now compare the src with trg
int j=0;
for(; j < trglen; j++)
{
if(src[i+j] != trg[j])
break; //not found, restart with next src character
}
if(j==trglen)
return i;
}

return -1;
}