Find if a tree is balanced

//Tree definition
struct Node{
Node* Left;
Node* Right;
int Val;
};
typedef Node * tree;

/*Helper functions to find minimum and maximum*/
int MaxVal (int iNum1, int iNum2)
{
return iNum1 >= iNum2 ? iNum1 : iNum2;
}
int MinVal (int iNum1, int iNum2)
{
return iNum1 <= iNum2 ? iNum1 : iNum2;
}


/* Depth of trees */

int FindTreeDepth (tree t)
{
if (t == NULL)
return 0;
return 1 + MaxVal(FindTreeDepth(t->Left), FindTreeDepth(t->Right));
}


/* Minimum depth of a leaf */

int FindMinDepthOfLeaf (tree t)
{
if (t == NULL)
return 0;

if (t->Left == NULL)
if (t->Right == NULL)
return 1;
else
return 1 + FindMinDepthOfLeaf(t->Right);
else
if (t->Right == NULL)
return 1 + FindMinDepthOfLeaf(t->Left);
else
return 1 + MinVal(FindMinDepthOfLeaf(t->Left),
FindMinDepthOfLeaf(t->Right));
}



bool IsTreeBalanced (tree t)
{
//For tree to be balanced the depths of two arbitrary leaves must differ
//by at most 1
return FindTreeDepth(t) - FindMinDepthOfLeaf(t) < = 1;
}

Insert and Delete operations on Double Linked List

struct Node
{
Node* Prev;
Node* Next;
int data;
};

void InsertNode(Node** ppNode, int num)
{
if(*ppNode == NULL)
{
*ppNode = new Node();
(*ppNode)->data = num;
(*ppNode)->Next = NULL;
(*ppNode)->Prev = NULL;
return;
}
Node * pTemp = *ppNode;
while(pTemp->Next != NULL)
pTemp = pTemp->Next;
pTemp->Next = new Node();
pTemp->Next->data = num;
pTemp->Next->Prev = pTemp;
pTemp->Next->Next = NULL;
return;
}
void Display(Node *pNode)
{
while(pNode)
{
cout<<" "<data;
pNode = pNode->Next;
}
}
bool DeleteNode(Node** ppNode, int num)
{
bool bVal = false;
Node * pTemp = *ppNode;
//If the node is head then the head has to be reset
if((*ppNode)->data == num)
{
pTemp = pTemp->Next;
pTemp->Prev = NULL;
delete(*ppNode);
*ppNode = pTemp;
bVal = true;
}
else
{
while(pTemp)
{
if(pTemp->data == num)
{
pTemp->Prev->Next = pTemp->Next;
pTemp->Next->Prev = pTemp->Prev ;
delete pTemp;
bVal = true;
return bVal;
}
pTemp = pTemp->Next;
}
}
return bVal;
}

void ReverseList(Node** ppNode)
{
if((*ppNode == NULL)||((*ppNode)->Next == NULL))
return;
//Use 2 more pointers
Node* pastNode = *ppNode, *currentNode = NULL;
*ppNode = (*ppNode)->Next;
pastNode->Next = NULL;

while(*ppNode)
{
currentNode = *ppNode;
*ppNode = (*ppNode)->Next;

// Insert node at the front of
// the temporary list
currentNode->Next = pastNode;
currentNode->Prev = NULL;
pastNode->Prev = currentNode;
pastNode = currentNode;
}

// Update head with the temporary
// list
*ppNode = pastNode;
}
int _tmain(int argc, _TCHAR* argv[])
{
Node * Head = NULL;
InsertNode(&Head,10);
InsertNode(&Head,20);
InsertNode(&Head,30);
InsertNode(&Head,40);
InsertNode(&Head,50);
InsertNode(&Head,55);
InsertNode(&Head,60);
Display(Head);
DeleteNode(&Head,10);
DeleteNode(&Head,55);
Display(Head);
ReverseList(&Head);
Display(Head);
return 0;
}

Angle between hour arm and minute arm in an analog clock

abs(30 * hours - (11/2) * min)

Replace all occurance of %20 with a blank space.

#define MAX_LEN 256

/*******************************************************
INPUT: 1) character string with one or more %20 patterns
2) length of the string
OUTPUT: 0 - SUCCESS
-1 - INVALID INPUT
-2 - No need to do anything.
Test Data: 1)"%20"
2)"This%20is"
3)"This%20is%20%20a"
4)"This%20is%20%20%20"
5)"This is a"
*******************************************************/
int FindPattern( TCHAR* szStr, size_t &len)
{
//Return Values
int iRet = -2;
//if invalid Input
if((szStr == NULL)||(len <= 0))
return -1;
if(len <3)
return iRet;

TCHAR *pAhead = szStr;
TCHAR *pBack = szStr;


//Loop till you reach the end of the string
while( *pAhead)
{

//if the pattern is found replace it with ' ' and reposition the pointers
if( (*pAhead == _T('%'))&& (*(pAhead+1) == _T('2'))&&
(*(pAhead+2) == _T('0')))
{
*pBack = _T(' ');
pAhead += 3;
pBack +=1;
iRet = 0;
}
else//copy the data and increment the pointer
{
*pBack++ = *pAhead++;
}
}
*pBack = 0;

len = _tcslen(szStr);
return iRet;
}
int _tmain(int argc, _TCHAR* argv[])
{
_TCHAR szPattern[MAX_LEN];
memset(szPattern,0,MAX_LEN);
_tcscpy_s(szPattern,MAX_LEN,_T("This is a beautiful world"));
size_t len = _tcslen(szPattern);
int retVal = FindPattern(szPattern, len);
if(retVal == 0)
{
_tprintf(_T("The \' \' replaced string for %%20 is %s"),szPattern);
}
else if(retVal == -2)
_tprintf(_T("The %s did not have any %%20 pattern"),szPattern);
else
_tprintf(_T("\nInvalid input\n"));
return retVal;
}

Compute the number of digit after . in floating point number.

if given 9.554 output=3
for 43.000 output=0

double no =3.44;

int count =0;

while(no!=((int)no))
{
count++;
no=no*10;
}
printf("%d",count);

Breadth first traversal in binary tree

//BreadthFirst Traversal
void BreadthFirst(Node* pNode)
{
queue que;
while(pNode!= NULL)
{
cout<<" "<Val;
if(pNode->Left != NULL)
que.push(pNode->Left);
if(pNode->Right != NULL)
que.push(pNode->Right);
if(!que.empty())
{
pNode = que.front();
que.pop();
}
else
pNode = NULL;
}
}

Non recursive insert operation in binary tree.

struct Node{
Node* Left;
Node* Right;
int Val;
};
void InsertNodeNonRecursive(Node** ppNode, int val)
{
if(ppNode == NULL)
return;
if(*ppNode == NULL)
{
*ppNode = new Node();
(*ppNode)->Val = val;
(*ppNode)->Left = (*ppNode)->Right = NULL;
}
else
{
Node *pNode = *ppNode;
Node *pParent = NULL;
while(pNode != NULL)
{
//need to store the parent as we hit the NULL using pNode
pParent = pNode;
if( val > pNode->Val)
pNode = pNode->Right;
else
pNode = pNode->Left;
}
if(val > pParent->Val)
{
pParent->Right = new Node();
pParent->Right->Val = val;
pParent->Right->Left = NULL;
pParent->Right->Right = NULL;
}
else
{
pParent->Left = new Node();
pParent->Left->Val = val;
pParent->Left->Left = pParent->Left->Right = NULL;
}
}

}
int _tmain(int argc, _TCHAR* argv[])
{
Node* Head1 = NULL;
InsertNodeNonRecursive(&Head1,6);
InsertNodeNonRecursive(&Head1,4);
InsertNodeNonRecursive(&Head1,5);
InsertNodeNonRecursive(&Head1,2);
InsertNodeNonRecursive(&Head1,3);
InsertNodeNonRecursive(&Head1,1);
InsertNodeNonRecursive(&Head1,8);
InsertNodeNonRecursive(&Head1,7);
InsertNodeNonRecursive(&Head1,9);
return 0;
}

Find the next biggest number from the digits in the number.

If input is 8999 the next biggest number is 9899.
If input is 14562 the next biggest number is 14625.
using namespace std;
//SWAP 2 CHARACTERS
void swap(char* ch1, char* ch2)
{
char t;
t = *ch1;
*ch1 = *ch2;
*ch2 = t;
}
//USED IN QUICK SORT FOR SORTING AROUND THE PIVOT
int partition(char* ptr, int low, int high)
{
char key = ptr[low];
int i = low+1;
int j = high;
while(high > i && ptr[i] <= key)i++;
while(ptr[j] > key) j--;
if(i < j)
{
swap(ptr[i],ptr[j]);
}
else
{
swap(ptr[j],ptr[low]);
}
return j;

}
//RECURSSIVE QUICK SORT
void quicksort(char * ptr, int low, int high)
{
if( high > low)
{
int idx = partition(ptr,low,high);
quicksort(ptr,low,idx-1);
quicksort(ptr,idx+1,high);
}

}
//NEXT BIGGEST
void NextBiggest(char * val){

size_t len = strlen(val);
bool swapped = false;
// case : 9788 o/p:9887
//IF THERE IS ANY NUMBER IN OTHER PLACE, SMALLER THAN THE UNITth PLACE THE SWAP THEM
// AND YOU HAVE FOUND THE NEXT BIGGEST NUMBER
for(int i = len-2; i >= 1; i--)
{
if(val[len-1] > val[i]){
swap(val[len-1],val[i]);
swapped = true;
break;
}
}
//case : 145621 o/p:151246
//case 8997 o/p:9789
//IN CASES AS SHOWN ABOVE CHECK EVERY ALTERNATE DECIMAL PLACE VALUE, IF YOU FIND A SMALLER VALUE IN THE HIGHER DECIMAL PLACE SIMPLY SWAP THEM AND SORT THE INPUT FROM THAT POSITION.
if(swapped == false)
{
int i = 0;
for(i = len-2; i >=1; i--)
{
if(val[i] > val[i-1])
{
swap(val[i],val[i-1]);
swapped = true;
break;
}

}
if(swapped == true)
{
char* ptr = &val[i];
quicksort(ptr,0,(len - (ptr-val)-1));
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
char numeric [256];
memset(numeric,0,256);
cin >> numeric;
NextBiggest(numeric);
cout < < "The next biggest val is :" < < numeric;
return 0;
}

Merging two sorted single linked lists

#include < iostream >
using namespace std;
struct Node
{
Node* Next;
int val;
};

void InsertNode(Node** pNode, int val)
{
if(pNode == NULL)
return;
Node * pTemp, *pTraversal;
pTraversal = *pNode;
pTemp = new Node();
pTemp->val = val;
pTemp->Next = NULL;
if(*pNode == NULL)
{
*pNode = pTemp;
return;
}
while(pTraversal->Next != NULL)
{
pTraversal = pTraversal->Next;
}
pTraversal->Next = pTemp;

return;
}
void Display(Node* pNode)
{
while(pNode != NULL)
{
cout < < pNode->val < < " ";
pNode = pNode->Next;
}
}

void MergeLL(Node* pNodeIP1,Node* pNodeIP2, Node** ppNodeOP)
{
Node * pTemp = NULL;

while((pNodeIP1 != NULL)&&(pNodeIP2 != NULL))
{
if(pNodeIP1->val <= pNodeIP2->val)
{
if(*ppNodeOP == NULL)
{
*ppNodeOP = pNodeIP1;
pTemp = *ppNodeOP;
}
else
{
pTemp->Next = pNodeIP1;
pTemp = pTemp->Next;
}
pNodeIP1 = pNodeIP1->Next;
pTemp->Next = NULL;
}
else
{
if(*ppNodeOP == NULL)
{
*ppNodeOP = pNodeIP2;
pTemp = *ppNodeOP;
}
else
{
pTemp->Next = pNodeIP2;
pTemp = pTemp->Next;
}
pNodeIP2 = pNodeIP2->Next;
pTemp->Next = NULL;
}

}
if(pNodeIP2 == NULL)
pTemp->Next = pNodeIP1;
if(pNodeIP1 == NULL)
pTemp->Next = pNodeIP2;
}
int _tmain(int argc, _TCHAR* argv[])
{
Node* HeadOfList1 = NULL;
InsertNode(&HeadOfList1,1);
InsertNode(&HeadOfList1,3);
InsertNode(&HeadOfList1,5);
InsertNode(&HeadOfList1,7);
InsertNode(&HeadOfList1,11);
InsertNode(&HeadOfList1,13);
InsertNode(&HeadOfList1,15);

Node* HeadOfList2 = NULL;
InsertNode(&HeadOfList2,2);
InsertNode(&HeadOfList2,4);
InsertNode(&HeadOfList2,6);
InsertNode(&HeadOfList2,7);
InsertNode(&HeadOfList2,8);
InsertNode(&HeadOfList2,10);

cout < < "Contents of Sorted List1 :";
Display(HeadOfList1);

cout < < "\nContents of Sorted List2 :";
Display(HeadOfList2);

Node* HeadOfList3 = NULL;
MergeLL(HeadOfList1,HeadOfList2,&HeadOfList3);
cout < < "\nContents of Merged Sorted List :";
Display(HeadOfList3);
return 0;
}

Binary Tree -Depth First Traversal - Recursive / Non Recursive

#include "stdafx.h"
#include < iostream >
#include < stack >
using namespace std;
struct Node{
Node* Left;
Node* Right;
int Val;
};
void InsertNode(Node** ppNode,int val)
{
if(ppNode == NULL)
return;
if(*ppNode == NULL)
{
*ppNode = new Node();
(*ppNode)->Val = val;
(*ppNode)->Left = (*ppNode)->Right = NULL;
}
else
{
if(val > (*ppNode)->Val)
InsertNode(&((*ppNode)->Right),val);
else
InsertNode(&((*ppNode)->Left),val);
}
}
void PreOrderRecursive(Node* pNode)
{
cout<<" "<Val;
if(pNode->Left)
PreOrderRecursive(pNode->Left);
if(pNode->Right)
PreOrderRecursive(pNode->Right);
}
void PreOrderNonRecursive(Node* pNode)
{
bool done;
stacks;
Node * cursor = pNode;
done = false;

while(!done)
{
if(cursor != NULL)
{
cout<<" "<Val;
s.push(cursor);
cursor = cursor->Left;
}
else
{
if(!s.empty())
{
cursor = s.top();
s.pop();
cursor = cursor->Right;
}
else
{
done = true;
}
}
}
}
void InOrderRecursive(Node* pNode)
{
if(pNode->Left != NULL)
InOrderRecursive(pNode->Left);
cout<<" "<Val;
if(pNode->Right != NULL)
InOrderRecursive(pNode->Right);
}

void InOrderNonRecursive(Node* pNode)
{
bool done;
stack s;

Node* cursor = pNode; //set cursor to root of binary tree
done = false;

while (!done)
{
if(cursor != NULL)
{
s.push(cursor); //place pointer to node on the stack
//before traversing the node's left subtree
cursor = cursor->Left; //traverse the left subtree
}
else //backtrack from the empty subtree and
//visit the node at the top of the stack;
//however, if the stack is empty, you are
//done
{
if (!s.empty())
{
cursor = s.top();
s.pop();
cout <<" "<Val;
cursor = cursor->Right;
}
else
done = true;
}
}


}
void PostOrderRecursive(Node* pNode)
{
if(pNode->Left != NULL)
PostOrderRecursive(pNode->Left);
if(pNode->Right != NULL)
PostOrderRecursive(pNode->Right);
cout<<" "<Val;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node* Head = NULL;
InsertNode(&Head,6);
InsertNode(&Head,4);
InsertNode(&Head,5);
InsertNode(&Head,2);
InsertNode(&Head,3);
InsertNode(&Head,1);
InsertNode(&Head,8);
InsertNode(&Head,7);
InsertNode(&Head,9);
cout< < "Recursive Inorder Traversal :";
InOrderRecursive(Head);
cout< < endl < < "Non recursive Inorder Traversal :";
InOrderNonRecursive(Head);
cout< < endl < <"Recursive Preorder Traversal :";
PreOrderRecursive(Head);
cout< < endl < < "Non recursive Preorder Traversal :";
PreOrderNonRecursive(Head);
cout< < endl < < "Recursive Postorder Traversal :";
PostOrderRecursive(Head);
return 0;
}

Find the first unique charater in a string.

#include <>
using namespace std;
int FindFirstUniqueChar(char* szString,char* uniqueChar)
{
if((szString == NULL) (uniqueChar == NULL))
return -1;
int indexPos[257];
int count[257];
char* temp = szString;
memset(uniqueChar,0,(sizeof(uniqueChar)/sizeof(&uniqueChar[0])));
memset(count,0,257*sizeof(int));
memset(indexPos,-1,257*sizeof(int));
while(*temp)
{
count[*temp]++;
if( indexPos[*temp] == -1)
indexPos[*temp] = (temp - szString);
temp++;
}
int idx = 256;
for(int i = 0; i < 257; i++)
{
if((indexPos[i] <= idx) && (count[i] == 1))
{
*uniqueChar = char(i);
*(uniqueChar+1) = '\0';
idx = i;
}
}
if((idx != 256) && (*uniqueChar != NULL))
{
return 0;
}
return -2;
}
int main ()
{
char ch[2];
int ret = FindFirstUniqueChar("tomato",ch);
return 0;
}

Finding if a character is present in a string

Finding if a character is present in a string
#include "stdafx.h"
#include <>
#include <>
#include <>
using namespace std;
bool CheckCharPresent(_TCHAR *str,_TCHAR ch)
{
if((str == NULL)(ch == NULL))
return false;
_TCHAR *ptr = str;
for(unsigned i = 0; i < _tcslen(str); i++)
{
if(ptr[i] == ch)
return true;
}
return false;
}


int _tmain(int argc, _TCHAR* argv[])
{
bool val = CheckCharPresent(_TEXT("Rajesh"),_TEXT('h'));
val = CheckCharPresent(_TEXT("h"),NULL);
val = CheckCharPresent(NULL,_TEXT('h'));
return 0;
}

BruteForce Algorithm - finding a substring in a string

void BruteForceAlgo(char * szString, int iLenString, char* szPattern, int iLenPattern)
{
int i, j;
for(i = 0; i <= (iLenString - iLenPattern); i++)
{
for(j = 0; j < iLenPattern;)
{
if(szString[i+j] == szPattern[j])
j++;
else break;
}
if(j == iLenPattern)
printf("Pattern found at position %d\n",i+1);

}
}
int main(int argc, char* argv[])
{
BruteForceAlgo("HotalHotelHotalHotel", 20,"Hotel",5);
printf("\n%d\n", atoi_CustomImplementation("-1998"));
return(0);
}

Google - Project 10 to the 100th.

Project 10¹⁰⁰ (pronounced "Project 10 to the 100th") is a call for ideas to change the world by helping as many people as possible. - Extract from the site.

Link: http://www.project10tothe100.com/how_it_works.html

Unfortunately, the idea submission day is over.I believe we can still make a difference by voting.

Google 10 years story.

It is worth reading how Google made it's way till here.
Check the link http://www.google.com/tenthbirthday/#start

The story has links to some good materials.

Good Data Structure Applications link on MSDN

http://msdn.microsoft.com/en-us/library/ms364091(VS.80).aspx

Given a number 'n'. Find the number of trailing zeros in n factorial.

Technique:
Number of Trailing zeros = floor(num / 5) + floor(num / 5^2) + floor(num / 5^3) + ....

#include <>
using namespace std;
void main()
{
int n;
printf("Enter a value : ");
scanf("%d", &n);

int cntOfZero = 0;
int powersof5 = 5;
while ( n / powersof5 )
{
cntOfZero += n / powersof5;
powersof5 *= 5;
}
printf("Num of zeros : %d\n", cntOfZero);
}

Optimal way to check if a given number is prime

Technique:
Prime numbers 2,3,5,7,11,13,17,19,.....
Except for 2 and 3, rest of the prime numbers would be in the form 6n-1 or 6n+1 where n = 1,2,... . The rule is not always true, for instance when n = 4 6n+1 is 25.
Given a number M, check if it is divisible from 2 to the floor of square-root of M.

Example
Suppose the given number is 59, then floor of square root of 59 is 7.
ie try dividing 59 from 2,3,5 and 7.

Represent the two dimensional matrix using a 1D matrix and convert a(x,y)coordinante to a value in this array

if 2Da[3][4] = {00,01,02,03,10,11,12,13,20,21,22,23} is a two dimensional array, then the equivalent one dimensional array is 1Da[12] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11}

2Da[2,2] = 1Da[10] = 1Da[2*4+2]
2Da[2,0] = 1Da[8] = 1Da[2*4+0]
2Da[x,y] = 1Da[x*(2nd dim of 2Da)+y]

Given a pointer to a node in a single linked list how do you delete it?

Technique:
Copy the contents of next node into the current node and then do the following things:
1) copy the next pointer into a temporary pointer
2) set current node's next to next node's next
3) delete the node pointed by temporary pointer.

Obtain the pointer to Nth last node in a single linked list.

Technique: Suppose you are given 2 buses Bus-A and Bus-B travelling always at 100mph and you have to maintain a distance of 20mps between them. Then you will achieve this by staring Bus-A first from the source station. You start Bus-B only when Bus-A is 20 miles from source station.

Given a string"My name is Girish" write a code snippet to make it "Girish is name My" (one of the optimistic ways)

This is a 2 step process:
Step 1 : Reverse the whole string "My name is Girish". It becomes "hsiriG si eman My".
Step 2: Reverse each word which makes it "Girish is name My".

Complexity: SIMPLE.

Best Method to find the missing interger in a array of contiguous positive integers.

If we have a array 10 intergers, that contains all integers from 1 to 10 except for one interger which is zero, then what is the best method to find the missing number.

Eg arr[10] = { 1, 2, 3, 4, 5, 0, 7, 8, 9, 10}

Answer:
The sum of n contiguous integers is (n* (n + 1) ) / 2.
The sum of 10 contiguous integers is (10 * 11) / 2 = 55.
The actual sum of integers in arr = 1+2+3+4+5+0+7+8+9+10 = 49.
The missing number is 55 - 49 = 6.

This method is easier when compared to setting the bit position for each number and then checking which bit is not set.

Complexity: SIMPLE.

Finding the middle of a single linked list

Node* MidOfLLUsing2Ptrs(Node *head)
{
Node* OneHop;
Node* TwoHop;
//If no node return NULL
if(head == NULL)
return NULL;
//If only one node then that is the middle
if(head->next == NULL)
return head;
OneHop = head;
TwoHop = OneHop->next;
while((TwoHop != NULL)&&(TwoHop->next != NULL))
{
OneHop = OneHop->next;
TwoHop = TwoHop->next->next;
}
return OneHop;
}


Calling the function:
Node *MidOne = MidOfLLUsing2Ptrs(head);


Complexity: SIMPLE.

Reversing a single linked list recursively

#include <stdio.h>
#include "malloc.h"

struct Node
{
struct Node * next;
int num;
};

void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}
}

void DisplayLL(struct Node* head)
{
Node* temp = head;
int num = 1;
while(temp != NULL)
{
printf("The value at node %d is %d\n", num, temp->num);
num++;
temp = temp->next;
}
}

Node* ReverseLLRecursively(Node* head)
{
Node *temp;
if(head->next)
{
temp=ReverseLLRecursively(head->next);
head->next->next=head;
head->next=NULL;
}
else
temp=head;
return temp;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
DisplayLL(head);
Node *revHead = ReverseLLRecursively(head);
DisplayLL(revHead);
DisplayLL(head);
return 0;
}


Complexity: SIMPLE.

Print the contents of a Single Linked List in reverse order without using temporary pointer

#include "stdafx.h"
#include "malloc.h"

struct Node
{
struct Node * next;
int num;
};

void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}
}

void DisplayLL(struct Node* head)
{
Node* temp = head;
int num = 1;
while(temp != NULL)
{
printf("The value at node %d is %d\n", num, temp->num);
num++;
temp = temp->next;
}
}

void PrintReverse(int num, struct Node* head)
{
struct Node * temp = head;
if(temp->next != NULL)
{
num++;
PrintReverse(num, temp->next);
}
else
{
num++;
}
printf("The value at node %d is %d\n", num, temp->num);
}

int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
DisplayLL(head);
PrintReverse(0,head);
return 0;
}


Complexity: SIMPLE.

Deleting last but one node in Single Linked List

void DeleteLastButOneNode(Node ** head)
{
Node * temp = *head;
while(temp->next->next != NULL)
temp = temp->next;
temp->num = temp->next->num;
free (temp->next);
temp->next = NULL;
}


Complexity: SIMPLE.

Finding the loop in Single Linked List

#include <stdio.h>
#include "malloc.h"


struct Node
{
struct Node * next;
int num;
};


void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}

}
Node* GetNodeAddress(int num, struct Node* head)
{
Node *temp = head;
if(temp->num == num)
return temp;
else
while(temp->next != NULL)
{
if(temp->num == num)
return temp;
temp = temp->next;
}
if(temp->num == num)
return temp;
else
return NULL;
}

void CheckLoopInLL(Node* head)
{
Node * slowGuy = head;
Node * fastGuy = head;
Node *fasterGuy = head;
while(slowGuy != NULL && fastGuy != NULL && fasterGuy != NULL)
{
slowGuy = slowGuy->next;
fastGuy = fastGuy->next->next;
fasterGuy = fasterGuy->next->next->next;
if((slowGuy == fastGuy)(slowGuy == fasterGuy)(fastGuy == fasterGuy))
{
printf("There is a loop");
break;
}

}
}

int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
insertIntoLL(&head,60);
insertIntoLL(&head,70);
insertIntoLL(&head,80);
insertIntoLL(&head,90);
insertIntoLL(&head,100);
insertIntoLL(&head,110);
insertIntoLL(&head,120);
insertIntoLL(&head,130);
insertIntoLL(&head,140);
insertIntoLL(&head,150);
insertIntoLL(&head,160);
insertIntoLL(&head,170);
Node* node30 = GetNodeAddress(30,head);
Node* node170 = GetNodeAddress(170,head);
node170->next = node30;
CheckLoopInLL(head);
return 0;
}

Complexity: SIMPLE.

Size of Empty class

CONCEPT:
Object has a unique state, behaviour and identity.

class Empty { };
The size of an object of empty class is one byte.
If was zero then array of 100 object would all be pointing to the same memory location.

Complexity: SIMPLE.

Swapping 2 numbers without using one more variable

int a = 7;
int b = 8;
b = a + b; // 7 + 8 = 15
a = b - a; // 15 - 7 = 8
b = b - a; // 15 - 8 = 7

It can be used for other basic datatypes like char, double, float, long.
This solution however has the problem of overflow/underflow, so does

a = a * b;
b = a / b;
a = a / b;

For variables of same size XORing provides better solution.
a = a ^ b;
b = a ^ b;
a = a ^ b;


Complexity: SIMPLE.

Multipling a number by 7 without using * or + operator.

iNumIntoSeven = iNum <<3 ; //Equivalent to multiplying by 8.
iNumIntoSeven = iNumIntoSeven - iNum;

Complexity: SIMPLE.

Making a class Non Derivable in C++

CONCEPT USED:
Private members can be accessed only from within the class or by the friend of the class.

CODE SNIPPET:
class Usable;

class Usable_lock {
friend class Usable;
private:
Usable_lock() {}
Usable_lock(const Usable_lock&) {}
};

class Usable : public virtual Usable_lock {
public:
Usable();
Usable(char*);
// ...
};

Usable a;

class DD : public Usable { };

DD dd; // error: DD::DD() cannot access
// Usable_lock::Usable_lock(): private member

Complexity: INTERMEDIATE.

x+(~x+1)

#include <stdio.h>

void main(void){

int x = 100;
printf("%d",(x+(~x+1)));

}


Answer:
(~x+1) == one's compliment + 1 == two's compliment of x.
The sum of any number and it's 2's compliment is zero.

Complexity: INTERMEDIATE.