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; }