Interview Coding Problems: Strings and Arrays

Solving an Interview Coding Problem

This post is part of the Interview Coding Problems series. Throughout the posts, I am following the same guide for solving problems. Inspired by John Sonmez’s Pluralsight Course and Gayle Laakmann’s Cracking the Coding Interview: 150 Programming Questions and Solutions, I put together five steps to address every coding problem.

Question

Write an algorithm to detect if all the characters in a string are unique.

One of the most common problems out there especially for junior developers.

Guide

The Environment

Before we dive in and start to think about how to handle the question we must define the environment. We are practicing for technical interviews, so we have to keep two things in mind:

  1. Communication. Talk your thoughts even if you have not yet reached an optimal solution. If you are struggling a good interviewer may give you a hint. I find it useful to do that as I practice even if no one listens
  2. Practice on paper or whiteboard. The chances are that you are not going to write code on IDE through the interview. I know it’s not easy and that’s why you should practice it.

Now, let’s dive in.

Step 1: Understand the question.

The first thing you want to do is to read through the question as many times as it takes to understand it. You wouldn’t want to start solving the wrong problem.

In many occasions, the questions are not very clear. You can ask the interviewer for clarifications and assumptions that have to be made in order to solve it. Sometimes asking the right questions is part of the solution.

On this particular problem, some good questions are:

  • What kind of characters does a string contain?  -ASCII characters
  • Is an uppercase letter a different character from a lowercase?  -Yes
  • Are spaces considered characters? -No

Keep in mind that questions like this might affect on a big scale our code.

Step 2: Design a solution

Most of the times the design won’t just pop out in your mind. A good beginning towards the right design would be to start with simple examples. Try to reach the solution using a small string or a simple number as input. Pay attention to the steps that you take and more often than not you’ll be able to see a pattern that you can implement with code.

Now, let’s work with an example.

“Apprentice Developer”

We can easily say that the string’s letters are not unique. However, we should distinguish the steps until we find a pattern.

Simplest Solution

Iterating through the string, we try to find if a particular letter exists more than once. Without using any other structures, we could start with the first character and compare it to every other character. Then do the same for the second and every character after it. Although no extra space is required, the time complexity is O(n^2).

Even if the solution is not the most efficient, it’s an excellent opportunity to speak your mind and say why and what would you like to improve.

Finding A Better Solution

This part, I believe, is the key to solving a coding question and an excellent opportunity to distinguish yourself from other candidates. Thankfully is something we can practice by solving more problems.

Now, it’s time to use the assumptions that we made when we started. All characters are ASCII, which means there are 256 possible characters inside the string. When the input has a known range and that range is not too big we can use an algorithm like Counting Sort. Although in our case we don’t need to sort the characters we can use the same approach to check for duplicates.

Similar to Counting Sort, we need an array with a size of 256 (All the possible values of a character). Instead of using an array of integers we will use an array of booleans initialized to false because all we need to check is if there is the same character twice. As we iterate through the string, we populate the array with true values on every character.

Now, after we review and test our solution, we are ready to start writing something.

Step 3: Pseudocode

The first step is the pseudocode. Many young developers skip this part, but I think it’s an essential step. It makes writing the actual code much easier.

Input String.
Array[256] of booleans.
Initialize all values of the Array to false.
For every character in string:
    Populate the Array with trues.
    If a duplicate is found the string's characters are not unique.
After the iteration if no duplicate is found then string's characters are unique.

Step 4: Code

Using the pseudocode we just wrote we can produce actual code. Remember when you are practicing you write all these on paper.

public class StringUtilities {

	public static boolean isStringCharsUnique(String s){
		
		boolean[] array = new boolean[256];
		
		for(int i = 0; i < s.length(); i++){
			int val = s.charAt(i);
			if(array[val] && val != ' ')
				return false;
			array[val] = true;
		}
		return true;
	}
}

As we write the code on paper we have to be much more careful than writing on IDE. You’ve figured out a good implementation, wrote the pseudocode, and you are confident you can write the code. That’s good, but you are not finished yet. The interviewer wants to see not only how you think but also how you write code. Finding the solution is the first step but writing good, readable and maintainable code is equally important.

Points to consider:
• Good variable and method naming. The code should speak for itself
• Write a comment only when your code does something that naming can’t explain.

 

Step 5: Testing

Last but not least, we have to write test cases for our code. Unit testing is something that you should always do, let alone during an interview.

The good news is that this step is more or else the same on every problem. You write some simple tests and corner cases for the input and the code.

public class isStringCharsUniqueTest {

	@Test
	public void testFalse() {

		String s = "How areyou?";
		boolean b = StringUtilities.isStringCharsUnique(s);
		
		assertEquals(b, false);
	}
	
	@Test
	public void testTrue() {

		String s = "How areyOu?";
		boolean b = StringUtilities.isStringCharsUnique(s);
		
		assertEquals(b, true);
	}
	
	@Test
	public void testSpace(){
		
		String s = "How are yOu?";
		boolean b = StringUtilities.isStringCharsUnique(s);
		
		assertEquals(b, true);
	}
	
	@Test
	public void testEmpty() {

		String s = "";
		boolean b = StringUtilities.isStringCharsUnique(s);
		
		assertEquals(b, true);
	}
	
	@Test
	public void testOne() {

		String s = "H";
		boolean b = StringUtilities.isStringCharsUnique(s);
		
		assertEquals(b, true);
	}
}

Conclusion

Finishing off your practice it’s time to write your code on an actual IDE and test it. Try to find the points that you missed and improve them. On the next interview coding problem, you’ll do even better.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.