Interview question: Find the most used character using a Hashtable

In my last post I discussed how to find the most used character in an ASCII string using only a INT[]. An interviewer would mostly ask you about that scenario to test your knowledge of programming to see if you knew of how to implement the algorithm using the least amount of memory. In this example, the immediate resources are not the biggest concern and we want to be able to handle Unicode characters. The interviewer is wanting to test your knowledge of the types the framework provides to you. 

The method for doing this will be similar to the previous post accept we're using a Hashtable this time. An advantage of this will be that we won't have to determine the number of keys before we start parsing the string as the Hashtable object will handle this automatically. This may mean that more memory will be wasted and that there maybe more overhead needed when a resizing of the table is needed. But, this isn't the concern right now. Just make sure to mention this and that a way to keep the resizing overhead to a minimum would be to indicate the initial number of keys needed when initializing the Hashtable. In this example we're only worried about English alphabetical characters, so a size of 32 would be large enough (*why 32 was used i explained below).

Overall the algorithm will function the same as the FindMostUsedUnicodeChar() method we wrote in the last post. We're going to have 2 FOR loops with the first parsing the string and counting the number of instances for each character. The second loop will go through the Hashtable to determine the character that had the most instances. In the end, the character with the most hits will be returned.

/**
 * Determines the first alphabetical character that has the most instances within the string.
 * The search is case insensitive.
 * @param givenString The string.
 * @return The character or null if none are found.
 * @throws IllegalArgumentException
 */
public static char FindMostUsedUnicodeChar(final String givenString)
      throws IllegalArgumentException {

    // Verifying the string is not NULL.
    if (givenString == null)
      throw new IllegalArgumentException("The parameter givenString cannot be null.");

    // At this time we're only concerned with the letters A-Z., the 26 letter in the English
    // alphabet, for this example. This is why we're initializing the hashtable to a size of 32;
    // the smallest 2^Nth value that's greater than 26.
    Hashtable<Character, Integer> hashtable = new Hashtable<Character, Integer>(32);

    // Looping through the string and counting the number of times a alphabetical character
    // appears. We're doing a case insensitive search.
    final char givenChars[] = givenString.toUpperCase().toCharArray();

    for (int index = 0; index < givenChars.length; index++) {
      final char key = givenChars[index];
      if (key < 'A' || 'Z' < key)  continue;

      int charCount = 1;
      if (hashtable.containsKey(key)) charCount = hashtable.get(key) + 1;
      hashtable.put(key, charCount);
    }

    // Finding the first letter to have the highest use count by the order that they appeared.
    char mostUsedChar = '0';
    int highestCharCount = 0;
    for (int index = 0; index < givenChars.length; index++) {
      char key = givenChars[index];
      if (key < 'A' || 'Z' < key) continue;

      int currentCount = hashtable.get(key);
      if (highestCharCount < currentCount) {
        mostUsedChar = key;
        highestCharCount = currentCount;
      }
    }

    // Done
    return mostUsedChar;
}

As before, you may want to ask what behavior is expected if there are an equal number of 'a' and 'c' characters. This implementation, like the last, will return the first letter found in the string with the highest count. You will need to know that this algorithm is O(n) because the FOR loops are in series, not nest like you would see with O(n^2) solutions. Some test cases you will want to consider are how to handle a null string, an empty string, and a string with no alphabetical characters.

Is there anything you would change in this method? Have any tips from interviews you've had in which this question was asked? If so, share your experience and leave a comment!

Full source code here.

* I used 32 instead of 26 because memory is allocated in blocks of 2^Nth. It's the smallest 2^Nth value that's large enough to contain the 26 keys.

Interview question: Finding the most used ASCII character

This question has come up in a few interviews and there's 2 ways to solve it depending on if you're using ASCII or Unicode character sets. This first post is to example how to solve the problem for the ASCII character set. 

The problems goes like this: You're to make a method that will return the most used character in a given string. The character set of the string is ASCII. How would you go about doing this? 

Hearing this you know you'll have some type of FOR loop happening here as you move through the string counting each character. Now how do you plan on storing the count of each character? The easiest way would be to use some type of hash table where the character is the key and the value is the number of times the character has been found. 

Great! You've got a plan. But, there should be something nagging you. Why did they emphasizing that the string consists of ASCII characters? This is a hint on how they want you to solve the problem and they're testing your knowledge a bit here. In most languages a CHAR can be used as a INT and vice versa. This means that you can create a simple hash table using an INT[] where the position in the array, or “key”, you want is determined by the value of the current CHAR. So if you're currently looking an A character, whose INT value is 65, you would increment the 65th element of the INT[]. Any time you found the letter D, you would increment the 68th element of the INT[]. And so on. 

About here is where you should ask if this algorithm should be case sensitive or not. Either way, it shouldn't affect your implementation too much, but it just shows you're thinking ahead for test cases. You should also know how the language you're using handles the creation of INT[]. Does it zero out all the elements on creation? Or do you have to do this manually? Knowing things like this shows your mastery of the language. 

So this is what the algorithm looks like. Just to make is a little more interesting I made it case insensitive and only counting alphabetical characters. 

public static char FindMostUsedAsciiChar(final String givenString)
      throws IllegalArgumentException {

   // Verifying the string is not NULL.
   if (givenString == null) {
       throw new IllegalArgumentException("The parameter givenString cannot be null.");
   }

   // To reduce the size of the int[] that's storing the count information I'm only making it
   // 26 elements in size. This means that any time the key char is used that its value must
   // be adjusted accordingly.
   int charHash[] = new int[26];

   // Looping through the string and counting the number of times a alphabetical character
   // appears. We're doing a case insensitive search.
   final char givenChars[] = givenString.toUpperCase().toCharArray();
   for (int index = 0; index < givenChars.length; index++) {
      int key = givenChars[index];
      if (65 <= key && key <= 90) {
         charHash[key - 65]++;
      }
   }

   // Finding the first letter to have the highest use count by the order that they appeared.
   int mostUsedChar = 0;
   int highestCharCount = 0;
   for (int index = 0; index < givenChars.length; index++) {
      int key = givenChars[index];
      if (key < 65 || 90 < key) {
         continue;
      }
      int currentCount = charHash[key - 65];
      if (highestCharCount < currentCount) {
         mostUsedChar = key;
         highestCharCount = currentCount;
      }
   }

   // Done
   return (char)mostUsedChar;
}

Things to possibly take into consideration is how the most used character is found in this scenario. I'm returning the first largest value. So if the string used was “caca” with both 'a' and 'c' having the same number of instances, 'c' would be returned as the character with the most hits. Your interviewer may want the results returned by alphabetical order, meaning the result would be 'a' instead of 'c'. But generally speaking, they don't care. They're just seeing if you understand how your algorithm works. If this comes up it's for the purpose of how to test the method and the expected results in this scenario. 

Another question that may come up, or is at least good to bring to up to once again show your knowledge, is what Big O notation this performs at. Although we are accessing the INT[] in O(1) fashion, the bottle necks are the FOR loops. We do have 2 of them, but since they're not nested our algorithm is O(n). 

In the next post I'll explain how to implement this using the Unicode character set. 

Would you have written this any differently? Are there any possible optimizations that you would have added?

Full source code here.

Interview question: Binary search in a sorted array

One of the questions that will usually come during an interview is related to Big O notation. This is a way for them to see how well you understand the efficiency or resource consideration of a particular algorithm. More importantly, they may be looking to see if you know how to implement a method using different variations of Big O. In this post I’ll show you 2 ways that you can implement a binary search on a sorted array.

Usually the question is presented to you like this; you’re given a sorted array of integers, what’s the best way to find if an integer is within the array? Simply starting from one end and moving towards the other incrementally is O(n). This would be fine except the hint that the array was sorted. Being sorted indicates that you use the divide and conquer method of binary search.

Now you have to decide whether to implement it by recursion or by iteration. Both have their advantages and disadvantages (which you should discuss with the interviewer). Personally, being taught C++ as my first real programming language (sorry BASIC!), I try to avoid recursion when possible. I know that in managed languages like Java and C# stack overflows are not as much of a worry as they are with native languages, but I generally feel that loops are a much safer way of programming. Other things to keep in mind when deciding which method to use are readability and maintenance. I’m sure you can write hotshot code for either one, but will you be able to easily understand what you wrote a year from now when you’re debugging a problem involving your chosen method? Or when someone else takes over your code because you’ve moved onto another project\team? Keep these in mind when deciding upon a method.

With either method the core logic is going to be the same for this task. First we will want to find the lowest and highest array indices. These will be used to determine the initial search location. If the location is not the value we’re searching for, we adjust the minimum or maximum index allowing for the first division of the data. The code will look something like this.

// Checking if the location is valueToFind
currentPos = (maxPos + minPos) / 2;
if (sortedArray[currentPos] == valueToFind)
   return true;

// Calculating a new minPos or maxPos values
if (sortedArray[currentPos] < valueToFind)
   minPos = currentPos + 1;
else
   maxPos = currentPos - 1;

If we’re using iteration we’ll want to keep looping through the core logic while the minimum index is less than or equal to that of the maximum or the value is found.

// Searching for valueToFind in sortedArray
while (minPos <= maxPos) {

   // Checking if the location is valueToFind
   currentPos = (maxPos + minPos) / 2;
   if (sortedArray[currentPos] == valueToFind)
      return true;

   // Calculating a new minPos or maxPos values
   if (sortedArray[currentPos] < valueToFind)
      minPos = currentPos + 1;
   else
      maxPos = currentPos - 1;
}
        
// valueToFind is not in the array
return false;

Similarly with the recursion, the method will continue calling itself until either the value is found or the maximum index is less than that of the minimum.

// Check if the location is valueToFind
int currentPos = (minPos + maxPos) / 2;
if (sortedArray[currentPos] == valueToFind)
   return true;

// Calculating a new value for minPos or maxPos
if (sortedArray[currentPos] < valueToFind)
   minPos = currentPos + 1;
else
   maxPos = currentPos - 1;

// If the new maxPos is less than minPos, we know valueToFind is not in the array
if (maxPos < minPos)
   return false;

// Trying new location since valueToFind was not in the current one
boolean findResult = RecursionMethod(valueToFind, sortedArray, minPos, maxPos);
return findResult;

All right, let’s talk test cases. We should come up with some scenarios that verify the logic in-depth. We’ll want to search for values that are less\greater than the lowest\highest value in the array, search for values not in the array but would fall between values that do exist, and interesting array sizes. Interesting array sizes would include a null array, a single element because the minPos and maxPos values are the same, and an array with 5 elements because it‘s the simplest tree with an odd number of elements that require both the minPos and maxPos to change to find at least 1 value, and finally 6 elements because it’s the simplest tree with an even number of leafs that require both minPos and maxPos to change to find at least 1 value in the array.

And there you have it! A binary search algorithm on a sorted array with interesting test cases. Understand this and when it comes up in an interview you’ll breeze through it.

You can view the full source code here.

Interview question: Palindrome detecting algorithm

This is the beginning of what I plan on making a series of posts about programming questions I’ve had during interviews over the years. This first one shows how to create an algorithm for detecting if a string contains a palindrome.

You’re first question maybe, “What’s a palindrome?” and being that you’re in the software engineering field and not an English major makes that a valid question. A quick explanation of a palindrome is that it’s a word that is spelled the same forwards and backwards like the names Bob or Hannah.

Ok. So that seems easy enough. Why would a software company ask you this question in an interview? Well, what if I told you that the string “race car” is also a palindrome. Now knowing this, you can probably begin to see the number of test cases rise and amount of logic needed to correctly handle each one. This is why it’s a good interview question. It shows them how you think and if you can correctly test your own logic.

Let’s begin by defining what this algorithm needs to be able to do.

• Ignore non-alpha characters
• Case insensitive character comparison
• A single letter word like ‘I’ are a valid palindrome
• A string that has no characters to compare is not a valid palindrome
• Return true if the string contains a palindrome and false otherwise

Ok. Let’s get started. How do we go about doing this?

First off, we need to compare the characters in the order of first compares to last, second compares to second to last, and so on. If any of the characters don’t match while doing this, we know it’s not a palindrome. This can be done by having 2 indexes, one that starts from the beginning of the string and another from the end of the string. Each time the indexes point to a character that match, the front index is incremented and the back index is decremented. We loop through this process until the indexes meet or until we find a pair that doesn’t match.

We’re not going to worry too much about comparing the case of the characters. Most languages have a method to either force a character to upper\lower case or to do a non-case sensitive comparison. But you should bring this up to your interviewer just so he\she knows it's on your mind.

boolean IsPalindrome(String givenWord) {

   // Setting the initial index values
   int frontIndex = 0;
   int backIndex = givenWord.length() - 1;
        
   // Moving though all the characters checking for a palindrome
   while (frontIndex <= backIndex) {
            
      // Obtaining characters to compare
      char frontChar = Character.toLowerCase(givenWord.charAt(frontIndex));
      char backChar = Character.toLowerCase(givenWord.charAt(backIndex));
            
      // Do the characters match?
      if (frontChar != backChar)
         return false;
            
      // Preparing for next loop pass
      frontIndex++;
      backIndex--;
   }
  
   //  The word is a palindrome
   return true;
}

Now we have a solution that solves for our sanity cases of Bob and Hannah, but what about “race car”? What we need to do is verify that the front index and the back index point to alphabetical characters before doing the comparison. If an index does not point to a letter, we must increment\decrement it until it does. The thing we have to be aware of while doing this is that we don’t want our indexes to pass each other.

// Trying to find an alpha character by moving left to right
while (!Character.isLetter(givenWord.charAt(frontIndex)) && frontIndex < backIndex)
   frontIndex++;
char frontChar = Character.toLowerCase(givenWord.charAt(frontIndex));

// Trying to find an alpha character by moving right to left
while (!Character.isLetter(givenWord.charAt(backIndex)) && frontIndex < backIndex)
   backIndex--;
char backChar = Character.toLowerCase(givenWord.charAt(backIndex));

Things are looking pretty good, but what about the test case for a string that contains no letters like “1337”? Your first reaction would probably be to add a check after setting frontChar to verify that it’s a letter and return false if it isn’t. This is partially correct. The problem is that a string like “a7a” is a valid palindrome and adding this check alone would not allow this test case to pass. What is also needed is a way to indicate that no other alphabetical pairs have matched before returning false. Adding a Boolean value that is initially set to false can do this. When a matching character pair has been found, this value will be set to true. This way we will only return false if we come across a frontChar that is not a letter and no previous matches have been found.

// Checking to make sure the character is an alpha character and if it isn't, checking to 
// see if a previous match has been found already.
if (!Character.isLetter(frontChar) && !matchFound)
   return false;

...

// Preparing for next loop pass
frontIndex++;
backIndex--;
matchFound = true;

Great! All we need now is to put everything together, add a string is NULL and\or 0 length check at the beginning of the method, and you have a working palindrome algorithm detector.

You can view the full algorithm code here.