Search This Blog

Saturday, January 29, 2011

Caching lengths and frequencies of lettered words in a paragraph

Suppose that we have a very short paragraph like this "Roses are red. Violets are blue. This verse doesn't rhyme. And neither does this one," how can we find and save all different word lengths and their frequencies of occurrence? For example, "red" is 3 letter long and there are a total of five letters of this length (are, red, are, and, one) in the paragraph. Then one of the items in our cache should be 3 and 5

Just like other problems where we have to keep track of the number of occurrences, we should use a hash table. The algorithm is like this:

public HashMap <Integer, Integer> countWordLengthFrequency(String[] paragraph)
{
    HashMap <Integer, Integer> frequencyTable = new HashMap<Integer, Integer>();

    for (int i = 0; i < paragraph.length; i++)
    {
      if (!frequencyTable.containsKey(paragraph[i].length()))
        frequencyTable.put(paragraph[i].length(), 1);
      else
      {
        Integer count = frequencyTable.get(paragraph[i].length()) + 1;
        frequencyTable.put(paragraph[i].length(), count);
      }
    }

    return frequencyTable;
}

Explanation:we just loop through the words in the paragraph. For each word, we check to see if its length is already in the hash table. Therefore, there are two cases. 1) If the word's length is already in the table, we increase the frequency count by one. 2) Otherwise, we hash the length into the table and set the frequency to 1 because this is the first time this length is hashed into the table.

Obviously, the time complexity is O(n) because we have to check every word in the paragraph. Moreover, in the worst case, the space complexity is O(n). That's when every word in the paragraph has a different length than the other words. If you know any better algorithm for this problem, please leave it in the comment below. Thanks for reading!

Thursday, January 27, 2011

Bit Manipulation Tips & Tricks (part 2)

Hello and welcome to the second part of "Bit Manipulation Tips & Tricks." If you haven't read the first part yet, here is the link of you. Read it! :)

1. Turning a bit off without affecting other bits

Turning a bit off means to change 1 bits (on) to 0 bits (off) and if the bits are already off then they'll stay off. This can be accomplished by using the ~, << and & operators. Here is the genera formula:

turnBitOff (int bitString, int bitPosition)
{
  return bitString & ~(1 << bitPosition);
}
  • bitString: is the set of bits we want to change. For instance, we want to turn off a bit in the bit string 1110.
  • bitPosition: is the position of the bit in the bit string that we want to turn off. For instance, we want to turn off the 3rd bit (bold) in 1110. Then, the bit position is 3.
  • 1 is just our help bit string. Its binary value is 0001.

We can now do an example to see how our formula. To turn off the 3rd bit of the bit string 1100, we do this: 1100 & ~(0001 << 3) = 1100 & ~(1000) = 1100 & 0111 = 0100. It works! :)

2. Turning a bit on without affecting other bits

If we can turn a bit off, then can we turn a bit on? Of course, we can. It's just the matter of replacing the & operator with the || operator and getting rid of the ~ operator. Here is the formula:

turnBitOn (int bitString, int bitPosition)
{
  return bitString || (1 << bitPosition);
}

To convince ourselves that this works, we should do two examples. To turn on the 2nd bit of bit string 1011 off, we do this: 1011 || (0001 << 2) = 1111 || (0100) = 1011 || 0100 = 1111. It works! How about trying to turn a bit on even if it's already on? So, to turn on the 3rd bit of bit string 1111 (which is already on), we follow the formula: 1111 || (0001 << 3) = 1111 || 1000 = 1111. As you can see, noting changed because the bit has already on.

3. Keeping track of boolean values of a data set using bits

Let's say we have an array of pictures and we want to keep track of them to see which one is in stock and which one is out of stock. How do we keep track of those pictures with least amount of memory? We can use a bit string.

If we have an array of 4 pictures to keep track of, we will have a bit string of 4 bits 0000. Whichever element is in stock will have its corresponding bit on. For instance, if picture no. 0 is in stock then the 0th bit is on, resulting in the bit string of 0001. If picture no. 3 is in stock then the 3rd bit is on, resulting in the bit string of 0100. If all pictures are in stock then all bits are on -> 1111.

We use the picture selling business as an example for convenience, but this technique can be applied to many different situations. For instance, we can use it to keep track of repeating letters in a word instead of using a hash table.

To make this whole scheme work, we need to employ the 1st and 2nd technique above. We also need a way to check to see if a bit is on or off to find out if a picture is in stock or no. Therefore, we will use a technique discussed in the first part of this tutorial. It is to check if a bit is on or off. If you don't remember, here is the formula for that technique:

int isAvailable (int bitString, int targetNum)
{
  return bit_string & (1 << targetNum);
}

Let's go back to our example. We have the bit string of 0001 that represents our stock. And, we want to know if picture no. 3 is in stock or not. By applying the formula, we can see that:

  • 1 = 0001 is our helper string and targetNum = 3 because we need to know about picture no. 3
  • bit_string & (1 << targetNum) = 0001 & (0001 << 3) = 0001 & 1000 = 0000 = 0 (in decimal)
  • return 0 means not in stock while any number > 0 means in stock :)

If the picture is in stock again, we just have to turn the bit on to 1 by using the "turning on a bit" technique. Moreover, to indicate a picture is out of stock, we use the "turning off a bit" technique.

As you can see, if we use this method for keeping track of a large quantity of data, we can save a lot of memory space because bits are well bits they take the least amount of memory! Besides, computers are faster at executing bit operations.

Thanks for reading this part. And keep checking back, we'll have more fun with bits :)

Thursday, January 20, 2011

Bit Manipulation Tips and Tricks (Part 1)

In this series, we'll try to compile a list of tips and tricks that are useful for performing bitwise operation.

1. Multiply a number by a power of two using bit left shift

Remember the bit shift operation? << and >>? Well if we left shift a number, we are multiplying that number by a power of two. For example, 1 = 0001. If we left shift it by 1, we'll have 1 << 1 = 0010 = 2 = 1 * 2^1. If we left shift it by 2, we'll have 1 << 2 = 0100 = 4 = 1 * 2^2. Thus, the general formula is:

a << b = a * 2^b

2. Divide a number by a power of two using bit right shift

In opposite to left shift, when we right shift a number we divide it by a power of two. For example, 4 >> 2 = 0100 >> 2 = 0001 = 1 = 4 / 2^2. Here is the general formula:

a >> b = a / 2^b

3. Toggle a specified bit in a bit string without effecting other bits

For example, we have a bit string 0111 and you have to turn the left most bit on 0 -> 1. How can we do that? We'll use XOR (^), left shift operation (<<) and the 0001 (1) bit string.

  1. Shift the 1 bit of 0001 to the position of the bit you want to change. In our example, we need to toggle the 3th bit (first bit is at position 0, that's why our target is at 3rd position not 4th). Thus, we shift 0001 to the left by 3. 0001 << 3 = 1000.
  2. Lastly, we XOR our bit string with the helper bit string. So, we have 0111 ^ 1000 = 1111

The general formula is:

bit_string = bit_string ^ (1 << positionOfBitToToggle)

4. Checking if a bit is on or off without affecting other bits

Let's say that we have a bit string of 1101 and we want to know if the 2nd bit is on or off. Here is a way to do it:

int isAvailable (int bitString, int targetNum)
{
  return bit_string & (1 << targetNum);
}
  • bit_string: the bit string whose bits we are interested in. For example, 1101 and we are interested in the 2nd bit which is the bit in bold.
  • 1: is just our helper bit string. Its binary value is 0001
  • targetNum: is the position of the bit we're interested in. For example, targetNum is 2 if we're interested in the 2nd bit of 1101.

According to our example, to find out if the 2nd bit of 1101 is on or off, we'll just apply the formula like this: 1101 & (0001 << 2) = 1101 & 0100 = 0100 = 4. The result is 4 which is greater than 0, so we know that the bit we're interested in is on (1).

Let's do another example, if our bit string is 1001 and we're interested in the 1st bit which is 0 (in bold). Again, just apply the formula: 1001 & (0001 << 1) = 1001 & 0010 = 0000 = 0. The result is 0, so we know that our bit is off (0).

This trick concludes the first part of our series. Please stay tuned. Thanks for reading.

Wednesday, January 19, 2011

Find Lowest Common Ancestor in Binary Search Tree

A common algorithm concerning binary search tree(BST) is finding the lowest common ancestor(LCA) of two given nodes. For example, if we have this tree, then LCA of 7 and 1 is 5. Or, the LCA of 0 and 1 is 2. So how can we do this? There are two ways to do this. We can use recursive or iterative algorithms.

For the recursive algorithm, we're going to use a convenient method to check if a node presents in a tree. That method was covered in this post "Searching for a node in a binary tree" The convenient method name is isNodeInTree(). It returns true if a node presents in a tree. Otherwise, it returns false. Next, we can recursively do the following steps for each node in a tree in order to find the LCA.

  1. If the current node is null or if one of the nodes we need to find LCA for is null, we return null.
  2. Next, if both nodes present in the current node's left subtree, then we call the function on the left child. The reason is that if the left child has both nodes, it is the lower common ancestor than the current node.
  3. Repeat step 2 for right child node
  4. In the end if neither left or right child node is the LCA, we know that the current node is the LCA

Node getLCAforNodesOfBST(Node root, Node firstNode, Node secondNode)
{
  if (root == null || firstNode == null || secondNode == null)
    return null;

  if (isNodeInTree(root.left, firstNode) && isNodeInTree(root.left, secondNode))
    getLCAforNodesOfBST(root.left, firstNode, secondNode);
  else if (isNodeInTree(root.right, firstNode) && isNodeInTree(root.right, secondNode))
    getLCAforNodesOfBST(root.right, firstNode, secondNode);
  else
    return root;
}

As you can see, the recursive method requires a lot of extra memory and steps. However, it can be used for regular binary trees, not just binary search trees. On the other hand, we can use an iterative algorithm to find LCA too. In fact, iterative method below is more efficient than recursive one because it uses less memory. However, this applies to only binary search trees

Node getLCAforNodesOfBST(Node root, Node firstNode, Node secondNode)
{
  Node currentNode = root;
 
  while (currentNode != null)
  {
    if (currentNode.data < firstNode.data && currentNode.data < secondNode.data)
     currentNode = currentNode.right;
    else if (currentNode.data > firstNode.data && currentNode.data > secondNode.data)
     currentNode = currentNode.left;
    else
     break;
  }

  return currentNode;
}

The strategy here is straight forward. We just look at the current node. If it is less than both of the nodes we're searching LCA for, we advance to the current's node right child. Why? Because this is a binary search tree! If the current node is less than both nodes, then those nodes must be on the right subtree of the current node. Moreover, we also know for sure that the current node is not the LCA.

In the next case, if the current node is greater than both of the nodes we're searching for, then the LCA must be on the left subtree of the current node. Thus, we advance to the current node's left child.

Lastly, if both of those cases aren't true, then the current node must be the LCA of the nodes we're searching LCA for.

Hope that helps :) If you have any question please put it in the comment section below. Thanks.

Monday, January 17, 2011

Swapping two integers without using a temporary variable

This is another interesting algorithm using bit manipulation. For example, let's say we have two integers x = 3 and y = 2. Our goal is to swap x and y values so that x = 2 and y = 3 after the swap.

Traditionally, we just use a temporary variable, called temp for example, to store the swapping values:

void swapIntegers (int x, int y)
{
  int temp = x;
  x = y;
  y = temp;
}

However, the XOR operation can help us accomplish the above with no extra variable needed:

void swapIntegers (int x, int y)
{
  x ^= y;
  y ^= x;
  x ^= y;
}

That's it :) So why does it work? Well because of the property of XOR operation (^). Lets x = 3 and y = 2. The binary form of those two are x = 0011 and y = 0010.

  • First step, x ^= y --> 0011 XOR 0010 makes x = 0001.
  • Second step, y ^= x --> 0010 XOR 0001 makes y = 0011 = 3.
  • Third step, x ^= y --> 0001 XOR 0011 makes x = 0010 = 2.

Given an integer array and a number X, find all unique pairs of (a, b) whose sume is equal to X

Here is an example to the question. Suppose we have an int array = {5, 3, 7, 0, 1, 4, 2} and X = 5. The unique pairs that sum up to 5 are (5, 0) (3, 2) and (1, 4).

There are two approaches to this problem. The first approach is to use brute force which gives time complexity of O(n^2) and space complexity of O(n). We basically just have to loop through the array and for each number we add it to each of other numbers and see if they sum up to 5. If so, we print out the pair. Here is the code for brute force approach:

void findPairOfSum(int arrayOfNum[], int arraySize, int sum)
{
  for (int i = 0; i < arraySize; i++)
  {
    for (int j = i; j < arraySize; j++)
    {
      if (arrayOfNum[i] + arrayOfNum[j] == sum)
        cout << "(" << arrayOfNum[i] << ", " << arrayOfNum[j] << ")" << endl;
    }
  }
} 

The second approach is to use a hash table to store the difference between sum and each of the elements in the array. Then as we loop through the array, check each element against the hash table. If the element presents, then print out the key value pair. For example, if we hash the example array we'll have this hash table:

Key   Value
5        5 - 5 = 0
3        5 - 3 = 2
7        5 - 7 = -2
0        5 - 0 = 5
1        5 - 1 = 4
4        5 - 4 = 1
2        5 - 3 = 2

This approach will have the time complexity of O(n) and space complexity of O(n). Thus, chose your method wisely, depending on your need (speed or space efficiency).

Saturday, January 15, 2011

Validate number input with Regular Expression in JavaScript

Validating inputs submitted by users is always a big challenge for writing any application that requires users input. For example, if we have a mortgage calculator app, we must validate and make sure that users don't enter a letter for the interest rate box.

For the mortgage calculator, it is easy to validate input that we don't need regular expression. But a lot of problems require complex validation if we don't know regular expression. For example, validate the zip code input which must be five digit long such as 22003 and 97850.

In this post, we'll learn how to do such validation with JavaScript. However, the regular expression pattern can be applied for other languages as well.

Let's take a look at this JavaScript code:

function validateZipCode(zipCode)
{
  var pattern = /^\d{5}$/;
  return zipCode.search(pattern);
}

This code will return 0 if the input contains only a string of five digits. Otherwise, it will return -1. Pretty neat right? Let's break down the pattern.

  • / marks the start of the pattern
  • ^ specifies that the pattern must start at the beginning of the input string
  • \d{5} means pattern of five consecutive digits in the string. For example, 9780 is a match but 98t034 is not. We can change the number inside { } to match more digits. For example, \d{6} matches six consecutive digits.
  • $ specifies that the end of the pattern must also be the end of the input string. ^ and $ combines to make sure that the input contains only five digits and nothing else. For example, t97850 matches the \d{5} and \d{5}$ pattern but doesn't match ^\d{5}$ and 97850f matches \d{5} and ^\d{5} but doesn't match ^\d{5}$. Only 97850 matches ^\d{5}$ pattern.
  • / marks the end of the pattern. Notice that a pattern must be enclosed within a pair of / / signs.

Given an integer array of repeating numbers. All but one number repeats an odd number of times. Find that number in O(n) time and no additional data structure?

Here is an example about the question. If we have an array = {3, 2, 1, 2, 1}, number 2 and 1 repeat two times (even number of times) while number 3 repeats only once (odd number of times). Thus, the answer to our question will be number 3.

This question is relatively easy if we are allowed to use an additional data structure. For example, we can use a hash table to maintain counts of repetition for each number in the array. Then, we look for the number with odd count. However, since we can't use additional storage, the question becomes difficult.

Well to answer this question, we need to use bit manipulation. Take a look at the code below:

int findOddRepeatInArray(int arrayToFind[], int arraySize)
{
  int result = 0;
  for (int i = 0; i < arraySize; i++)
  {
    result ^= arrayToFind[i];
  }
  return result;
}

Wow, that's much shorter and efficient than using hash table! However, this requires the knowledge of bit manipulation which is a scary topic :( for a lot of programmers.

The caret '^' sign means XOR (exclusive OR). And, our algorithm works because XOR of two same number is 0. For example, 2 XOR 2 = 0 because 0010 XOR 0010 = 0000. Thus, all the even repeating numbers will yield the result = 0 while the odd repeating number will yield itself as the result. In our example, we know 3 is the odd-repeating number because 3 XOR 0 = 3.

Friday, January 14, 2011

How merge sorted arrays into one

Question: given 2 sorted arrays. First array has X elements and of size X. Second array has Y elements and size N where N = X + Y. Merge the first array to the second array and return the second array so that the new second array is also sorted.

I encountered this question in an interview with a big software company in Seattle. So, I thought it would be useful to share it.

Let's look at an example to understand the problem better. If we have two arrays: array1 = {1, 3, 5, 9} and array2 = {2, 6, 8, 10}, the merged array is array2 = {1, 2, 3, 5, 6, 8, 9, 10}. Note that according to the question, array2 has enough free space to contain all elements of array1.

Here is how we're gonna solve this. Assume that we have two int arrays for simplicity, the code looks like this:

int* mergeSortedArray(int array1[], int numOf1Elements, int array2[], int numOf2Elements)
{
  int pivotIndex = numOf1Elements + numOf2Elements - 1;
  
  int array1Index = numOf1Elements - 1;
  int array2Index = numOf2Elements - 1;

  while (array1Index >= 0 && array2Index >= 0)
  {
    if (array1[array1Index] >= array2[array2Index])
    {
      array2[pivotIndex] = array1[array1Index];
      array1Index--;
    }
    else
    {
      array2[pivotIndex] = array2[array2Index];
      array2Index--;
    }
    pivotIndex--;
  }

  if (array1Index >= 0)
  {
    while (array1Index >= 0)
    {
      array2[pivotIndex] = array1[array1Index];
      pivotIndex--;
      array1Index--;
    }
  }

  return array2;
}

First, get the index of the last cell in array2, called pivotIndex. Next, we get the index of the last element in array1, named array1Index, and the index of the last element in array2, named array2Index.

Secondly, we loop through the arrays until either array1Index and array2Index becomes negative. For each iteration, we look at the values at array1[array1Index] and at array2[array2Index]. If array[array1Index] is greater than or equal to array2[array2Index], we put it at the end of array2, ie. array2[pivotIndex]. Otherwise, we put array2[array2Index] at array2[pivotIndex]. This gives the effect that all big values are pushed at the end of the array in order. Also, if an element from array1 gets put in array2, we decrement the array1Index by one to access to the next element in array1. Otherwise, we decrement array2Index by one to access to the next element in array2. After all that, we need to decrement pivotIndex by one to move to the next available cell in array2.

Lastly, we just copy leftover elements in array1 into array2. How do we know if array1 has leftover after the main loop? Well, if array1Index is still >= 0 then there is leftover in array1

If you are confused, use a piece paper and pencil to trace the code using the arrays in the example. It will clear things up. I promise :)

Thursday, January 13, 2011

How to rotate an array

One of the classic problems with array is to perform in-place rotation on the array. For example, if we have an array of integers such as int[]array = new int[]{1, 2, 3, 4, 5, 6} and we want to rotate it around index 2, then the rotated array is {3, 4, 5, 6, 1, 2}. So, how can we rotate an array around a given index? Well here is the algorithm with explanation follows after:

public void reverseArray(int[] array, int start, int end)
{
 int i;
 int temp;

 while (start < end)
 {
  temp = array[start];
  array[start] = array[end];
  array[end] = temp;
  start++;
  end--;
 }
}

private static void rotateArrayByIndex(int array[], int rotatePos, int arraySize)
{
 reverseArray(array, 0, rotatePos - 1);
 reverseArray(array, rotatePos, arraySize - 1);
 reverseArray(array, 0, arraySize - 1);
}

The strategy consists of three steps. First, we reverse the first half of the array--starting from index 0 to (rotate index - 1). Then we reverse the second half of the array--starting from rotate index to the last index of the array. Lastly, we reverse the whole array.

The first function reverses a specific portion of an array. It's simple. We just swap the last element with the first element, the second to last element with the second element and so on until the start and end indices meet.

Once we have the reverse function, the rotate function is trivial. rotateArrayByIndex does the three steps that we outlined above in order to rotate an input array by a specified index.

Note:The functions didn't include error checking procedures. You can improve them by writing your own error-checking code :)

Breadth First Search in Binary Tree

Breadth First Search (BFS) is a very important algorithm for binary tree. So what does it mean? There are different ways we can search for a node in a binary tree. BFS is one of the those ways.

Specifically, BFS looks at nodes at lower depth first before moving on to the next depth. It is, in fact, level traversal. For example, lets take a look at the tree to your left. If we're to search for Node 3, the order that BFS goes is like this 5->2->8->0->1->3 (found!)

That's what a BFS is. Here is the algorithm for it. It is level traversal algorithm with a twist because we will stop as soon as we find the needed node.

public boolean binaryTreeBFS (Node root, int value)
{
  if (root == null)
    return false;

  LinkedList queue = new LinkedList();
  Node tempNode;
  queue.addLast(root);

  while (!queue.isEmpty())
  {
    tempNode = queue.remove();

    if (tempNode.data == value)
      return true;
    else
    {
      if (tempNode.left != null)
      queue.addLast(tempNode.left);

      if (tempNode.right != null)
      queue.addLast(tempNode.right);
    }
  }
  return false;
}

First we check the root. If it is null, then return false because there is nothing else to look for.

We then create a queue and a temporary node. The queue will store nodes according to their depth so that nodes of lower depth are always processed first.

Next, we loop search through every node in the queue, starting with the root. Thus, for every iteration, we remove the node at the beginning of our queue. If that node is what we're looking for then return true. Otherwise we'll add its children (nodes of lower level) to the end of the queue, so we can look at them later.

After looking at all nodes, if the needed node is not found yet, return false because it is not in the tree

As you might expect, in the worst case, this algorithm will take O(n) time where n is the number of nodes in the binary tree. The reason is that BFS has to look for every node.

That's all for now. If you have any question/suggestion please leave it in the comment section below :)

Monday, January 10, 2011

Searching for a node in a binary tree


Question: Given a node, write an algorithm to determine if that node is in binary tree?

This is one of the basic algorithms about binary tree that you should know how to implement. It can help aid in designing other algorithms for solving more complicated problems such as finding the Lowest Common Ancestor of two nodes in a binary tree.

Moreover, job interviewers may ask you to implement it or use it to solve some other problems. Thus, spending a few minutes to understand the algorithm is definitely worth it.

Here is a the recursive / easiest algorithm to answer the question:

public boolean isNodeInTree(Node node, Node root)
{
 if (node == null || root == null)
  return false;
 if (root.data == node.data)
  return true;
 
 return isNodeInTree(node, root.left) || isNodeInTree(node, root.right);
}


In short, we just look at every node under the binary tree. And we do it recursively.

If the node we're looking at is null or if the node we're looking for is null then the node we're looking for is not in the tree.

Next, if the current node has the same data as the node we're searching for then return true because we've found what we need.

Otherwise, we'll continue to do the same for both the left and right child of the current node. And return true if we find the node we need in either left or right child. In case both left and right child don't contain the node we need then it is not in the tree.

Monday, January 3, 2011

Drawing Basic Shapes with HTML5 Canvas (last Part)

Welcome back to another edition of "Drawing Basic Shapes with HTML5 Canvas." Here are the links to the first three parts: part 1, part 2 and part 3

This post will cover the last part of the series. Specifically, we'll draw a circle using HTML5 Canvas. If you find the explanation difficult to understand, please review the previous parts of the tutorial. I covered a lot of basic information in those parts.

Alright, here we go!

Circle:

As usual, please check out the code first and try to see if you can understand it. Then, you can read the explanation.

<!DOCTYPE HTML>
  <html>
    <body>
      <canvas id="myCanvas" width="200" height="100" style="border:1px solid #c3c3c3;">
        Your browser does not support the canvas element.
      </canvas>
      <script type="text/javascript">
        var c=document.getElementById("myCanvas");
        var cxt=c.getContext("2d");
        cxt.fillStyle="#FF0000";
        cxt.beginPath();
        cxt.arc(70,18,15,0,Math.PI*2,true);
        cxt.closePath();
        cxt.fill();
      </script>
    </body>
  </html>
<canvas>: as usual, we define a canvas with specified dimension and id. We also make the canvas border visible for easy drawing.

<script>: we first get a reference to our canvas and then get the its 2D drawing context. If you don't know what a context is, please review the second part of the tutorial. 

  1. fillStyle(): use red color to fill our circle.
  2. beginPath(): this method creates a new path for custom drawings. What is a path? It is a collection of different sketches and strokes. A shape is considered a path because a shape is made up of many different strokes (lines, arcs, ...). Each path has its own properties such as stroke color and fill color. 
  3. arc(): draw an arc or a circle. The full method signature is arc( center_x, center_y, radius, startAngle, endAngle, antiClockwise). 
center_x and center_y: the coordinates of the center of the circle or arc. 
radius: radius of the circle / arc.
startAngle and endAngle: start and end point of the circle / arc in radian. If you forgot your trigonometry,  use this JavaScript formula to convert degree to radian (Math.Pi / 180) * degree. Since we draw circle, we need to start our angle at 0 and end our angle at 360 degree or PI * 2. 
antiClockwise: a boolean that is true to draw the circle / arc anti-clockwise and false to do the opposite.
closePath(): end the path after we has done our drawing. When drawing many different shapes on the same canvas, we must call beginPath() and closePath() for each shape.
fill(): fill our circle with specified color (red).
Here is a picture. Hope it helps to clear up any confusion:


Well, that concludes our tutorial. If you have any question / suggestion please leave it in the comment below. 

I'm preparing for more advanced tutorial on HTML5 Canvas! So check back for more goodies later :)