Check if two rectangles intersect

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:

1. Right edge of blue is closer to the left of the screen than the left edge of red
2. Bottom edge of blue is further from the bottom of the screen than the top edge of red
3. Top edge of blue is closer to the bottom of the screen than the bottom edge of red
4. 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

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:

1. First iteration: fast points to 3. slow points to 2. fast->next is 4. fast->next->next is 5.
2. 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.

Introduction to Thread in Java

What is Thread?

Thread: light weight process which can access the resource of the process that creates it. Creating a thread is more efficient than creating a new process. Multi-threaded programs utilize the CPU better than single thread programs. Therefore, multi-threading /concurrency is an important feature in Java.

Thread is efficient because multiple threads can share the same resources. However, this also creates problems in communication between threads and the integrity of the resources they share.

In Java, the Thread class and the Runnable interface are used to make classes executable in threads. In order words, if we want our class to be executed in a separate thread, we must either:

• Subclass the Thread class
• Or implement the Runnable interface

Defining threadable classes by subclassing the Thread class

We can make our class threadable by subclassing the Thread class like this:

public class ThreadableClass extends Thread
{
  public void run()
  {
    //code to be executed in thread...
  }
}

Next, the only thing that we must do is to override the run() method in our class. The reason is that when the objects of our class are executed as threads, the run() method is called immediately and only code inside this method is executed.

To use our threadable class, we can just instantiate it like any other class. For example:

ThreadableClass newThread = new ThreadableClass();

Defining threadable classes by implementing the Runnable interface

In this method, to create a new thread, we just need to create a new Thread object by calling the Thread constructor. There are several thread constructors. You can find them here Java Thread API. We'll focus only on the most common ones which are Thread(Runnable target) and Thread(Runnable target, String name).

Thread(Runnable target) creates a new thread that contains the "target" runnable object. This means that whenever the thread starts, the object is immediately executed in that thread.

Thread(Runnable target, String name) not only creates a new thread containing the "target" object but it also accepts a name which you give to it.

Here is an example of how to create a thread and give it a name:

Thread newThread = new Thread(myObject, "Thread 1");

Similar to subclassing the Thread class, the class that implements the Runnable interface must also implement the run() method. That method is called when a thread starts. Therefore, any code to be executed in the thread must be inside the run() method. In addition, the thread stops when the run() method returns. It is important to remember that when implementing the run() method.

Here is how to implement the Runnable interface:

public class RunnableClass extends ParentClass implements Runnable
{
  public void run()
  {
    //code to be executed in thread...
  }
}

Notice that our RunnableClass is now a runnable class while still able to inherit methods from its ParentClass.

To use our runnable class, we must instantiate the Thread object and pass in the object of our runnable class as an argument. Whenever the Thread object starts, our object will be executed inside that thread. For instance:

Thread runnableThreadClass = new Thread(runnableClassObject, threadName);

Implement Runnable vs. subclass Tread

So which method is better? In general, implementing the Runnable class is the way to go because it gives our classes better flexibility. For instance, once our classes extend the Thread class, they cannot inherit from any other class because Java doesn't support multiple, direct inheritance.

However, when writing simple applications that utilize threads, subclassing the Thread class is faster and easier to use.

That is it for this first installment. Here is the link to the second post of the series "Thread Life Cycle".

Construct a full binary tree from a pre-order list of marked nodes

Question: construct a full binary tree from a list of nodes in pre-order. The nodes are marked 'i' if they are inner nodes and are marked 'l' if they are leaf nodes.

Example given a list of nodes marked as (i, i, i, l, l, i, l, l, i, l, l), we need to construct a tree from those nodes so that the result looks like this:

Notice how all "l" nodes are leaf nodes and "i" nodes are inner nodes? Moreover, since the nodes are given in pre-order, we must take into account the node order when we put them into the tree. The first node in the list will always be the root node because in pre-order, root node comes first then left most and then right most. Also, since this is a full binary tree, we know that every node, except leaf node, must have 2 children.

With the information provided by the question, here is the code to solve this problem:

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

struct Node
{
  Node* left;
  Node* right;
  char mark;
};

Node* constructFromPreorder(Node* preorder[], int treeSize)
{
  stack<Node*> stackOfNodes;

  Node* root = preorder[0]; //pointer to root node
  
  stackOfNodes.push(preorder[0]);

  int count = 1;
  
  while (count < treeSize && !stackOfNodes.empty())
  {
    if (stackOfNodes.top()->left == NULL || stackOfNodes.top()->right == NULL)
    {
      Node* currentNode = preorder[count];
      
      if (stackOfNodes.top()->left == NULL)
        stackOfNodes.top()->left = currentNode;
      else if (stackOfNodes.top()->right == NULL)
        stackOfNodes.top()->right = currentNode;

      if (currentNode->mark == 'i')
        stackOfNodes.push(currentNode);
        
      count++;
    }
    else
    {
      stackOfNodes.pop();
    }
  }

  return root;
}

Explanation: assuming that we have the Node struct like the one in the code, then the left pointer of a node points to the left child of that node while the right pointer points to the right child. Hence, we can now put those nodes in a tree by connecting parent nodes to child nodes.

1. Declare a stack to keep track of inner nodes. Whenever we encounter an inner node, we'll push it into the stack. And, we'll pop it when it has two children. This makes sure that every inner node is connected to its two children.
2. Add the root which is the first node in the list into the stack. Because we'll add and push the nodes until the stack is empty or until we run out of nodes, we need to add the root to initialize the stack.
3. Set a count flag to 1. This count flag is used to exit the loop. When count reaches the total number of nodes in the list, it means we've run out of nodes to add into our tree. Moreover, we initialize the flag to 1 since we have already processed one node(root node) from the list in step 2.
4. Loop until either we run out of nodes to add or until the stack is empty.
5. For every loop:
   
   a) If the top of the stack is not connected to its two children yet, we get a node out of our list and attach it to the top node in the stack as that node's child. Then, we push that newly retrieved node into the stack if it is an inner node. We also increase the count flag by 1, so we can retrieve the next node in the list in the next loop.
   
   b) If the top of the stack has already been connected to two children, we pop it and do nothing.
   
   
6. When the loop is done, we simply return the pointer to the root. Whichever function uses this pointer will have access to the entire tree that we have just constructed.

Performance: this algorithm has time complexity of O(n) where n is the number of nodes in the list because we loop through the list only once. In terms of space, the algorithm has space complexity of O(m) where m is the depth of the tree we have to construct. The reason is that in the worst case we must store the second-deepest nodes into our stack.

If you have better solution or any suggestion, please feel free to leave it in the comment below. It'll be greatly appreciated :)

How to determine if two strings are anagrams?

First of all, what are anagrams? Well, anagrams are words that have the same characters which can be at different locations in the words. For example, "level" and "level" are anagrams, a special kind of anagrams because they are exactly the same in terms of characters and their locations in the words. Moreover, "rat" and "art" are also anagrams because all characters in "rat" are in "art", no more no less. Another example is "seek" and "ekes". Pay attention to the numbers of "e" letters in both words, they must be the same amount too. Thus, "seek" and "sek" are not anagrams.

Now we know what anagrams are. Let's take a look at the solution to the posted question:

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

bool areAnagrams(string str1, string str2)
{
  if (str1.length() != str2.length())
  {
    return false;
  }

  int charsTracker[26] = {0};

  for (int i = 0; i < str1.length(); i++)
  {
    charsTracker[str1[i] - 'a']--;
    charsTracker[str2[i] - 'a']++;
  }

  for (int i = 0; i < 26; i++)
  {
    if (charsTracker[i] != 0)
      return false;
  }

  return true;
}

Explanation:

1. First we check to see if the two strings have the same length. If not, they are not anagrams.
2. Then, we declare an array of 26 integers. We will use this array to keep track of the characters in both strings. Why 26? You may ask. It is because we have 26 letters in the alphabet. Each of the letter is represented by an index in the array. And the value stored in each index represents the count of the letter's occurrence in both words.
3. Next, we just loop through the strings and count the number of occurrences for each letter in both strings. For every letter in the first string, we'll subtract 1 from the count value stored in the index representing that letter. On the other hand, we'll add 1 for every letter in the second string. By doing this, we know that if both strings have the same letters, the final result will always be 0 because they cancel each other out through decrement and increment.
4. Lastly, we check the array of counts. If any index has a non-zero value, then the strings are not anagrams

We'll do an example by checking for "rat" and "art". First run of the loop, "r" count is -1 because it is in first string and "a" count is 1 because it is in second string. Second run, "a" count is now 0 because it appears in the first string so 1 - 1 is 0. Moreover, "r" count is also 0 because it appears in the second string -1 + 1 = 0. Last run, "t" count is 0 because it appears in both strings 1 - 1 = 0. Thus, we know "rat" and "art" are anagrams because the resulting array contains all 0s

Thanks for reading.If you have any suggestion please leave it in the comment below.

Converting integers less than 100 to words

This is a classic problem in which we're given an integer less than 100 and we have to output the words corresponding to the integer's value. For instance, if input is 90, then the output is "ninety" Moreover, if the input is -99, then the output is "incorrect input"

To solve this problem, we should have arrays of unique names such as "one" and "thirteen". The reason is that other integers' names are made up of just those unique names. For example, "nine" is unique name and "ninety" is unique name while "ninety nine" is just made up of "ninety" and "nine" The trick is to arrange our array such that it is easy to access the names. Here is one of the solutions to this problem:

#include
using namespace std;

string spellIntLessThanOneHundred(int number)
{
  if (number >= 100 || number < 0)
    return "Incorrect Input";
  
  string tensNames[] = {"", "ten", "twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety"};
  
  string lessThanTwentyNames[] = {"zero", "one", "two", "three", " four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};

  string result;

  //numbers >= 20
  if ((number / 10) > 1)
  {
    result = tensNames[number / 10];

    number %= 10;
    
    if (number > 0)
      result = result + " " + lessThanTwentyNames[number];
  }
  //numbers < 20
  else
    result = lessThanTwentyNames[number];

  return result;
}

Notice that we have two separate arrays of unique names, one for the numbers less than twenty and one for numbers that divisible by 10 such as 20 and 30. With this arrangement, it is very easy to access the name.

1. Our algorithm first checks for valid input which must be less than 100 and greater or equal 0.
2. Next, we look at the first digit. If dividing the input by 10 gives a number greater than one, the input must be greater or equal 20. By dividing the input by 10, we can extract the first digit out of the input. For example, dividing 21 by 10 gives 2 (implicit type conversion). We then use the first digit to access its name in the tensNames[] array. So, if the first digit is 2 then its name is twenty.
3. After that, we look at the last digit. By taking the remainder of the input divided by 10, we can extract the last number. If the last number is greater than 0, then we just need to get its name from the lessThanTwentyNames[] array. For example, 21 % 10 gives 1, so its name is one and the result now becomes "twenty one". However, if the remainder equals 0, we don't add anything to the result because that input is certainly divisible by 10 and has a unique name.
4. If dividing the input by 10 results in a number less than or equal to 1, then the input must have a unique name and less than 20. Thus, we just need to look for it in lessThanTwentyNames[] array

Printing "Hello World" to screen without using a single semicolon in C/C++

When I first encountered this question, I thought it was impossible. However, there are ways to do so. I don't know if the solutions are exploitation of c / c++. Anyway, here are the most common solutions:

#include<iostream>

int main()
{
    if (printf("Hello World \n")) { }
}

Or you can use the while loop like this:

#include<iostream>

int main()
{
    while (printf("Hello World") > 20) { }
}

If you don't think these codes will work, try them out. They are weird but work well in c / c++.

Notice: These don't work in Java. Not sure about other languages, so use them responsibly. After all, this is just for fun :)

Reverse a singly linked list

If we have a singly linked list like this 1->2->3->4, how can we reverse it so that it becomes 4->3->2->1? The algorithm is pretty simple. We just need to use two extra pointers and traverse the list once. Here is the algorithm in C++:

struct Node
{
  int data; //data
  Node* next; //pointer to next node in the list
};

Node* reverseLinkedList(Node *head)
{
  Node *next = NULL;
  Node *last = NULL;
  while (head != NULL)
  {
    next = head->next;
    head->next = last;
    last = head;
    head = next;
  }
  head = last;

  return head;
}

Our linked list is composed of different Nodes which have a data field and a next field. The next field is a pointer to the next node in the linked list.

Method reverseLinkedList() takes the head node of a list as its argument. It then creates a next pointer to store the next node in the list and a last pointer to store the last node we visit. After that, we traverse the list until our head pointer is null. For each node in the list, we change its next field to the node before it, and we set it as our last visited node. Finally, when we have traversed the whole list, we must set head to last pointer because last is now pointing at the first node in the list while head is pointing to null. After all, we just return head to give access to the beginning of the reversed list.

So, if our list was 1->2->3->4, the reversed list will be 4->3->2->1. As expected, this algorithm takes O(n) time complexity where n is the number of nodes in the list. It also takes O(2) space complexity because we need only 2 additional pointers for any given list.

Merging two sorted linked list

Question: given two sorted linked lists. Merge one to another, so that the result is a sorted linked list.

Let's take a simple case where we have two linked lists of integer such that list1 = 1->3->5->7 and list2 = 1->2->4. Our algorithm must take in these two lists and output either list1 or list2. the catch is that the result must be 1->1->2->3->4->5->7. The result contains all elements of both lists in sorted order.

Assume that we have class called Node such that a Node has a data and next field. data is used to hold an integer and next is the pointer to the next node in the list. Here is one of the solutions to this question written in C++

Node* MergeTwoSortedList(Node* list1, Node* list2)
{
    Node* temp = NULL; //temporary pointer
    Node* slow = NULL; //slow and fast pointer to travel list2
    Node* fast = NULL; 
    Node* head = list2; //keep track the head of the new list2
    
    //merge list1 to list2
    while(list1)
    {
        if(list1->data <= list2->data)
        {
          temp = list1;
          list1 = list1->next;
          temp->next = NULL;
          temp->next = list2;
          list2 = temp;
          head = list2; //update the head pointer
        }
        else
        {
          slow = list2;
          fast = list2->next;
          while(fast != NULL && fast->data <= list1->data)
          {
            slow = slow->next;
            fast = fast->next;
          }
          temp = list1;
          list1 = list1->next;
          temp->next = fast;
          slow->next = temp;
          list2 = temp;
        }
    }
    return head;
}

Explanation:

1. Loop through list1 and examine each node's value. If the current node's value in list1 is smaller or equal to the current node in list2, then we add it to list2 before the current node in list2. After that, we update pointers to the next node in list1 and list2.
2. However, if the current node in list1 is greater than the current node in list2, we'll traverse list2 using slow and fast pointer until our fast pointer is null or is at a node that is greater than the current node in list1. Next, we add the current node in list1 in front of the node pointed to by the slow pointer in list2. Finally, we update the current node in list2 to the node we just took from list1 and the current node in list1 to the next node in list1.
3. In the end, we return head which is the pointer to the head of the new list2 which has all elements from list1 and the old list2 in sorted order.