Code Samurai

Difference Between Sums of Odd and Even Levels in Binary Trees

2011-08-18T13:34:00.000-07:00

Question: calculate the difference between the sum of nodes at even level and sum of nodes at odd level.

Solution: recursion is the easiest way to solve this problem. At each non-null node of the tree, we have three things to do. 1) Find the difference between the node's left child with it's children by calling the function recursively on the node's left child. 2) Do the same thing for the node's right child. 3) Find the difference between the current node and the sum of it's left and right child. Here is the implementation in JavaScript:

function diffBetween(pRootNode)
{
   if (pRootNode === null || pRootNode === undefined) 
      return 0;

   var lvalue = diffBetween(pRootNode.pLChild);
   var rvalue = diffBetween(pRootNode.pRChild);

   var result = pRootNode.nData - (lvalue + rvalue);
   return result;
}

Explanation: the method takes in the root node of the binary tree that users want to compute the difference. Here are the steps:

Line 3 and 2, check for invalid input. This step acts as the case stopper for our recursion.
Line 6: find the difference between the left child and its children.
Line 7: find the difference between the right child and its children.
Line 9: find the difference between the current node and its children.
Line 10: finally returns the result.

If you have any comment, please post. Also if there is any part that is not clear, please also let me know :)

How to Reverse a String

2011-07-29T22:46:00.000-07:00

Question: given a string, reverse it. You can destroy the original string or return a new string that is the reverse of the original string. For example, if input is "abcde", output will be "edcba".

Solution: this is a simple problem. We just need to traverse the input string from last character to the first character. As we traversing the input string, we add its characters to the output string. At the end of the traversal, we have an output string that is the reverse of the original. Here is the code in JavaScript:

function sReverseStr(pInputStr)
{
   if (pInputStr === null || pInputStr === undefined)
      return;

   var pResultStr = "";
   
   for (var i = pInputStr.length - 1; i > -1; i--)
   {
      pResultStr += pInputStr.charAt(i);
   }

   return pResultStr;
}

Code Explanation: the code is straight forward. Here is the breakdown:

First, we check for invalid input. Nothing new here.
Next, we allocate a new string named pResultStr.
The for loop goes through each character in the input one by one from the end to the beginning. Then we add each of those character to the new string.
When the for loop finishes, pResultStr is now the reverse of the input. We simply return it.

That's all for this post. Thanks for reading :)

Minimum Distance Between Two Elements in an Array

2011-07-08T10:16:00.000-07:00

Question: given an array and two elements, find the minimum distance between the elements in the array. The array may have duplicates. For example, if the array is (2, 1, 3, 4, 0, 2, 5) and the two elements are 4 and 5, then the min distance is 3 because 4 is at index 3 and 5 is at index 6.

Solution: this problem can be solved using two index trackers. The idea is to loop through the array and keep track of the indices of elements that have the same values with the inputs. At the same time, calculate the distance between those two indices and keep the smallest distance.

This solution works great because it doesn't compare all possible distances of inputs when there are duplicates in the array. A naive solution would be computing all different distances between elements that have the same values with the inputs and then return the smallest distance. Here is the implementation in JavaScript:

function nMinDistanceBetweenTwoElements (nInputArray, nNum1, nNum2)
{
   if (nInputArray.length <= 0)
   {
      document.write("Empty Array!");
      return -1;
   }

   var nPos1 = nPos2 = nDis = nInputArray.length;

   for (var i = 0; i < nInputArray.length; i++)
   {
      if (nInputArray[i] == nNum1)
         nPos1 = i;
      else if (nInputArray[i] == nNum2)
         nPos2 = i;

      if (nPos1 < nInputArray.length && nPos2 < nInputArray.length)
      {
         if (nDis > Math.abs(nPos1 - nPos2))
            nDis = Math.abs(nPos1 - nPos2);
      }
   }

   return nDis == nInputArray.length ? -1 : nDis;
}

Code explanation: the method accepts three parameters. nInputArray is an array of integers. nNum1 and nNum2 are the two numbers that we must find the minimum distance between them. Here are the steps in the method:

First, we check for the length of the array. If the client passes in an empty or invalid array, we return -1 and an error message.
Next, we declare three variables. nPos1 and nPos2 keep track of the indices of the first number nNum1 and the second number nNum2 respectively. nDis keeps track of the minimum distance between the two numbers. We also initialize all of these variables to the input array's length because there is a chance that the input array doesn't contain both of the input numbers whose distance we must find. In other words, if the input array doesn't contain any of the two input numbers, nDis will equal the array's length at the end of the method. Moreover, we must also initialize nDis to a large number that is not obtainable by any pair of numbers in the array because we are trying to find the minimum distance. If we initialize nDis to 0, it's more complicated to use nDis to keep track of the minimum distance. nDis = 0 is already the smallest possible distance between any two elements in an array.
The for loop will go through the entire input array ,nInputArray once. At each iteration, we do the following:
- If the current element, nInputArray[i], equals to the first input number, nNum1, then assign nPos1 to that element's index, i. On the other hand, if the current element's value equals nNum2, then assign nPos2 to that element's index. Otherwise, we do nothing.
- Next, we check if both of the index trackers' values have changed. If the values of nPos1 and nPos2 are less than the input array's length, it means that nNum1 and nNum2 exist in the input array. Again, we are guarding against the possibility that nNum1 or nNum2 is not in the input array.
- If nPos1 and nPos2 are less than their initial values, then both nNum1 and nNum2 are present in nInputArray. Thus, we need to find out whether the new distance between nNum1 and nNum2 is less than the current minimum distance, nDis. If the new distance is less than nDis, we change nDis to the new distance. Note that we use the absolute value of the difference between nPos1 and nPos2 to figure out the distance. The reason are that nPos2 may be smaller than nPos1 and that we don't care about the numbers' order.
After the for loop, we check to see whether nDis is different from its initial value which is the input array's length. If nDis equals its initial value, input numbers are not present in the input array. We return -1 as an error indicator. However, if nDis is different from its initial value, both input numbers must be in the input array. Therefore, we return nDis as the minimum distance between those two numbers.

I hope the code and the explanation are clear. However, if you have any question, please let me know by emailing or commenting. Thanks for reading :)

Convert Binary Tree to Double Linked List in Zig-Zag Order

2011-07-01T09:10:00.000-07:00

Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order.

Solution: let's first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level. For example, take a look at this tree:

A zig-zag level-order traversal creates the list 1, 2, 3, 5, 4. It doesn't matter which direction the root is printed because there is only one node. However, since the second level is printed left to right, 2 then 3, the third level is printed from right to left, 5 then 4.

Now we understand the question, let's figure out how to solve this problem. Well, the only tricky part is to traverse the tree in zig-zag order. The other part, adding nodes to a linked list, is easy.

To solve this problem, we need two stacks. One stack stores nodes of levels that traversed from left to right. The other stores nodes of levels that traversed from right to left. The idea is to add the children of each node of the same level into a different stack than their parent. Thus, all children of the same level are in the same stack, separating one level from another. These children nodes are also pushed in the stack in the same direction with each other but opposite direction with their parents, so they can be traversed in the opposite direction to their parents. Moreover, as we traverse the tree, we add each node into a double linked list. Here is the implementation in C++:

struct Node* bt2ZigZagDoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;

  struct Node* head = root;
  struct Node* listIT = NULL;
  struct Node* prevNode = NULL;
  
  stack left2RightStack;
  stack right2LeftStack;

  left2RightStack.push(root);
  
  while (!left2RightStack.empty())
  {
    //add nodes from left to right to the list
    while (!left2RightStack.empty())
    {
      //set previous node
      prevNode = listIT;
    
      //pop a node in left2RightStack and add it to list
      listIT = left2RightStack.top(); 
      left2RightStack.pop();

      //add child nodes of the newly node in right to left direction
      if (listIT->left != NULL)
        right2LeftStack.push(listIT->left);
      
      if (listIT->right != NULL)
        right2LeftStack.push(listIT->right);

      //set left pointer of current node to the node in front of it
      listIT->left = prevNode; 

      //the previous node points to the current node in list
      if (prevNode != NULL)
        prevNode->right = listIT;
    }

    //add nodes from right to left to the list
    while (!right2LeftStack.empty())
    {
      prevNode = listIT;
      
      listIT = right2LeftStack.top();

      right2LeftStack.pop();

      if(listIT->right != NULL)
        left2RightStack.push(listIT->right);
        
      if(listIT->left != NULL)
        left2RightStack.push(listIT->left);

      listIT->left = prevNode;

      if (prevNode != NULL)
        prevNode->right = listIT;
    }
  }

  //connect linked the end node of list to NULL and the node in front of it
  listIT->right = NULL;
  listIT->left = prevNode;
  
  return head;
}

Code explanation: the method accepts the tree's root node as its parameter and return the head node to the double linked list.

First two lines check for null node, empty tree. If the tree is empty, we return an empty linked list.
The next three lines declare three pointers to tree nodes. head points to the head node of the linked list. We initialize it to the root node because the root node will be the first node in the list. listIT will be the iterator to traverse the tree. prevNode points to the last node visited by listIT. We need it to construct the double linked list since we must point the previous node to the current node and the current node back to previous node.
We also create two stacks that contain pointers to tree nodes. left2RightStack contains nodes in left to right order while right2LeftStack contains nodes in right to left order.
We then initialize left2RightStack by pushing the root node inside it.
There are three different while loops. The first while loop makes sure that we visit all nodes in the tree and add them into our double linked list. The two inner while loops make sure that we add the nodes level by level and in opposite directions. We do the following in the first inner while loop:
- First, we pop a node off the left2RightStack and assign it to listIT.
- Then, we add listIT's left child into the right2LeftStack before adding listIT's right child into the same stack. This guarantees that when we pop those children off the right2LeftStack they will be poped in the opposite order to their parent.
- After that, we add listIT into the linked list. Pointing its left pointer to the node before it, prevNode
- Finally, we point the right pointer of the prevNode to listIT. Remember we're making a double linked list, that's why we need to point the node in front of listIT, which is prevNode, to listIT.
- The while loop runs until there is no nodes left in left2RightStack.
After the first inner loop traverses a level from left to right, the second inner while loop traverses the next level from right to left. The process is similar to that of left-to-right traversal. The only difference is that we add right children to the stack before left children.
Once all nodes have been added into the double linked list, we'll connect the end node of the list to the node before it and to a null node as the node after it.
Lastly, we return head. In the beginning, we have already assigned head to the root node which is the first node of the list, so head is point at the first node in the list.

That's all for this problem. If you find any mistake or have better solution, please feel free to let me know. Thanks for reading :)

Check If an Integer's Bit Representation Is a Palindrome

2011-06-28T09:33:00.000-07:00

Question: how can you determine if a positive integer is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001.

Solution: an integer is palindrome when its bit representation is the same reading from left to right or from right to left. Thus, in order to know if it is a palindrome or not, we just have to check if the number's value is still the same when we read the number's bits backward (right to left). For example, 5 is 101 and when we read its bits from right to left, which is 101, the result is still 5. However, 4 is 100 and when read backward it becomes 001 which is 1, so 4 is not a palindrome.

Pseudocode: here is the pseudocode for the algorithm:

integer nResultNum = 0
integer nInputNumCopy = nInputNum

while nInputNumCopy > 0
  nResultNum = nResult << 1;
  if nInputNumCopy & 1 == 1
    nResultNum = nResultNum | 1;
  nResultNumCopy = nResultNumCopy >> 1;
end while

if nResultNumCopy == nInputNum 
  return true

return false

Here is the implementation of the pseudocode using JavaScript:

function bIsIntPalindrome(nInputNum)
{
   if (nInputNum === 'undefined' || nInputNum === null || nInputNum < 0)
      return false;

   var nInputNumCopy = nInputNum;
   var nResultNum = 0;

   while (nInputNumCopy > 0)
   {
      nResultNum <<= 1;

      if (nInputNumCopy & 1)
      {
         nResultNum |=1;
      }

      nInputNumCopy >>= 1;
   }

   if (nInputNum == nResultNum)
      return true;

   return false;
}

Explanation: the general plan is to generate a number whose bit representation is the reverse of that of the input number. After that, we check to see if the two numbers equal. If they do, the input number is palindrome as explained above:

Check for invalid inputs.
nResultNum is the number whose bit representation is the reverse of the input number. nInputNumCopy is the copy of the input number. Since we'll destroy the value in the process, we must make copy of it so that we can compare the result to the original input later on.
The while loop runs until nInputNumCopy is 0, meaning that we have copied all of its bits. In other words, this loop copies the bits from nInputNumCopy to nResultNum from right to left. At each iteration:
- First, shift nResultNum's bits to the left by 1
- Second, check if the current right most bit in nInputNumCopy is 1 by using & operator. If the right most bit is 1, turn the right most bit of nResultNum to 1 using | operator.
- Third, shift all bits of nInputNumCopy to the right by 1.
When finishing copying the bits from right to left, we check for equality between nInputNum (the original input value) and nResultNum (containing the same number of bits but in reverse order). If the two equal, then input number is palindrome, otherwise not.

Example: let's check to see if 5 is a palindrome. At the start of while loop, variables' values are nResultNum = 0 and nInputNumCopy = 5 (101). Entering the while loop:

First iteration, nResultNum <<= 1 still equals 0 because 000 << 1 = 0. nInputNumCopy & 1 = 1 because 101 & 001 = 001, so nResultNum |= 1 = 000 | 1 = 001. Then, nInputNumCopy >>= 1 = 2 because 101 >> 1 = 010 which is 2. Because nInputNumCopy > 0, loop continues.
Second iteration, nResultNum <<= 1 makes nResultNum = 010 because 001 << 1 = 010. Since nInputNumCopy & 1 = 0 (010 & 001 = 000), nothing added to nResultNum in this iteration. nInputNumCopy >>= 1 = 001 = 1. Since nInputNumCopy is still greater than 0, the loop continues.
Third iteration, (nResultNum <<= 1) = (010 << 1) = 100. (nInputNumCopy & 1) = 001 & 001 = 001, so a 1 bit is added to nResultNum such that (nResultNum |= 1) = (100 | 1) = 101. Shift nInputNumCopy to right by 1, making nInputNumCopy = 000. Since nInputNumCopy is now 0, the loop ends.

After the while loop, nResultNum = 101 which is 5. Thus, nResultNum equals nInputNum. The method returns true. 5 is a palindrome. We're done.

I hope the explanation was clear. If you have any question, please feel free to ask by emailing or posting in the comment section. Until next time!

Search for Intersection Between Two Sorted Arrays of Integers

2011-06-25T11:00:00.000-07:00

Question: there are two sorted arrays of integers such as array(1, 3, 6, 9, 10) and array(-2, 0, 4, 6, 12). Search for the intersection between these arrays. The intersection is 6 at index 2 and index 3 in the example arrays.

Solution: a naive solution would be to compare each element in the first array to each element in the second array, resulting in an O(N * M) algorithm where N and M are the numbers of elements in first and second array respectively. A better solution is using binary search for each element in the first array in the second array. That is an O(N LogM) algorithm. However, we can even do better using two array iterators at a time. Take a look at the pseudocode below:

it1, it2
while it1 < size1 and it2 < size2
  if (array1[it1] == array2[it2])
    print(it1 and it2)
    return
  else if (array1[it1] > array2[it2])
    it2++
  else
    it1++

We simply move the iterators, one for each array, whenever an element of one array is less that the element of the other array. We do this until we either find the common element (intersection) or we reach the end of any array. This works because both arrays are sorted in the ascending order. Thus, we don't have to compare each and every element to all other elements to know where the intersection is. Here is the implementation of the pseudocode in JavaScript :)

function vIntersectionInSortedArrays(cIntArray1, cIntArray2)
{
   if (cIntArray1 === null || cIntArray1 === undefined 
      || cIntArray2 === null || cIntArray2 === undefined)
   {
      document.write("Empty arrays!"); 
      return;
   }

   var nArray1It = 0;
   var nArray2It = 0;
   
   while (nArray1It < cIntArray1.length 
         && nArray2It < cIntArray2.length)
   {
      if (cIntArray1[nArray1It] == cIntArray2[nArray2It])
      {
         document.write("Intersect at index" + nArray1It 
                        + " and " + nArray2It);
         return;
      }
      else if (cIntArray1[nArray1It] > cIntArray2[nArray2It])
         nArray2It++;
      else
         nArray1It++;
   }

   document.write("No intersection!");
}

I know it's unusual to use JavaScript but a break from C++ and Java is nice. As we expect, this algorithm is more efficient. In the worst case, it takes only O(M + N) time to return the answer!

As always, thanks for following and if you have any suggestion, please don't hesitate to let me know in the comment section.

Convert integers to roman numbers

2011-06-23T10:13:00.000-07:00

Question: write an algorithm to convert an integer into roman number. For example, 1 -> I, 2 -> II, or 4 -> IV.

Solution: in order to solve this problem, we must know the rules of writing roman numerals. For example, I is 1 and V is 5 but IV is not 6 but 4 (5 -1). Moreover, there is no 0 number in roman numeral system. Here is the link to an article about roman numerals if you are unfamiliar with the system.

As you may notice, the roman numeral system consists of several fundamental and unique numbers. They are used in conjunction with rules to create other numbers. Therefore, we just have to cache the unique numbers and apply the rules in order to generate any roman number we want. Let's take a look at the implementation below in C++

#include<iostream>
#include<map>
#include<string>
using namespace std;

string int2RomanNum(int intVal)
{
   if (intVal <= 0)
   {
      cout << "Roman numbers don't support 0 or negative! Return NULL" << endl;
      return ""; 
   }

   //build hash table of unique values 
   map valueMap;

   valueMap[1] = "I";
   valueMap[4] = "IV";
   valueMap[5] = "V";
   valueMap[9] = "IX";
   valueMap[10] = "X";
   valueMap[40] = "XL";
   valueMap[50] = "L";
   valueMap[90] = "XC";
   valueMap[100] = "C";
   valueMap[400] = "CD";
   valueMap[500] = "D";
   valueMap[900] = "CM";
   valueMap[1000] = "M";

   //the roman value
   string romanResult = "";

   //traverse the list in reverse order 
   map::reverse_iterator it;
   
   for (it = valueMap.rbegin(); it != valueMap.rend(); it++)
   {
      //if current number is greater than current key in list
      //add the value corresponded with key to result
      //then subtract the equivalent int value from current number
      while (intVal >= it->first)
      {
         romanResult = romanResult + it->second;
         intVal = intVal - it->first;
      }
   }

   return romanResult;
}

Explanation: our method accepts an integer as parameter and return a string that contains the roman number equivalent to that integer.

First we check the parameter to see if it is equal or less than 0. Because there is no 0 or negative roman numbers, we return an empty string after printing out the warning.
Next, we build a hash table of unique roman numbers which are then combined to create other numbers.
The heart of this method consists of two loops. The "for" loop runs through the hash table from bottom to top (largest number to smallest number). At each number in the hash table, we run the "while" loop to construct the roman number. This while loop will run until the integer is less than the current number in the hash table. And for every iteration in the while loop we add the current roman number to the returned string. For example, if our integer is 35, at the 10 or X position in the hash table, the while loop will kick in and add XXX into our string. And then the for loop continues at the 5 or V position, letting the while loop add V into our string.

Example: let's say we want to convert the integer 430 into its equivalent roman number. Here is how the method runs:

First "for" loop's iteration, intVal = 430 and it->first = 1000. No while loop because intVal is less than it->first.
Second iteration, intVal = 430 and it->first = 900. No while loop.
Third iteration, intVal = 430 and it->first = 500. No while loop.
Fourth iteration, intVal = 430 and it->first = 400. Enter while loop: romanResult = CD and intVal = 30. Because intVal is less than it->first after the first "while" iteration, the while loop exits.
Fifth iteration, intVal = 30 and it->first = 100. No while loop.
Sixth iteration, intVal = 30 and it->first = 90. No while loop.
Seventh iteration, intVal = 30 and it->first = 50. No while loop.
Ninth iteration, intVal = 30 and it->first = 40. No while loop.
Tenth iteration, intVal = 30 and it->first = 10. Enter while loop: 1) intVal = 20 and romanResult = CDX, 2) intVal = 10 and romanResult = CDXX, and 3) intVal = 0 and romanResult = CDXXX. The while loop exits after that because intVal is less than it->first.
Nothing happens in the last four iterations because intVal is 0. Thus, the final result is romanResult = CDXXX

Thank you for reading and until next time :)

Least-Square Linear Regression of Data Using C++

2011-06-02T22:45:00.000-07:00

Question: implement the least-square method to determine the linear function that best fits the data. This method also needs to find the coefficient of determination (R^2) and standard error of estimation (E). Input to this method is a collection of data points (x, y) and the collection's size, a.k.a. number of data points.

Solution: the answer is straight forward. We basically just have to apply the statistics formulas for finding the least-square linear function to the data. If you are not familiar with the formulas and where they come from here is the link for you. Now, let's take a look at the implementation below:

#include<iostream>
#include<cmath>
using namespace std;

struct Point
{
   double x;
   double y;
};

void leastSqrRegression(struct Point* xyCollection, int dataSize)
{
   if (xyCollection == NULL || dataSize == 0)
   {
      printf("Empty data set!\n");
      return;
   }

   double SUMx = 0;     //sum of x values
   double SUMy = 0;     //sum of y values
   double SUMxy = 0;    //sum of x * y
   double SUMxx = 0;    //sum of x^2
   double SUMres = 0;   //sum of squared residue
   double res = 0;      //residue squared
   double slope = 0;    //slope of regression line
   double y_intercept = 0; //y intercept of regression line
   double SUM_Yres = 0; //sum of squared of the discrepancies
   double AVGy = 0;     //mean of y
   double AVGx = 0;     //mean of x
   double Yres = 0;     //squared of the discrepancies
   double Rsqr = 0;     //coefficient of determination

   //calculate various sums 
   for (int i = 0; i < dataSize; i++)
   {
      //sum of x
      SUMx = SUMx + (xyCollection + i)->x;
      //sum of y
      SUMy = SUMy + (xyCollection + i)->y;
      //sum of squared x*y
      SUMxy = SUMxy + (xyCollection + i)->x * (xyCollection + i)->y;
      //sum of squared x
      SUMxx = SUMxx + (xyCollection + i)->x * (xyCollection + i)->x;
   }

   //calculate the means of x and y
   AVGy = SUMy / dataSize;
   AVGx = SUMx / dataSize;

   //slope or a1
   slope = (dataSize * SUMxy - SUMx * SUMy) / (dataSize * SUMxx - SUMx*SUMx);

   //y itercept or a0
   y_intercept = AVGy - slope * AVGx;
   
   printf("x mean(AVGx) = %0.5E\n", AVGx);
   printf("y mean(AVGy) = %0.5E\n", AVGy);

   printf ("\n");
   printf ("The linear equation that best fits the given data:\n");
   printf ("       y = %2.8lfx + %2.8f\n", slope, y_intercept);
   printf ("------------------------------------------------------------\n");
   printf ("   Original (x,y)   (y_i - y_avg)^2     (y_i - a_o - a_1*x_i)^2\n");
   printf ("------------------------------------------------------------\n");

   //calculate squared residues, their sum etc.
   for (int i = 0; i < dataSize; i++) 
   {
      //current (y_i - a0 - a1 * x_i)^2
      Yres = pow(((xyCollection + i)->y - y_intercept - (slope * (xyCollection + i)->x)), 2);

      //sum of (y_i - a0 - a1 * x_i)^2
      SUM_Yres += Yres;

      //current residue squared (y_i - AVGy)^2
      res = pow((xyCollection + i)->y - AVGy, 2);

      //sum of squared residues
      SUMres += res;
      
      printf ("   (%0.2f %0.2f)      %0.5E         %0.5E\n", 
       (xyCollection + i)->x, (xyCollection + i)->y, res, Yres);
   }

   //calculate r^2 coefficient of determination
   Rsqr = (SUMres - SUM_Yres) / SUMres;
   
   printf("--------------------------------------------------\n");
   printf("Sum of (y_i - y_avg)^2 = %0.5E\t\n", SUMres);
   printf("Sum of (y_i - a_o - a_1*x_i)^2 = %0.5E\t\n", SUM_Yres);
   printf("Standard deviation(St) = %0.5E\n", sqrt(SUMres / (dataSize - 1)));
   printf("Standard error of the estimate(Sr) = %0.5E\t\n", sqrt(SUM_Yres / (dataSize-2)));
   printf("Coefficent of determination(r^2) = %0.5E\t\n", (SUMres - SUM_Yres)/SUMres);
   printf("Correlation coefficient(r) = %0.5E\t\n", sqrt(Rsqr));

}

Explanation: assuming that each data point is structured similar to our Point struct, then our method takes an array of Points and the array's size as its parameters.

To advance any further, we must first find these sums:

SUMx: the sum of all x values of the points
SUMy: the sum of all y values of the points
SUMxx: the sum of the square of x values, meaning that we square x values individually and add them togethers
SUMxy: for each point we multiply its x value with its y value, then add all the results together to find this sum.

The first for loop is used to calculate those sums simultaneously.

After that, we calculate the means of x and y values which equal sum of x values divided by the number of points and sum of y values divided by the number of points respectively.

slope and y_intercept of the best-fit function can then be determined using the means and the sums we found. Thus, the linear function is y = slope*x + y_intercept.

Finally, to calculate the coefficient of determination and standard error of estimation, we need to find the sum of squared standard deviation (SUM_Yres) of each point from the best-fit linear function and sum of the squared residues (SUMres). That's what the second for loop does.

Once, we know sum of squared residues and sum of squared standard deviation, we just apply formulas to find the coefficient and the standard error.

As you can see, the challenge is not writing the code to compute the least-square regression but being able to understand the logic behind that. Why slope, y_intercept, coefficient of determination and standard error of estimation are calculated that way? Where do the formulas come from? Etc..

Answering those questions is beyond the scope of this post, so I leave it to you. I actually took statistics in order to understand the concepts and translate the formulas into code :)

As always, any comment or suggestion is welcome! Bye for now.

Find Local Maximum of a Function Using Bisection Method

2011-05-08T19:08:00.000-07:00

Question: implement the bisection method to find a function's local maximum.

Solution: bisection is one of the root-finding methods that are used to find real roots of a continuous function. More information about the method and mathematical analysis can be found here. For this question, we'll modify the bisection method to find the local maximum of a function instead of its roots.

The maximum of a function is a point where the value of the function is max. Thus, the local maximum is the maximum of a specified interval of the function. It is local because outside of the specified interval, we can't prove that it is the maximum of the function. Here is the code in C:

double bisect(double x_lower, double x_upper, double epsilon, double (*dx)(double), int maxIteration)
{
   double result = 0.0; //the root
   double f_result = 0.0; //value of f(x)
   int iteration = 0;

   while (fabs(x_upper - x_lower) > epsilon && iteration < maxIteration)
   {
      iteration++;

      //compute the new root
      result = (x_upper + x_lower) / 2;

      //derivative of the new root
      f_result = dx(result);
      
      //see if derivative has changed sign
      if (dx(x_lower) * f_result < 0)
         x_upper = result;
      else if (dx(x_upper) * f_result < 0)
         x_lower = result;
      else
      {
         return result;
      }
   }
   printf("No root found, returning -1 ! \n");
   return -1;
}

Explanation: our function accepts five arguments and return the maximum if it finds one.

The first two arguments, x_lower and x_upper, are the lower and upper bound of the interval whose maximum is our interest.
The third argument, epsilon is the accuracy or the acceptable range of error that the answer must meet. Why do we have this? Because in real life, it is extremely difficult to find the exact solution. Some reasons include the limit on computer's ability to store floating point numbers and round off error. Moreover, most real world applications only need the answer to be precise enough instead of being exact. That's why we accept the concept of tolerable error. To keep the error to minimum, I suggest passing in machine epsilon as the acceptable error. Machine epsilon is the smallest difference between two numbers that the computer, on which the program is run, can produce. Thus, if the error is less than machine epsilon, then the answer is the most precise that particular computer can produce.
The fourth argument, *dx, is the pointer to the function's first derivative.
the last argument, maxIteration, is the max number of times that we want our program to run. If the bisection method doesn't converge (it does in some cases), then our program will run forever. The maxIteration is there to prevent that case. After a certain number of calculations and the method has not returned the result, we better find another way to solve the problem right? :)

The basis to find the local maximum is that the derivative of lower and upper bounds have opposite signs (positive vs. negative). Furthermore, after passing through the maximum the derivative changes sign. Therefore, we can run the function until the derivative changes sign. It means that when neither dx(x_upper) * dx(x) < 0 nor dx(x_lower) * dx(x) < 0, then x is the value in interval (x_lower, x_upper) where f(x) is max.

Mathematically, the local maximum is the point where the derivative is 0 (dx = 0). Think about slope of a graph. However, since we are dealing with computer and floating point numbers, it's not a good idea to use equality comparison as the way to find maximum. That's why we exploit the fact that the derivative changes sign after passing through the maximum.

Thanks for reading and until next time.

Determine the Height of Binary Trees

2011-05-03T20:29:00.000-07:00

Question: given a root of a binary tree, write an algorithm to find the tree's height.

Solution: the height of a binary tree is the length of the path from the root to the deepest leaf node of the tree. For example, the following tree has height of 3:

To find the height, we need to count the number of nodes on the path from root to the deepest leaf. This can be done recursively. Here is the code in C++:

//basic tree node definition
struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};

int getBinaryTreeHeight(struct Node* root)
{
   if (root == NULL)
      return 0;

   int leftHeight = getBinaryTreeHeight(root->left);
   int rightHeight = getBinaryTreeHeight(root->right);

   return 1 + (leftHeight <= rightHeight ? rightHeight : leftHeight);
}

Explanation: assuming that we have a tree node structure just like that in the example code, our method takes in a pointer to the root and return the height of that root's tree. Recursively, a tree's height is the height of its subtrees. So if we know the height of the subtrees, we know the height of the tree. For each node under the current root, we do the following:

If the current node is null, we simply return 0 because a rooted tree with no root has height 0.
Next we find the height of the left subtree and the right subtree.
Lastly, either left or right subtree's height plus one is returned as the height of the current root's tree. Why do we add one into the return result? Well because the current node is counted as one height unit if it is not null.

By the end of the recursive calls, the returned sum is the height of the tree whose root is the argument to the function.

That's the end of this post. Thanks for reading :)

How to Shuffle an Array or the Fisher-Yates Algorithm

2011-04-28T23:10:00.000-07:00

Question: how can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5).

Solution: this problem can be solved using Knuth Shuffling Algorithm a.k.a Fisher-Yates Shuffling Algorithm. The core strategy behind the algorithm is to pick a random index between 0 and N, where N is the greatest index of the unshuffled array, and then move that element to the shuffled part of the array. In other words, the algorithm partitions the original array into two parts, the unshuffled and shuffled part. It randomly picks an element from the unshuffled part and puts it into the shuffled part. It does that until no elements left in the unshuffled part. Here is the implementation in C:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void knuthShuffle(int orgArray[], int arraySize)
{
   if (arraySize == 0 || arraySize == 1)
      return;

   srand(time(NULL));

   int i;
   int index, temp;
   for (i = arraySize - 1; i > 0; i--)
   {
      index = rand() % (i+1);
      temp = orgArray[index];
      orgArray[index] = orgArray[i];
      orgArray[i] = temp;
   }
}

Explanation: in order to partition the array, we traverse the array from the end to start. The subarray from iterator index i to the last index of the array (arraySize - 1) is the shuffled part. And, the subarray from the first index (0) to the iterator index i is the unshuffled part. As, the index i moves up the array, we randomly generate a number between 0 and i + 1 using C-function rand(). We then swap the element at the index that equals the random number with the element at the last index (i) of the unshuffled part. As the result of decreasing i by 1 for every loop iteration, the partitions are automatically reserved. Here is an example with illustration that will hopefully make everything clearer.

Example: we'll shuffle this array(1, 2, 3, 4, 5). Notice that the value for index is randomly picked, so at run time the algorithm may not generate the values in the exact order that they are here. We just need to understand that, the random values are always greater than or equal 0 and less than i. Here is what the array starts out with:

First iteration, i = arraySize - 1 = 4. Let's say that index is randomly generated as 3, so we switch array[3] with array[4]. Here is the picture:

Second iteration, decrement i by 1, so i = 3 and index randomly generated as 0. We swap array[0] and array[3]:

Third iteration, i = 2 and index = 1. Swap array[2] with array[1].

Fourth iteration, i = 1 and index = 0. Swap array[0] and array[1].

Fifth iteration: i = 0, so loop terminates. Nothing happens. Here is the final shuffled array:

If there is any bug or better solution, please let me know in the comment section below. Thanks for reading :)

Sorting Array of Three Kinds or The Dutch National Flag Problem

2011-04-22T14:21:00.000-07:00

Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), write an algorithm to sort the array. For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c).

Solution: the Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. Hence, we can adopt the algorithm to sort any array of three different kinds of objects / values. Let's take a look at the implementation below where we sort an array of three different integers:

void dutchFlagSort(int inArray[], int arraySize, int high, int low)
{
  if (arraySize == 0)
    return;

  int lower = 0;
  while (inArray[lower] == low && lower < arraySize)
    lower++;

  int upper = arraySize - 1;
  while (inArray[upper] == high && upper >= 0)
    upper--;

  int temp = 0;
  int pivot;
  for (pivot = lower; pivot <= upper;)
  {
    if (inArray[pivot] == low)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[lower];
      inArray[lower] = temp;
      pivot++;
      lower++;
    }
    else if (inArray[pivot] == high)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[upper];
      inArray[upper] = temp;
      upper--;
    }
    else
      pivot++;
  }
}

Explanation: the method above takes in an array of integers, the array's size, and the order of the integers (low and high) as arguments. Notice that low indicates the lowest value in the array and high indicates the highest value in the array. For example, if our array is (1, 2, 3, 1, 2, 3) then the low maybe 1 and high maybe 3. The algorithm uses those indicators to sort the array. We can actually specify low and high as any value in the array if we want to. It only affects how the array places the integers.

The basic strategy behind the method is to partition the array into three regions, low, middle and high. These regions correspond to the three kinds of integers. Low integers whose values equal low, high integers whose values equal high, and the middle integers whose values are anything other than high and low.

That's why we have three different iterators. Any integer before lower is low integer, and any integer after upper is high integer. The pivot iterator traveses the array and swaps high and low integers to their correct places. However, it skips over the middle integers because they are supposed to be in the region between low and high integer regions. Let's do an example to clear things up.

Example: lets Dutch Flag sort this array (0, 2, 1, 0, 1, 2)

low = 0, high = 2
After the first while loop, lower = 1. After the second while loop, upper = 4. Finally, pivot = 1.

Entering the for loop:

First iteration: array[pivot] = 2 (high), so we swap array[pivot] with array[upper] and decrease upper by 1.

Second iteration: pivot = 1, lower = 1, and upper = 3. Because array[pivot] = 1, we do nothing but increasing pivot by 1.

Third iteration: pivot = 2, lower = 1, and upper = 3. Again, array[pivot] = 1, we just increase pivot by 1 and move on.

Fourth iteration: pivot = 3, lower = 1, and upper = 3. Since array[pivot] = 0 (low), we swap array[pivot] and array[lower]. Then, we increase both pivot and lower by 1.

Fifth iteration: pivot = 4, lower = 2, and upper = 3. The loop terminates here because pivot is now greater than upper. Here is the final array. Notice how all the 0s, 1s and 2s are separated and sorted in ascending order.

Well, I hope everything is clear now after the example. If you have any question, please feel free to post it in the comment section below.

Calculate the Least Common Multiple of Two Integers

2011-04-15T16:55:00.000-07:00

Question: write an algorithm to return the least common multiple (LCM) of two integers. For example, if the inputs are 3 and 4, the function returns 12.

Solution: least common multiple (LCM) is the lowest value that is a multiple of both integers. That means LCM is divisible by both integers or the modulus of LCM divided by either integers is 0 (LCM % num = 0). Thus, we just need to start with a reasonable number and keep increasing that number until it is divisible by both integers. The number is then the LCM of the integers.

But where is the reasonable number to start out? Well, instead of starting out at 1, we can start out at the highest integer between the two integers. The reason is that a number that is less than either of those two integers can't be divisible by those integers. For example, if we are to find LCM of 2 and 3, then any number that is less than 3 is surely not the LCM. Thus, we can safely start our search at 3. Notice that one integer can be the LCM of another integer. That's why we start out at the higher number. For example, the LCM of 2 and 4 is 4. Here is the algorithm in C:

  int lcm(int num1, int num2)
  {
    if (num1 % num2 == 0)
      return num1;

    if (num2 % num1 == 0)
      return num2;
      
    int n = (num1 <= num2) ? num2 : num1;
    
    for (; ; n++)
    {
      if(n % num1 == 0 && n % num2 == 0)
         return n;
    }
  }

Explanation: our function takes two integers as arguments and returns the LCM of those integers.

First, we take the modulus of the first integer (num1) and the second integer (num2). If num1 % num2 equals 0, we know num1 is the LCM because num1 is divisible by num1 and is the smallest number that is not less than num1 and num2. Similarly, if num2 % num1 equals 0 then num2 is the LCM.
When neither integer is the LCM, we find out which integer is greater and begin to find the LCM starting from that integer. That's exactly what the for loop does. For every iteration, we increase n by 1 until we find a number that divisible by both num1 and num2. This loop guarantees to find the solution. That's why we don't need any other return statement outside the loop. Nor we need a termination condition for the loop.

That's all we have for today. Thanks for reading!

Convert Binary Tree to Double Linked List

2011-04-07T16:34:00.000-07:00

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:

The output will be a double linked list like this:

Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.

For traversing the tree, we'll use level / order traversal a.k.a breadth first search. If you are not familiar with that concept, here is the post for you :) Take your time to read it, I'll be right here when you come back!

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)

#include<iostream>
#include<queue>
using namespace std;

struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};

struct Node* bt2DoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;

  queue nodeQueue;

  struct Node* head = root; //reference to head of the linked list
  struct Node* listIT = NULL; //current node being processed
  struct Node* prevNode = NULL; //previous node processed

  //initialize the stack
  nodeQueue.push(root);

  //convert to double linked list
  while (!nodeQueue.empty())
  {
    //process next node in stack
    prevNode = listIT; 
    listIT = nodeQueue.front();
    
    nodeQueue.pop();

    //add left child to stack
    if (listIT->left != NULL)
      nodeQueue.push(listIT->left);

    //add right child to stack
    if (listIT->right != NULL)
      nodeQueue.push(listIT->right);

    //add current node to linked list
    if (prevNode != NULL)
      prevNode->right = listIT;
    listIT->left = prevNode;
  }
  
  //connect end node of list to null
  listIT->right = NULL;

  return head;
}

Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:

If the root node is null, we return null because the tree is empty.
If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
The while loop will run until no node left in queue to process. For each node in the queue, we do the following:

prevNode = listIT gets reference to the last processed node because we are about to process a new node

listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.

nodeQueue.pop() removes the top node out of the queue.

We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.

Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.
When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

Whew! That was a long explanation. If you are still confused, you may want to read about breadth first traversal and do an example with pencil and paper. Also, please don't hesitate to ask questions in the comment section below!

Find the maximum subarray of an integer array

2011-03-31T14:32:00.000-07:00

Question: given an unsorted array of integers, find the subarray that yields the largest sum. For instance, if the input is {5, 2, -1}, then the output is subarray {5, 2} because it gives the largest sum (7 vs. 5 vs. 2 or 6).

Solution: this problem can be solved by using a modified version of Kadane's Algorithm. The strategy is to calculate the sum of each subarray and keep track of the sum, the start index and the end index of the subarray that gives the largest sum. Moreover, we calculate the sum of a subarray by adding the sum of the previous subarray with an additional element. For example, to calculate the sum of {5, 2, -1}, we add the sum of {5, 2}, which is 7, to the value of the next element, which is -1.

Here is our C++ method to solve the problem:

void findMaxSumSequence (int inputArray[], int size)
{
  if (size == 0)
    throw "Array Size is 0";

  int maxSum = inputArray[0];
  int maxStartIndex = 0;
  int maxEndIndex = 0;
  
  int curSum = inputArray[0];
  int curStartIndex = 0;
  

  for (int i = 1; i < size; i++)
  {
    if (curSum < 0)
    {
      curSum = 0;
      curStartIndex = i;
    }
    
    curSum = curSum + inputArray[i];

    if (curSum > maxSum)
    {

      maxSum = curSum;
      maxStartIndex = curStartIndex;
      maxEndIndex = i;
    }
  } 

  cout << "Start index: " << maxStartIndex << " End index: " 
        << maxEndIndex << " Max sum: " << maxSum << endl;
}

Explanation: this method accepts an array and its size as arguments. It prints out the start index, end index and the sum of the subarray that yields the max sum. Here are the main steps:

First, check if the array size is 0. If it is so, we throw an exception because there is nothing we need to do when the array is null.
Then, initialize variables: maxSum is the largest sum found. maxStartIndex and maxEndIndex are respectively the start index and end index of the subarray that yields the max sum. curSum is the sum of the current subarray that we're examining. curStartIndex is the start index of the current subarray we're checking.
Next, we loop through the array and start calculating the sum of subarrays one after another:

If the sum of the current subarray is less than 0, we reset curSum to 0. Why? If the last subarray's sum is negative, we will only decrease the next subarray's sum by adding the previous subarray's sum with an additional number. For example, if the previous subarray's sum is -2, and the next element is 3, it's better to reset the sum to 0 and add 3 into 0 than to add -2 to 3.

curSum = curSum + inputArr[i] calculates the sum of the current subarray by adding the sum of the previous subarray with the next value in the array.

After that, if the sum of the current subarray is greater than the max sum then we replace the max sum with the sum of the current subarray. We also change the maxStartIndex to the start index of the current subarray and the maxEndIndex to the current index i.

When the loop ends, maxSum will contain the largest sum found. maxEndIndex and maxStartIndex contain respectively the end and start index of the subarray that gives the largest sum. Thus, we just have to print out those values.

If you have any comment or another solution to this problem, please post in the comment below. I would love to learn about it. Thanks for reading and until next post!

Finding an integer that repeats odd number of times in an array of positive integers

2011-03-24T12:37:00.000-07:00

Question: in an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?

Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. Thus, if a number appears a even number of times, it yield a result of 0. For example, given the array {2, 3, 2, 3}, we have 2 and 3 repeat two times (even). Thus, if we XOR all of them together we should get 0 as the result. However, if there is an odd repeated number, the result will be the value of that number! Here is the algorithm in C++:

  public int getIntOddlyOccured(int[] inputArr)
  {
    int oddNum = inputArr[0];
   
    for(int i = 1; i < inputArr.length; i++)
      oddNum = oddNum ^ inputArr[i];
   
    return oddNum;
  }

Explanation: our method takes an integer array as argument. It assumes that there is one and only one odd occurring number (conditions given by the question), so it will return that number and does no validation to see whether the input in fact has only one odd repeated number. In the body, the method loops through the array and XOR all the elements together. The result will be the oddly repeated number.

Example: let's do an example with this array {1, 4, 3, 4, 1}. The method first initializes the result oddNum to 1 and then does the for loop:

First iteration: oddNum = 1(0001) ^ 4(0100) = 5(0101) and i = 1
Second iteration: oddNum = 5(0101) ^ 3(0011) = 6(0110) and i = 2
Third iteration: oddNum = 6(0110) ^ 4(0100) = 2(0010) and i = 3
Fourth iteration: oddNum = 2(0010) ^ 1(0001) = 3(0011) and i = 4
Loop ends because i = 5, so we return oddNum = 3 which is the oddly repeated number in the array

This algorithm takes O(n) time complexity because it loops through the array only once. The space complexity is O(1) because we only need an additional integer for storage. Very efficient! That's all we have for now. Thanks for reading :)

Check if two singly-linked lists intersect

2011-03-23T17:49:00.000-07:00

Question: given two singly linked lists, determine if they intersect one another without modifying them.

Understand the question: first of all, we need to understand what intersecting linked lists are. Let's say we have two linked lists 1->2->3->4->5 and 10->20->30->5, they intersect each other because each list passes through the node 5. It's hard to visualize it in our head, so here is the picture:

Solution: to know whether two lists intersect, we just have to check if they share any common node. This is easy to be done with two pointers. One starts at the head of one list while the other starts at the head of the other list. Those pointers will run till the end of their lists or till they meet (pointing to the same node). If they meet, the two linked lists intersect. But if one pointer reaches the end of its list and hasn't met the other pointer yet, then the two linked lists do not intersect.

However, there is a small problem with our approach. When the lists have different lengths such as the ones in our example, the two pointers may never meet even if the lists intersect. Thus, we need to take into account that situation.

One way to solve that problem is to find out the lengths of the list. If they have different lengths, we'll calculate the difference in number of nodes between the shorter list and the longer list. Then, we'll move the pointer of the longer list ahead by that many nodes before starting to check for intersection. Our pointers are guaranteed to meet if there is intersection. Here is the implementation in Java:

private static boolean areListsIntersected(Node list1, Node list2)
{
    if (list1 == null || list2 == null)
      return false;

    if (list1 == list2)
      return true;

    int list1Len = 0;
    Node it1 = list1;
    while (it1 != null)
    {
      list1Len++;
      it1 = it1.next;
    }

    int list2Len = 0;
    Node it2 = list2;
    while (it2 != null)
    {
      list2Len++;
      it2 = it2.next;
    }

    int lenDiff = 0;
    it2 = list2;
    it1 = list1;

    if (list2Len > list1Len)
    {
      lenDiff = list2Len - list1Len;
      
      while (lenDiff > 0)
      {
        it2 = it2.next;
        lenDiff--;
      }
    }
    else if (list1Len > list2Len)
    {
      lenDiff = list1Len - list2Len;
      while (lenDiff > 0)
      {
        it1 = it1.next;
        lenDiff--;
      }
    }

    while (it2 != null && it1 != null)
    {
      if (it2 == it1)
        return true;
      it1 = it1.next;
      it2 = it2.next;
    }

    return false;
}

Explanation: our method takes two lists as arguments. It returns true if those lists intersect and false if they don't. The first two if statements are used to check for null lists and special case where the head of one list is the end node of the other list. When there are no null or special lists, we do the following:

First while loop counts the number of nodes in the first list.
Second while loop counts the number of nodes in the second list.
After having the length of each list, we find the difference in number of nodes and then move whichever pointer that points to the longer list ahead using that difference.
Finally, the while loop is used to find the intersection. We just loop until either of the pointers reaches the end of its list. During the loop, if the pointers meet, we return true immediately because it means that the lists intersect. But at the end of the loop and nothing has happened, we simply return false because the lists don't intersect.

You may notice that the pointers will meet at the first node that both lists share! Thus, this algorithm can be tweaked a little bit to return the intersection node of two intersecting lists. Or, this algorithm can be used to break two intersecting lists at their intersection node. Pretty neat huh?

Anyway, time complexity is O(m + n) where m and n are the number of nodes in the first and second list respectively. The space complexity is O(1).

Thanks for reading and until next time.

Convert integer to binary or bit string

2011-03-22T16:21:00.000-07:00

Question: write a function to convert an integer into a bit string. For example, if input is 2, the output is "00000000000000000000000000000010" if the system is 32-bit, "0000000000000010" if the system is 16-bit and so on.

Solution: the strategy here is to use bitwise manipulation and convert one bit at a time to character. We look at the right most bit and if it is a 0 bit, we add '0' character into our bit string. Otherwise, we add '1' character into our bit string. Here is the code in C++:

char* int2bin(int num)
{
  const int BITS_PER_BYTE = 8;

  int bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char); 

  char* p = (char*)malloc(bitStrLen);

  for (int i = (bitStrLen - 1); i >= 0; i--)
  {
    int k = 1 & num;
    *(p + i) = ((k == 1) ? '1' : '0');
    num >>= 1;
  }
  
  return p;
}

Explanation: our function takes an int as the argument and returns a char pointer which points to the bit string. Also, remember that there are 8 bits per byte, that's why we have that constant declared in the first line.

Allocating memory from the heap to store our bit string: each bit is represented by a char ('0' or '1'). Thus, to get the total number of bytes required, we need the total of bits our integer has, and the number of bytes each char needs.

To get the total number of bits each integer has, we use sizeof(int) * BITS_PER_BYTE. sizeof(int) gives the number of bytes each integer has, and BITS_PER_BYTE is the number of bits each byte has. Thus, multiplying them together, we have the total number of bits each integer has.

To get the number of bytes each char needs, we just call sizeof(char)

By multiplying the number of bits the integer has with the number of bytes each char needs, we get the total number of bytes required to store the binary string representation of the integer. Hence, bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char).
Next, we explicitly allocate enough memory from the heap to store our bit string by calling the malloc function.
Finally, we convert the integer into bit string using the for loop. Notice that the number of bytes we need is also the number of characters the bit string has. That's why our loop needs to run from 0 to 32 only.

For each iteration, we check the right most bit of the integer by using bitwise manipulation: 1 & num. If the outcome is 1, then the right most bit must be 1. Otherwise, the right most bit must be 0. This works because any number with 1 at the right most bit will give the result of 1 when it AND with the number 1. But if the right most bit is 0, then the result is 0. For example, 1101 & 1 = 1 because 1101 has 1 as the right most bit.

After converting the current right most bit, we need to shift the integer to the right one position to convert the next bit. Hence, num >>= 1

That's all we have for this post. If there is any suggestion or better solution, please leave it in the comment section below :) Thanks for reading!

Introduction to Thread in Java (part 2): Thread Life Cycle

2011-03-19T16:02:00.000-07:00

Welcome to the second installment of the series "Introduction to Thread in Java." If you haven't read part 1, here is the link for you. Please read it because we covered a lot of important and fundamental concepts in the first part.

In this section, we'll learn more about the life cycle of threads. Specifically, we need to learn what states threads go through and why / how they end up in a particular state.

In the simplest form, a thread's life cycle consists of five states:

New state: this is when the threadable / Thread object is first created by calling the constructor of the Thread class. For example, our thread is in new state after this statement Thread newThread = new (runnableObj, threadName);
Runnable / Read-to-run state: after calling the start() method on the thread, it enters the runnable state. That means it is ready to run or to go to some other states. As of the current version of Java, a thread must enter the runnable state before going to any other state.
Running state: a thread is in this state while its run() method is executing. During this state, the thread can go to blocked state if it gets blocked or has to wait for other threads. When the run() method finishes, this state ends.
Blocked/waiting state: while running a thread can be put to sleep, interrupted or blocked by other threads. There are many reasons why this may happen. We'll go deeper in the next section.
Terminated / dead state: when a thread reaches this state, its life ends. It can never be revived again. Normally, a thread enters this state because its run() method has ended. However, a thread can also be terminated even before it is in the runnable state or during the waiting state by calling stop() or suspense() on the thread. I don't suggest using any of those methods to move a thread to its terminated state because those methods have been deprecated by Java and are not thread safe. Therefore, ending the run() method is the best way to go. We'll discuss more on how to do that later.

Here is the UML state diagram that describes the states that a Java thread goes through and how it gets to those states.

Next, let's examine the Blocked/Waiting state and the Terminated/Dead state. They are more complicated than other three states.

As we have seen, a thread can only enter this state while it is running. So why does a thread enter this state? There are many causes. The main three are:

Yielding for another thread: current thread yields for another thread to run first. Sometimes, we have a particular thread that needs to run immediately, so we call the yield() method on any running thread to reclaim CPU and resources for the important thread. As the result, any running thread enters the blocked state until the important thread finishes and releases the CPU / resources.
Waiting for another thread: somewhat similar to yielding, there are times when a thread needs to wait for another thread to finish first before it can continue. For instance, if two threads share the same resource, and one of the two is holding that resource, then the other thread needs to wait for that resource to be released.
Waiting for I/O: as you may know, the I/O speed is extremely slow compared to the CPU speed. Thus, if a thread needs some resources / inputs from I/O, it may need to enter the waiting state in order to let the CPU work on other threads. This practice is better for utilizing the CPU because it should be working on other threads / processes instead of siting idle and waiting for a particular thread.

The Java Thread API provides all functions needed to resolve all the situations above. For example, the join() method allows one thread to wait for the completion of another thread. Moreover, you can always cause a thread to enter the waiting state at anytime by calling the method interrupt() on that thread (there are some cases where threads are not interruptable however). Here is the link to the Java Thread API for further reading.

Once a thread enters this state, it cannot come back to other states. There two distinct ways to terminate the thread, letting the run() method return and calling stop(), suspense() or destroy() method on the running thread. The former is recommended because it ensures thread safe. In fact, Java has already deprecated stop(), suspense() and destroy() method in the new API.

Here is an excellent article that points out why those methods are bad and why stopping a thread through run() is a good practice.

That's all for the second part of this series. Please leave any comment or suggestion because they are always helpful and appreciated :)

Removing a loop in a singly linked list

2011-03-16T15:22:00.000-07:00

Challenge: remove a loop from a singly linked list if the list has a loop. For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4.

Solution: the first task is to determine if our linked list has a loop. If it does, we then need to figure our where the end of the loop is. The reason is that we will set the pointer of the loop's end node to NULL to break the loop. For instance, given the list 1->2->3->1, we must find out whether it has loop. Obviously, that list does have a loop and the loop's end node is 3 (3 points back to head of the loop which is 1). Thus, we need to make node 3 point to NULL so the list doesn't have a loop anymore. The result should be 1->2->3->NULL. Here is the C++ implementation of the algorithm:

#include<iostream>
using namespace std;

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

void removeLoop(Node* head)
{
  if (head == NULL)
    return;

  Node* slow = head;
  Node* fast = head;
  Node* last = NULL;
  
  bool hasLoop = false;

  while (fast->next != NULL && fast->next->next != NULL) 
  {
    last = slow;
    slow = slow->next;
    fast = fast->next->next;
    
    if (slow == fast)
    {
      hasLoop = true;
      break;
    }
  }

  
  if (hasLoop)
  {
    slow = head;

    while (slow->next != fast->next)
    {
      slow = slow->next;
      fast = fast->next;
    }
    
    if (slow == head && fast == head )
      last->next = NULL;
    else
      fast->next = NULL;
  }
}

Explanation: our method takes only the reference to the list's head node as an argument. The first while loop determines if the list has loop. And, the second while loop points the loop's end node to null, terminating the loop:

If the list is empty (head points to NULL), there is nothing to do so return.
Next, we need three different pointers. slow will go through the list one node after another. fast moves through the list two nodes at a time, so it goes twice as fast as the slow pointer. And, last refers to the previous node visited by the slow pointer.
We just have to loop through the list until fast reaches NULL because if the linked list doesn't have loop, fast will reach NULL eventually. Moreover, if the list does have a loop, we'll break out of the while loop immediately.
As the while loop runs, we check if slow and fast pointer point to the same node. When they do, it means the list has a loop. This is a very common technique to find out if a linked list has loop. Here is a post about that technique if you are not familiar with it.
As soon as we know that the list has loop, we set the flag hasLoop to true. And then, we break out of the while loop immediately because fast will never reach NULL and the while loop will never end.
If the list has loop as indicated by the flag hasLoop, we enter the second while loop to remove that the list's loop.

a) First, we set the slow pointer back to the list's head node.

b) Then, we move both the slow and fast pointer one node at a time. They will eventually meet each other because the list still has a loop.

c) We stop the loop right before the pointers meet. That's how we get the reference to the end node of the loop:

d) If the slow and fast pointer both point to the head of the list, then the list is circular, meaning that the end node points back to the head node of the list (ie. 1->2->3->4->1). Thus, we'll get the reference to the end node by using the last pointer. Remember that last is pointing to either the head of the list or the end node of the loop after the first while loop. That's why if slow and fast point at the head, then slow must be pointing at the end node.

e) On the other hand,if the end node is pointing to any node in the list other than the head node (ie. 1->2->3->4->2), then slow and fast is pointing to the end node and last is pointing to the head node. Thus, we use fast pointer instead of last pointer to break the loop.

This algorithm takes O(n) time complexity and O(1) space complexity. It's very efficient!!

Find all subsets of a given set

2011-03-14T17:52:00.000-07:00

If we're given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the subsets are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.

To solve this problem there are two techniques that we need to understand:

Determine the number of subsets using bit strings: we know that the number of subsets equals to 2 to the power of the number of elements in the superset: #subsets = 2 ^ #elements. For instance, if our superset is S = {1, 2, 3}, then it has 2^3 = 8 subsets. If our superset has four elements then it has 2^4 = 16 subsets. Moreover, by shifting the bit representation of the number 1 by n, we also get 2^n. Thus, if we shift the bit string of 1 by the number of elements in the superset, we'll get the number of subsets for that superset. For example, if we have S = {1, 2, 3}, then there are 1 << 3 = 2^3 subsets in S.
Keeping track of data using bit manipulation: for this problem, we will use a bit string to keep track of subsets and their elements. Take S = {1, 2, 3} as an example. If the bit string is 100 then the subset we're working on has only one element which is 1. If the bit string is 110 then the subset we're working on has two elements which are 1 and 2. We will use & and << bit operators to figure out which bit is 1 in the bit string.

If you are not familiar with bit manipulation please read "Bit manipulation tips & tricks" part 1 and part 2. Here is the code for the algorithm written in Java:

private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
 {
    int pos = array.length - 1;
   int bitmask = i;

   System.out.print("{");
   while(bitmask > 0)
   {
    if((bitmask & 1) == 1)
     System.out.print(array[pos]+",");
    bitmask >>= 1;
    pos--;
   }
   System.out.print("}");
 }
}

Code explanation:

First, we find out the number of subsets that the superset has by shifting the bit representation of 1 by the number of elements in the superset.
Next, we just loop through each subset and generate its elements accordingly.
Inside the loop, we use pos and bitmask to keep track of the element. Specifically, bitmask is the bit string that represents elements in the current subset. And, we use post to retrieve the correct element from the superset.
The while loop will add the correct element to the subset. Note that bitmask & 1 equals to 1 only when bitmask has a '1' bit at the last position. For example, bitmask = "001" or "011" will make bitmask & 1 equal to 1. That's when we'll add an element into the subset. Why does it work? Well, for each iteration of the while loop, we'll shift bitmask by one bit position to the right (bitmask >>= 1) and we decrement pos by 1 (pos--). Thus, whenever there is a '1' bit at the last bit position, we know exactly which element to add into the subset. If you are confused, don't worry because we'll do an example!
After finishing one subset, we go to a new line and continue processing the rest.

Example: supposed that we have S = {1, 2} as our superset, then numOfSubsets = 0001 << 2 = 0100 = 4 (subsets). The rest of the program runs like this:

i = 0, pos = 1, and bitmask = 0. First while loop iteration, bitmask & 1 = 0, bitmask >>= 1 = 0, and pos = 0. While loop exits because bitmask = 0.
i = 1, pos = 1, and bitmask = 1. First while loop iteration, bitmask & 1 = 1, so print out array[pos] = 2. bitmask >>= 1 = 0 and pos = 0. While loop exits because bitmask = 0.
i = 2, pos = 1, and bitmask = 2. First while loop, bitmask & 1 = 0, so print nothing. bitmask >>= 1 = 1 and pos = 0. Second while loop, bitmask & 1 = 1, so print out array[pos] = 1. bitmask >>= 1 = 0 and pos = -1. While loop exits because bitmask = 0.
i = 3, pos = 1, and bitmask = 3. First while loop, bitmask & 1 = 1, so print out array[pos] = 2. bitmask >>= 1 = 1 and pos = 0. Second while loop, bitmask & 1 = 1, so print array[pos] = 1. bitmask >>= 1 = 0, and pos = -1. While loop exits because bitmask = 0.

The result is 4 subsets: {}, {2}, {1} and {2, 1}

This algorithm can be challenging to understand if you don't have any knowledge about bit manipulation. So, if you have a hard time making sense of it, try to read about bit manipulation first! That will help a lot! Well, thanks for reading and until next time.

Algorithm to determine if a linked list is circular or has a loop

2011-03-10T20:26:00.000-08:00

Problem: how do you find out if a linked list is circular (ie. 1->2->3->4->1) or has a loop (ie. 1->2->3->4->2)?

Understand the problem: a circular linked is like a circle where the end node points to the head node instead of null like in a regular linked list. The example, 1->2->3->4->1, has the end node 4 points to the head node 1, creating a cycle. Similarly, a linked list is said to have a loop when it contains a cycle. However, the cycle doesn't have to start at the head node. It can start at any node in the list. For instance, 1->2->3->4->2 has a loop that starts at node 2 and ends at node 4.

Solution: to solve this problem, we'll have two pointers moving at different speeds over the list. The slow pointer will move through the list one one at a time while the fast pointer will move over two nodes at a time. In other words, the fast pointer will move twice as fast as the slow pointer. When the slow and fast pointer point at the same node, we know that the linked list either is circular or has a loop. But if the linked list is just a regular list, the fast pointer will reach null before the slow pointer.

Algorithm implementation: here is the algorithm implemented in C++

#include<iostream>
using namespace std;

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

bool hasLoopInList(Node* head)
{
  if (head == NULL)
    return false;

  Node* slow = head;
  Node* fast = head;

  while (fast->next != NULL && fast->next->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;

    if (slow == fast)
      return true;
  }

  return false;
}

Code explanation:

Check whether the list is empty. If it is, return false because an empty list neither is circular nor has loop.
Create two pointers, slow and fast, that are used to traverse the list and determine if the list has loop or not. Initially, these pointers will point at the first node in the list.
Next, we just need to loop until our fast pointer reaches null or until the slow and fast pointer points at the same node. If the list is just a regular list, nothing will happen inside the while loop. And, the while loop will end eventually because the fast pointer will reach null. On the other hand, if the list has loop or is circular, the slow and fast pointers will eventually point at the same node. That's why we check for that condition for every iteration of the while loop. And as soon as we know the list has a loop, we return true.

This is a very efficient way to find out if a linked list has loop or is circular. The time complexity is O(n) where n is the number of nodes in the list. Moreover, the space complexity is O(1) because we only need two pointers no matter how long the list we need to check is.

Converting ASCII representation of positive numbers to integer

2011-03-07T13:34:00.000-08:00

A number can be represented as ASCII characters (char) or integers (int). Thus, the question is how we can convert from char to int. For example, we want to convert '123' to 123 or '45' to 45.

To solve this problem, we need to revisit the ASCII table for a little bit. Moreover, we are interested in the characters '0' to '9' in the table. The special thing about those characters is that they stand consecutively in the table. That means their decimal values are consecutive positive integers. For example, '0' is 48; '1' is 49; and '2' is 50. Thus, if we have '1' - '0', we'll get an integer value of 1 because 49 - 48 = 1. That's how we're gonna convert the number from char to int. Here is the algorithm in C++:

#include<iostream>
#include<math.h>
using namespace std;

int digitsToInt(char arrayOfChars[], int size)
{
  int digitPos = size - 1;
  int result = 0;
  for (int i = 0; i < size; i++)
  {
    result += ((int)(arrayOfChars[i] - '0')) * pow(10, digitPos);
    digitPos--;
  }
  return result;
}

Explanation: our function takes an array of characters containing the char representation of the number and the size of the array.

digitPos keeps track of which digit we're converting. It is important to do so because we must convert the digit into appropriate value in integer (remember that ASCII digits are between '0' and '9'). If the number passed in is '102', then the first digit '1' represents 100 in integer. The algorithm must know that and multiply '1' with 100 after converting it into int 1.
result is the final number in int. Our strategy here is to convert each digit into its appropriate int value and then add all of them up. That will give us the final result in integer. For example, if we need to convert '12', we will convert '1' to 1 first and multiply it by 10. Next, we convert '2' to 2 and multiply it by 1 (2 is the last digit). Therefore, the final result is 10 + 2 = 12.
We loops through the array and convert each digit into the appropriate int value and add that value into the result. As explained above, by subtracting the digit by '0' and casting the result into int we'll get the correct int number corresponding to that digit. However, that's not all. Notice how we use the function pow(10, digitPos) to get the correct value for each digit. This method works because our numbers are base 10 numbers. Thus, by multiplying a number by 10 to the power of its position, we'll get the correct value for that number. Don't worry if you are confused, we'll do an example later.
Lastly, we decrement digitPos by one because we will move to process the next digit which has one order less than the current number.
Return the final result which is the sum of all the int values of our digits.

Example: we'll convert the number '123' into integer.

Our digitPos is 2 because we process the first digit '1' first and it is in the hundredth position. So, '1' - '0' gives int 1. Then, 1 * 10 ^ 2 = 100. Add that into our result. We have 100 after the first iteration. Moreover, digitPos decreases by 1 because we are about to process the tenth digit.
Second iteration, digitPos is 1. And we have '2' - '0' = int 2. Multiplying 2 by ten to the power of its position, we have 2 * 10 ^ 1 = 20. Add that value to the result and we end up with the sum of 120. Finally, we decrement digitPos by 1.
Last iteration, digitPos is 0. And, '3' - '0' = int 3. Multiplying 3 by ten to the power of its position, we have 3 * 10 ^ 0 = 3. Add 3 into the result and we have int 123. Loop ends and our algorithm returns the result of 123.

Thanks for reading and as always feel free to leave any comment or suggestion :)

Check if two rectangles intersect

2011-02-28T12:42:00.000-08:00

This is a one of the classic problems in graphics programming and game development. So, let's see how we can solve it.

Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. As you move down the screen, the y value increases. And, as you move right the x value increases.

For the general purpose of this post, assume that we have a right-handed coordinate system where the origin is at the bottom-left screen such that it is exactly like the coordinate system we learn in high school algebra. Also, the rectangles that we have to check are on that coordinate system and are identified by the coordinates of their top-left corner and bottom right corner. For instance:

Here are scenarios where we consider two rectangles as intersecting each other:

Of course, those figures are just special cases of intersecting rectangles. There are many more ways to draw them, but four figures should give us enough information about what considered intersection. However, to solve this problem it is better to focus on when two rectangles do not intersect.

Here are example of non-intersecting rectangles:

From those pictures, we can infer that two rectangles are not intersecting each other if they have one of the four conditions:

Right edge of blue is closer to the left of the screen than the left edge of red
Bottom edge of blue is further from the bottom of the screen than the top edge of red
Top edge of blue is closer to the bottom of the screen than the bottom edge of red
Left edge of blue is further from the left of the screen than the right edge of red

So, if our rectangles don't have any of those conditions, then they intersect one another! Here is the code:

#include<iostream>
using namespace std;

struct Point
{
  float x;
  float y;
};

struct Rect
{
  Point topLeft;
  Point bottomRight;
};

bool isIntersect(Rect rect1, Rect rect2)
{
  if (rect1.topLeft.x >= rect2.bottomRight.x 
      || rect1.bottomRight.x <= rect2.topLeft.x 
      || rect1.topLeft.y <= rect2.bottomRight.y 
      || rect1.bottomRight.y >= rect2.topLeft.y)
    return false;
    
  return true;
}

Our rectangles are defined by their top-left and bottom-right vertices each of which is defined by a pair of x and y coordinates. Thus, there are two structs. One for the point and one for the rectangle.

Our method to determine intersection is simple, we just have to check for all four conditions explained above. If any of those conditions is true then our rectangles do not intersect. Notice that we use x values when comparing the distance of right and left edges of the rectangles. Also, we only use y values when comparing the distances of top and bottom edges of the rectangles.

That's it for this post. Please leave a comment if you have any question / suggestion. Thanks

Retrieve middle node of a singly linked list

2011-02-22T17:43:00.000-08:00

Question: find the middle node in a singly linked list. If the linked list has even number of nodes, return either of the middle nodes. For example, 1->2->3 returns 2 but 1->2->3->4 returns either 2 or 3.

This is a common algorithm concerning linked lists. The trick here is to have two pointers moving at different paces. When the faster pointer reaches the end of the list, the slow pointer is pointing to the middle node in the list. Here is the algorithm implemented in C++:

#include<iostream>
using namespace std;

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

Node* findMidofLinkedList(Node* head)
{
  Node *fast = head;
  Node *slow = head;

  while (fast->next != NULL && fast->next->next != NULL)
  {
    fast = fast->next->next;
    slow = slow->next;
  }

  return slow;
}

Explanation: We maintain two pointers fast and slow. For every iteration of the while loop, we move the fast pointer two nodes forward and move the slow pointer one node forward. When the node next to the fast pointer is NULL or when the node next to the next node of the fast pointer is NULL, the slow pointer has reached the middle node. We simply returns the slow pointer.

Example: Let's trace our algorithm with this linked list 1->2->3->4->5:

First iteration: fast points to 3. slow points to 2. fast->next is 4. fast->next->next is 5.
Second iteration: fast points to 5. slow points to 3. fast->next is NULL. fast->next->next is NULL. So we stop after this iteration. Slow is now pointing at 3 which is the middle node.