Maximum Subarray Problem

Maximum subarray problem can be solved in multiple ways. Here we will look at some of the approaches.

Approach 1:  Brute Force

In case of brute force we will be finding all the possible subarrays and comparing their sizes to find out the maximum sum subarray.
 

void MaxSumSubArray( int * a, int size) {     int MaxSum = a[0];     int MaxSumStart = 0, MaxSumEnd = 0;     for( int i = 1; i < size; i++)     {         int tempSum = 0;         int j = i;         while(j>=0)         {             tempSum += a[j];             if ( tempSum > MaxSum )             {                 MaxSum = tempSum;                 MaxSumStart = j;                 MaxSumEnd = i;             }             j--;         }     }     cout << "Max Sum in the array : " << MaxSum << endl;     cout << "Maz Sum Start : " << MaxSumStart << "  MaxSumEnd : " << MaxSumEnd << endl; }

Approach 2:

We can modify the brute force algorithm in order to use the existing max subarray to find out next maximum subarray as given below.

void MaxSumSubArray( int * a, int size) {     int MaxSum = a[0];     int MaxSumStart = 0, MaxSumEnd = 0;     for( int i = 1; i < size; i++)     {         int tempSum = 0;         int j = i;         int tempStart = MaxSumStart;         while(j>=tempStart)         {             tempSum += a[j];             if ( tempSum > MaxSum )             {                 MaxSum = tempSum;                 MaxSumStart = j;                 MaxSumEnd = i;             }             j--;         }     }     cout << "Max Sum in the array : " << MaxSum << endl;     cout << "Maz Sum Start : " << MaxSumStart << "  MaxSumEnd : " << MaxSumEnd << endl; }

Approach 3: Kadane's algorithm

This approach uses simple mechanism, just go on adding the numbers in the sum till the time sum is greater than zero, but maintain the maximum sum found till the time. This is C++ variation of Kadane's algorithm.

void MaximumSubArraySum(vector<int> input) {     if (input.size() > 0)     {         int sum = 0;         int MaxSum = 0;         int start = 0;         int end = 0;         for (int i = 0; i < input.size(); i++)         {             sum += input[i];             if (sum > 0)             {                 if (sum > MaxSum)                 {                     MaxSum = sum;                     end = i;                 }             }             else             {                 sum = 0;                 start = i;             }         }         cout << "Max Sum : " << MaxSum << " sub Array : " << start + 1 << " - " << end << endl;     } }

Printing Binary tree in leverl order C++

Given a binary tree, print tree in level order. Consider tree given in below image 

For above tree the level order should be printed as 

9

15  8

4  3  11

Approach 1:

Try to solve this problem in iterative manner. If we go iteratively from root to each level we can easily print the level order. But the problem here will be you should store the next level nodes on every level. This we can achieve using a queue of nodes. So while iterating any level we will add next level nodes in the temporary queue and will pull back those for next iteration. 

Function "PrintLevelOrderIterative" uses the method describe here.

void PrintLevelOrderIterative(Node * pRoot) {     if (pRoot)     {         queue<Node*> nodes;         nodes.push(pRoot);         while (!nodes.empty())         {             queue<Node*> temp;             while (!nodes.empty())             {                 Node * node = nodes.front();                 nodes.pop();                 cout << node->data << " ";                 if (node->pLeft)                     temp.push(node->pLeft);                 if (node->pRight)                     temp.push(node->pRight);             }             swap(nodes, temp);             cout << endl;         }     } }

The above approach can be modified to use single queue as well by using NULL pointer as end of each level as done in below code.

void PrintLevelOrderWithSingleQueue(Node * pRoot) {     if (pRoot)     {         queue<Node *> nodesQ;         nodesQ.push(pRoot);         nodesQ.push(NULL);         while (!nodesQ.empty())         {             Node * tmp = nodesQ.front();             nodesQ.pop();             if (tmp)             {                 cout << tmp->data << "  ";                 if (tmp->pLeft)                     nodesQ.push(tmp->pLeft);                 if (tmp->pRight)                     nodesQ.push(tmp->pRight);             }             else             {                 cout << endl;                 if (!nodesQ.empty())                     nodesQ.push(NULL);             }         }     } }

Approach 2:
The above approach will require the storage for storing the two level nodes, current level nodes as well as next level nodes. If we dont want that then we can use the recursive approach. Here first we will find out the height of the tree, so that we know at what level to stop. Then go recursive in in-order manner and print each level every time. This approach requires "n long(n)" time complexity where "n" denotes nodes in the given binary tree.

void PrintLevel(Node * root, int level, int current) {     if (root)     {         current++;         if (current < level)         {             PrintLevel(root->pLeft, level, current);             PrintLevel(root->pRight, level, current);         }         if (current == level)         {             cout << root->data << "  ";         }     } } int max(int a, int b) {     return (a > b ? a : b); } int HeightOfTree(Node * root) {     if (root)     {         return (1 + max(HeightOfTree(root->pLeft), HeightOfTree(root->pRight)));     }     return 0; } void PrintLevelOrderRecursive(Node * root) {     if (root)     {         int height = HeightOfTree(root);         int counter = 1;         while (height >= counter)         {             PrintLevel(root, counter, 0);             cout << endl;             counter++;         }     } }

Check if the given list is palindrome

You are given with the singly linked list of say having characters, you have to tell whether the list is palindrome or not.

The list is palindrome when if you iterate the list from both the ends it should generate the same string. This problem can be solved in multiple ways. Some of the approaches are discussed here.


Approach 1: Brute force

• Generate the string out of the list. 
• Now check if the list is palindrome, by simple traversing the string from both the ends and comparing each character during traversal.

This approach has many shortcomings such as space required and multiple traversals for palindrome confirmation.

 

Approach 2: Reverse the list from middle

• Find out the mid element of the list by using two pointer ( slow will increment once, fast will increment twice).
• From the middle to the end reverse the list. 
• Now use two pointers one pointing to the start of the list and other pointing to middle of the list. 
• Then iterate list till middle ( from start) comparing each element from middle till end.

In this approach we have overhead of reversing the list. If we are not allowed to modify the list then we will have to revert back the modification done.

 

Approach 3: Use recursion

• Use the reference pointer variable.
• Use slow and fast pointers to reach till middle of the list using recursion.
• Now once we have reached to the middle of the list, assign the middle element to the reference pointer variable.
• Now while coming back from the recursion, compare at each step the element with the reference variable value. 
• Point to the next node of reference variable and come out of recursion.

This is sort of reversing of the list but here we are not modifying the list. But this method will require the stack space for recursion equal to the half of the size of the list.
Advantage of this approach is we are using single pass for verifying if list is palindrome.

struct  Node {     char data;     Node * pNext; }; bool IsListPalindrome(Node* head, Node* current, Node* & reverse) {     if (head)     {         head = head->pNext;         if (head)             head = head->pNext;         else         {             reverse = current->pNext;             return true;         }         if (IsListPalindrome(head, current->pNext, reverse))         {             if (current->data == reverse->data)             {                 reverse = reverse->pNext;                 return true;             }         }         return false;     }     reverse = current;     return true; }

Root to leaf path with specified sum in a binary tree

The problem here is "To find if there is any root to leaf path with specified sum in a binary tree."

Consider the binary tree shown in the tree below .

We have to find whether there is any path which goes from root to any leaf having sum equal to given sum.
For example if we have given sum as 28 then there can be two paths which has sum 28.
9->8->11 or 9 ->15->4.

Approach 1:

• Perform the level order traversal. 
• During  level order traversal find out all the root to leaf paths exists in the tree.
• Now for each path check if all the nodes sum equals to given sum. 

This approach will require large space to store all the paths formed during level order. Then again we will have to iterate through all the nodes for finding the sum. 

Approach 2:

• Perform the post order traversal. 
• During post order traversal maintain stack of the nodes visited and sum so far.
• If we have reached to leaf then check if sum so far is same as required sum. 
• If yes.. print the path else pop the current root and continue.

This approach does usages the temporary space but that will always be equal to maximum height of the tree. Also as every node is visited only once the time complexity will be O(n) where n being number of nodes in the tree.

 

Code below shows both ways to check if given sum exists in the any root to leaf path if exists then how to print the path.

struct Node {     int data;     Node * pLeft;     Node * pRight; }; //Just check if sum exists bool CheckIfSumExistInRTLPath(Node * pRoot, int sum, int currentSum) {     if (pRoot)     {         currentSum += pRoot->data;         bool left = CheckIfSumExistInRTLPath((pRoot->pLeft, sum, currentSum);         bool right = CheckIfSumExistInRTLPath((pRoot->pRight, sum, currentSum);         if (!(pRoot->pLeft) && !(pRoot->pRight) && currentSum == sum)         {             cout << " Found matching sum at the leaf : " << pRoot->data << endl;             return true;         }         return (left || right);     }     return false; } //Print the path if provided sum exists bool GetRTLPathForSum(Node * pRoot, int sum, int currentSum, stack<Node*> & path) {     if (pRoot)     {         currentSum += pRoot->data;         path.push(pRoot);         bool left = GetRTLPathForSum(pRoot->pLeft, sum, currentSum, path);         bool right = GetRTLPathForSum(pRoot->pRight, sum, currentSum, path);         if (!(pRoot->pLeft) && !(pRoot->pRight) && currentSum == sum)         {             cout  << endl << " Found matching sum at the leaf : " << pRoot->data << "   The PAth : " << endl;             stack<Node*> temp;             while (!path.empty())             {                 Node * node = path.top();                 temp.push(node);                 path.pop();                 cout << node->data << "  ";             }             while (!temp.empty())             {                 path.push(temp.top());                 temp.pop();             }             path.pop();             return true;         }         path.pop();         return (left || right);     }     return false; }

Verify whether a given binary tree is binary search tree or not

There are many ways to find out whether given binary tree is binary search tree or not.

Simplest way to verify is to traverse the tree in in-order fashion, create an array of node values while traversing in-order. Now check if this array is sorted or not.

We will extend similar approach for our solution. Instead of creating a array, we will just use the last value during in-order traversal to verify if its less than the current node value. If yes then the tree is binary tree.

Code below implements the approach discussed.

struct TreeNode {     int data;     TreeNode * pLeft;     TreeNode * pRight; }; bool VerifyIfBST(TreeNode * pRoot, int & lastvalue) {     if (pRoot)     {         bool  bLeft = VerifyIfBST(pRoot->pLeft, lastvalue);         bool  bRoot = true;         if (lastvalue > pRoot->data)         {                 bRoot = false;         }         lastvalue = pRoot->data;         bool bRight = VerifyIfBST(pRoot->pRight, lastvalue);         return ( bLeft && bRoot && bRight);     }     else         return true; }

The function will return true if tree is empty or if tree is binary search tree.

Implementing Counting sort C++

Counting sort is a technique which sorts input in o(n) time complexity if it falls in particular range. 
As the input falls in particular range, the counting method works well and can be rearranged easily.

Counting sort maintain count of each element appearing in the input then it places those in the order.

Code below sorts the input array A and returns B as a sorted array.  Even you can choose to return sorted data in same array by copying B data to input array.

typedef vector<int> IntVect; void CountingSort(IntVect & A, IntVect & B, int range) {     IntVect temp;     for (size_t i = 0; i < range; i++)     {         temp.push_back(0);     }     for (int i = 0; i < A.size(); i++)     {         temp[A[i]] += 1;     }     for (int i = 1; i < temp.size(); i++)     {         temp[i] += temp[i - 1];     }     for (int i = 0; i < A.size(); i++)     {         B[temp[A[i]] - 1] = A[i];         temp[A[i]] -= 1;     } }

Counting sort described here takes o(n) additional space.

Implementing bubble sort in C++

Bubble sort is the simplest sorting algorithm. It can be viewed as the lighter values coming up step by step.

Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.

The code below implements the bubble sort.

typedef vector <int> IntVect; void SwapInts(int & A, int & B) {     int temp = A;     A = B;     B = temp; } void BubbleSort(IntVect & A) {     for (int i = A.size() - 1; i >= 0; i--)     {         for (int j = 0; j < i; j++)         {             if (A[j] > A[j + 1])             {                 SwapInts(A[j], A[j + 1]);             }         }     } }

The bubble sort has O(n^2) average and worst case complexity.

Implementing heap sort algorithm in C++

Heapsort is a comparison-based sorting algorithm to create a sorted array, and is part of the selection sort family.

Heap sort build the max heap first. The max heap is where the highest element is at the front of the array. Once max heap is built then swap the highest element to end.

Now minimize the size of heap by and fulfill the max heap property. So that highest from the remaining array will be at the front. Now again swap this with second last element from the array. Follow this process till first element.

typedef vector<int> IntVect; inline int Left(int i) {     return (2 *  i); } inline int Right(int i) {     return ((2 * i) + 1); } void MaxHeapify(IntVect & A, int i, int end) {     int left = Left(i);     int right = Right(i);     int max = i;     if (left < end && A[left] > A[max])         max = left;     if (right < end && A[right] > A[max])         max = right;     if (max != i)     {         SwapInts(A[max], A[i]);         MaxHeapify(A, max, end);     } } void BuildMaxHeap(IntVect & A, int end) {     for (int i = end / 2; i >= 0 ; i--)     {         MaxHeapify(A, i, end);     } } void HeapSort(IntVect & A) {     BuildMaxHeap(A, A.size());     for (int i = A.size() - 1; i > 0; i--)     {         SwapInts(A[0], A[i]);         MaxHeapify(A, 0, i);     } }

The BuildMaxHeap method can be used for creating the priority queue as well.

Implementing Quick Sort in C++

Quicksort is a sorting algorithm which picks one element at a time and places it at its correct position, during this it also places elements less than that element on its left and element greater than that element on right side.

The code below implements the Quick sort in recursive manner.

typedef vector<int> IntVect; int QuickPartition(IntVect & A, int start, int end) {     int  key = A[end];     int j = start - 1;     for (int i = start; i < end; i++)     {         if (A[i] < key)         {             int temp = A[++j];             A[j] = A[i];             A[i] = temp;         }     }     j++;     A[end] = A[j];     A[j] = key;     return j;     } void QuickSort(IntVect & A, int start, int end) {     if (start < end)     {         int pivot = QuickPartition(A, start, end);         QuickSort(A, start, pivot - 1);         QuickSort(A, pivot + 1, end);     } }

In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.

Cloning link list with Random node pointer

You are given a link list which contains the data, next pointer and random pointer which points any random node in the list. Your task is to clone this list.

This problem can be solved using multiple approaches.

Approach 1: Brute force approach

• Clone the new list.
• Now traverse form start each time in both list for finding  out the random nodes and update the random node.

This approach will take the O(n^2) time complexity.

 

Approach 2: Use Temporary Storage 

Simply go on creating the clone and storing the map of old pointer address to its respective new pointer address and during cloning copy the random pointer address as is in the new list.Let's say pHead is pointer to old list head and pNewHead is pointer to new list, then the map will contain key as pHead and value will be pNewHead. Also pNewHead->pRandom = pHead->pRandom.

Now once new list is ready, traverse it from head again and replace each random pointer with its respective new random pointer by look up in the map.  

This way with the temporary storage of map we can clone the list as shown in below code.

struct RandomNode {     int data;     RandomNode * pNext;     RandomNode * pRandom;     RandomNode(int value) : data(value), pNext( NULL), pRandom( NULL)     {        } }; typedef  map<RandomNode *, RandomNode *> RandNodeMap; RandomNode *  CloneListUsingMap(RandomNode * pHead) {     if (pHead)     {         RandNodeMap nodeMap;         RandomNode * pTemp = pHead;         RandomNode * pNewHead = new RandomNode(pTemp->data);         pNewHead->pRandom = pTemp->pRandom;                RandomNode * pNewTemp = pNewHead;         nodeMap.insert(make_pair(pTemp, pNewTemp));                pTemp = pTemp->pNext;         while (pTemp)         {             RandomNode * pClone = new RandomNode(pTemp->data);             pClone->pRandom = pTemp->pRandom;             nodeMap.insert(make_pair(pTemp, pClone));             pNewTemp->pNext = pClone;                    pNewTemp = pNewTemp->pNext;             pTemp = pTemp->pNext;         }         pNewTemp = pNewHead;         while (pNewTemp)         {             RandNodeMap::const_iterator kit =  nodeMap.find(pNewTemp->pRandom);             pNewTemp->pRandom = kit->second;             pNewTemp = pNewTemp->pNext;         }         return pNewHead;     }     return NULL; }

The issue with the above solution is that we require the temporary storage for storing the addresses in the map.

Approach 3: Modify the existing list temporary

If we want to avoid the temporary storage, we can do that just by modifying the existing list. 
We will create the new list in the same fashion as created above. Means copy the random node address as is in the clone node random address location.
Also during creating the cloned list, attache every cloned node will be the next node of existing node.  Now for updating the random node we have to visit just the next node of the random node.
Once random nodes are updated separate the two lists.
  

RandomNode * CloneList(RandomNode * pHead) {     if (pHead)     {         RandomNode * pNewHead = new RandomNode(pHead->data);         RandomNode * pNew = pNewHead;         pNewHead->pRandom = pHead->pRandom;         RandomNode * orgList = pHead->pNext;         pHead->pNext = pNewHead;         pNewHead->pNext = orgList;         while (orgList)         {             //Create new node             RandomNode * nextNode = new RandomNode(orgList->data);             nextNode->pRandom = orgList->pRandom;                //Current list next will be new node next             nextNode->pNext = orgList->pNext;             RandomNode * tempNode = orgList;             orgList = orgList->pNext;                        //Insert it to existing list             tempNode->pNext = nextNode;         }                //Now update the random nodes of new list         pNew = pNewHead;         while (pNew)         {             pNew->pRandom = pNew->pRandom->pNext;             pNew = pNew->pNext;             if (pNew)                 pNew = pNew->pNext;             else                 break;         }         //Break entire list in to original list and cloned list         orgList = pHead;         pNew = pNewHead;         while (pNew)         {             orgList->pNext = pNew->pNext;             orgList = orgList->pNext;             if (orgList)                 pNew->pNext = orgList->pNext;             else             {                 pNew->pNext = NULL;                 break;             }             pNew = pNew->pNext;         }         return pNewHead;     }     return NULL; }

This technique just requires total three iterations of the list.

Swaping kth node from start and kth node from end from the singly link list

In order to  swap the linked list nodes you will require the previous nodes of the nodes to be swapped so that you can maintain the list.
 
We already know how to find the kth node from the end of the singly link list. We will first search for the kth node from the start and its previous node. Then we will find out the kth node from the end and its previous node. 

Then swapping these nodes will be a easy task.

//Code returns the head of the modified list. Node * SwapKthNodes(Node * pHead, int nKth) {     if (pHead)     {         Node * pKth = pHead;         Node * pKthPrev = NULL;         int i = 1;         while (pKth && i < nKth)         {             i++;             pKthPrev = pKth;             pKth = pKth->pNext;         }         //Didn't find the kth element         if (!pKth)             return pHead;         Node * temp = pKth;         Node * pKthFromEnd = pHead;         Node * pKthPrevFromEnd = NULL;         //Searching the Kth node from end         while (temp->pNext)         {             pKthPrevFromEnd = pKthFromEnd;             pKthFromEnd = pKthFromEnd->pNext;             temp = temp->pNext;         }         if (pKthFromEnd == pKth)             return pHead;         //kthpos == 1         if (!pKthPrev)         {             pKthPrevFromEnd->pNext = pHead;             Node * pTemp = pHead->pNext;             pHead->pNext = pKthFromEnd->pNext;             pKthFromEnd->pNext = pTemp;             return pKthFromEnd;         }         //KthFrom end might be the first node         if (!pKthPrevFromEnd)         {             Node * pTemp = pKthFromEnd->pNext;             pKthFromEnd->pNext = pKth->pNext;             pKth->pNext = pTemp;             pKthPrev->pNext = pKthFromEnd;             return pKth;         }         pKthPrevFromEnd->pNext = pKth;         Node * pTemp = pKth->pNext;         pKthPrev->pNext = pKthFromEnd;         Node * pTemp2 = pKthFromEnd->pNext;         pKthFromEnd->pNext = pTemp;         pKth->pNext = pTemp2;         return pHead;     }     return NULL; }

Find kth node from end in the singly linked list

You can not traverse the liked list backward unless you have stored it on the stack or at some temporary storage. So if you want to find the kth node from the end without using the temporary storage you will have to adopt different technique.

Consider a link list : 1-> 3 -> 9 -> 23 -> 14 ->NULL

Now 23 is the second last element in the list. To find this element we will use the temp linked list pointer. We will increment that pointer so that it will point to kth position from head. Once the temp pointer is pointing to kth node from head, now increment head and the temp pointer till the temp pointer points to last node of the list.  

This ways the the head will point to the kth node from the end. Code below usages the similar technique.

struct Node {     int data;     Node * pNext; }; Node * FindKthNodeFromEnd(Node * pHead, int kthPos) {     if (pHead)     {         Node * pTemp = pHead;         int i = 1;         while (i < kthPos && pTemp)         {             pTemp = pTemp->pNext;             i++;         }         if (pTemp)         {             while (pTemp->pNext)             {                 pHead = pHead->pNext;                 pTemp = pTemp->pNext;             }             return pHead;         }     }     return NULL; }

Find the duplicate number from unsorted array

There are many methods to find out the duplicate numbers form the array. We can use the map which will store the values from the array as a key, while storing itself we can check for duplicate insertion. If map.insert flags out duplicate insertion that means we found out duplicate.
Code below uses the same technique to find the duplicate.

typefec vector<int> IntVect; void PrintDuplicateNumberFromUnsortedArrayWithMap(IntVect & A) {     std::map<int, int> mapOfInt;     std::pair<std::map<int, int>::iterator, bool> retVal;     for (int  i = 0; i < A.size(); i++)     {         retVal = mapOfInt.insert(make_pair(A[i], i));         if (retVal.second == false)         {             cout << "Found Duplicate for : " <<  A[i] << "  at : " << retVal.first->second  << endl;         }     } }

The above method is faster way to find the duplicate but it requires the storage.

If we want to avoid the temporary storage then we can just sort the array then find the duplicate by comparing the consecutive elements just in one pass as given in code below.

void FindDuplicateWithSorting(IntVect & vect) {     if (vect.size() > 0)     {         // Sort vector using any standard sort like quick sort         int prev = vect[0];         for (size_t i = 1; i < vect.size(); i++)         {             if (prev == vect[i])             {                 cout << "Duplicate exists for the number : " << prev << endl;             }             prev = vect[i];         }     } }

This code will have the time complexity equal to the time complexity of the sorting algorithm used for sorting the array because after sorting we will be using just one pass to search the duplicate.

Searching number in sorted but rotated array

Consider a sorted array as below 

15  19  29  34  35  49   96  97 99

the rotated sorted array of this array can be 

49 96  97 99  15  19  29  34  35  

Approach 1:
We have to find the element from this array. With linear search we can find the element in o(n) time complexity. But as array is sorted we should take advantage of this property.
Approach 2:
We can use the binary search for searching the PIVOT element. Pivot element will denote the starting point of rotation.  You can check the Binary search is implementation here.
With this we will minimize the search area and then apply the binary search again on the remaining array.

Approach 3:
With above approach we will be doing two pass of binary search one for searching pivot and one for searching the number. We can even think of modifying the binary search as we know if the array is rotate. 
Code below shows how we can use modified binary search method to find element in sorted but rotated array.
   

//Num is number to search int SearchNum(vector<int> & input, int start, int end, const int num) {     if (start <= end)     {         int mid = start + (end - start) / 2;         if (num == input[mid])             return mid;         if (input[mid] < input[end])         {             if (input[mid] < num && input[end] >= num)                 return SearchNum(input, mid + 1, end, num);             else                 return SearchNum(input, start, mid - 1, num);         }         else         {             if (input[start] <= num && input[mid] > num)                 return SearchNum(input, start, mid - 1, num);             else                 return SearchNum(input, mid + 1, end, num);         }     }     return -1; }

The function will return -1 if it failed to find the number else it will return index of the number in the array.

Reversing circular singley link list

In last post we have see how to reverse the single link list. We had used the iterative method to reverse the list.
Consider that you have a circular list as shown below.

Now you have to reverse the list and break the circle.
Now you can use same approach of finding out the loop in the list as discussed in the previous post. Then reverse the list recursively. 

One thing to note here is that once you find out that there is loop in the list then find out the last node of the list and then you will have to break the loop.

void ReverseCircularSinglyList(Node *pHead, Node *pHeadNext, Node * pFar, Node * pOrgHead, bool & bFoundLoop, Node * & pNewHead) {     if (pHead)     {         if (pHead->pNext == NULL)             pNewHead = pHead;         if (!bFoundLoop)         {             Node * pTemp = pHead ->pNext;             if (pFar)                 pFar = pFar->pNext;             else                 bFoundLoop = true;             if (pFar)                 pFar = pFar -> pNext;             else                 bFoundLoop = true;             if (pFar == pTemp)             {                 bFoundLoop = true;                 //found the circle                 //Now search the starting point of the circle.                 pTemp = NULL;                 while (pOrgHead != pFar)                 {                     pTemp = pFar;                     pOrgHead = pOrgHead->pNext;                     pFar = pFar -> pNext;                 }                 pTemp->pNext = NULL;             }         }         ReverseCircularSinglyList(pHead->pNext, pHead, pFar, pOrgHead, bFoundLoop, pNewHead);         pHead->pNext = pHeadNext;     } } Node * ReverseCircularSLL(Node * pHead) {     Node * pNewHead = NULL;     bool bFoundLoop = false;     ReverseCircularSinglyList(pHead, NULL, pHead, pHead, bFoundLoop, pNewHead);     return pNewHead; }

Finding out if given arrays represent identical binary search tree (BST)

You are given two arrays of integers. You need to check if the binary search tree is generated out of two arrays considering first element as root, then will the trees be identical. You are not allowed to create the binary tree. 

The techniques is fairly simple. Just try to identify from root, left and right elements of every sub tree. E.g. in the array 5, 6, 3, 7, 2 
Root: 5 -> Left 3
Root: 5 -> Right 6 -> right 7
Root: 3 -> left 2
Root: 6 -> right 7

Follow this for both the arrays and check if the left and right element of every sub tree are in the same order if not both array can not generate the identical BST.

Code below demonstrate this technique.  

bool DoesGivenArraysRepresentIdenticalBST( vector<int> firstArray, vector<int> secondArray) {     if( firstArray.count() != secondArray.count() )         return false;     if( firstArray.size() <= 0)         return true;     //Check if the root of every sub tree is same     if( firstArray[0] != secondArray[0] )         return false;     if( firstArray.size() <= 1)         return true;     vector<int> left1;     vector<int> right1;     for(int i = 1; i < firstArray.size(); i++)     {         if( firstArray[0] < firstArray[i] )             right1.Add(firstArray[i]);         else             left1.Add(firstArray[i]);     }     vector<int> left2;     vector<int> right2;     for(int i = 1; i < secondArray.size(); i++)     {         if( secondArray[0] < secondArray[i] )             right2.Add(secondArray[i]);         else             left2.Add(secondArray[i]);     }     return DoesGivenArraysRepresentIdenticalBST( left1, left2 ) && DoesGivenArraysRepresentIdenticalBST( right1, right2 ); }

Detecting start of the loop in circular singly linked list

Consider a single linked list as below which has a loop at node 5.

As discussed in the last post we can detect if there is loop present in the list or not with use of the two pointers. To find out the start of the loop we will have to follow the same strategy. 

As we are traversing some x nodes before starting the loop hence the far and near pointer will meet at x nodes less location in the loop. If we traverse x nodes from start and x nodes from where the two pointers meet we can detect the start of the loop. 

The code below uses the same technique discussed above to detect the start of the loop in circular single linked list.

struct Node {     int data;     Node * pNext; }; Node * IsListCircular(Node * pHead) {     Node* pFar = pHead;     while (pHead != NULL && pFar !=NULL)     {         pFar = pFar->pNext;         if (pFar)             pFar = pFar->pNext;         else             return NULL;         pHead = pHead->pNext;         if (pFar == pHead)         {             return pFar;         }     }     return NULL; } Node * FindStartOfLoop(Node *pHead) {     Node * pTemp = IsListCircular(pHead);     if (pTemp)     {         while (pTemp != pHead)         {             pHead = pHead->pNext;             pTemp = pTemp->pNext;         }         return pHead;     }     return NULL; }

The function FindStartOfLoop will return the address of the start node of the loop else will return NULL.

Detecting loop in singly linked list

To detect loop in the circular singly linked list you will need two pointers. One near pointer and one far pointer.

Far pointer you will increment by two nodes where as near pointer you will increment by one so that if there is loop in the link list at some point both pointer will point to the same node. 

The code uses the similar technique.

struct Node {     int data;     Node * pNext; }; bool IsListCircular(Node * pHead) {     Node* pFar = pHead;     bool bHasLoop = false;     while (pHead != NULL)     {         if (pFar)             pFar = pFar->pNext;         else             break;         if (pFar)             pFar = pFar->pNext;         else             break;         pHead = pHead->pNext;         if (pFar == pHead)         {             bHasLoop = true;             break;         }     }     return bHasLoop; }