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!

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 :)