Converting a binary tree into a single linked list.

Find sum of two even numbers in a array

// findsumof2evens.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
/* int Find2Evens(int iLen, int* arr)
* IN: iLen - length of array
* arr - array of list
* OUT: -1 if list is empty the sum otherwise
*/
int Find2Evens(int iLen, int* arr)
{
int sum = 0;

//if there are no element in array
if((iLen == 0)|| (arr == NULL))
return -1;//no case we get the sum of 2 even nos to be -1 except in error case

//if there is only one element
if(iLen == 1)
if(arr[0]%2 == 0)
return arr[0];

int* iEven1 = NULL;
int* iEven2 = NULL;
for(int i = 0; i < iLen; i++)
{
if(arr[i]%2 == 0)
{
if((iEven1 == NULL)||(arr[i] > *iEven1))
{
iEven2 = iEven1;
iEven1 = &arr[i];
continue;
}
if(arr[i] != *iEven1)//if it a array like {1,4,4,5}
{
if((iEven2 == NULL)||(arr[i] > *iEven2))
{
iEven2 = &arr[i];
}
}
}
}
if((iEven1 == NULL)&&(iEven2 == NULL))
return -1;
if(iEven2 == NULL)
return *iEven1;
return *iEven1 + *iEven2;
}

int _tmain(int argc, _TCHAR* argv[])
{
int len = 4;
int arr[] = {1,-4,-2,7};
Find2Evens(len,arr);
return 0;
}

Find the index of first unique occurance of a character in a array - least time complexity

#include
//Complexity of the algorithm is 2n
int FindIndexOfFirstUniqueOccurance(char * arr)
{
if(arr == NULL)
return NULL;
//have a counter for each character
char iArr[256];
memset(iArr,0,256*sizeof(char));
char *ptr = arr;
while(*ptr)
{
iArr[*ptr]++;//increment the counter
ptr++;
}
ptr = arr;
while(*ptr)
{
if(iArr[*ptr] == 1)//the one that has a one set is the unique
return static_cast(ptr - arr);
ptr++;
}
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
char * ptrarr = "abcbbcadfg";
int i = FindIndexOfFirstUniqueOccurance(ptrarr);
return 0;
}

Implementing Queue using one Stack.

class Stack
{
private:
int ar[10];
int top;
public:
Stack():top(-1){}
void Push(int i)
{
if(top <= 10)
{
ar[++top] = i;
}
}
int Pop()
{
if( !IsEmpty())
return ar[top--];
else
return -1;
}
bool IsEmpty()
{
if( top <= -1)
return true;
return false;
}
};

class Queue
{
private:
Stack st;
public:
void Enqueue(int i)
{
st.Push(i);
}
int Dequeue()
{
int iVal = st.Pop();
if(st.IsEmpty())
return iVal;
else
{
int ret = Dequeue();
st.Push(iVal);
return ret;
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
Queue q;
q.Enqueue(10);
q.Enqueue(20);
q.Enqueue(30);
int i = q.Dequeue();
i = q.Dequeue();
i = q.Dequeue();
return 0;
}

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)