Cracking The Coding Interview Together – Problem 1: Is Unique?

I hope you are as excited as us for the first post in the series, where we explore the problems from the book Cracking The Coding Interview by Gayle Laakmann. Let me give you an idea about the format of this and upcoming posts. We will explore it in the context of the actual interview. I would also assume that you have basic understanding of Data Structures and simple algorithms. As part of this we will go through the following:

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem Statement

Implement an algorithm to determine if a string has all unique characters. What if you cannot use any additional data structures?

Analyse Problem Statement

This problem statement is straight forward and super easy to understand. But in case if you couldn't, let me break it down for you. I am sure you know what a string is, it is basically an alphanumeric set of characters, for example: hello , I am 23 years old , my name is Alex etc.

You have to write an algorithm to check if a string has all unique characters or not. For example hello has two l and hence is not completely unique. But sky has all unique characters. So your algorithm would have to take a string and would have to return either true or false based on if it has all unique characters or not.

You have to also make sure that you don't use any additional data structures, apart from the original string. But I am starting to have some questions, do you? If not, then think right now, this is the time to think about the problem statement and gather questions that you may have. In the next section I will share with you my set of questions and you can compare yours with mine.

Questions for the Interviewer

Don't feel bad that you couldn't understand the problem statement completely and that you have questions in your mind. Speak your mind and clarify your doubts. Don't think that it is a bad thing, it is in fact mostly a good thing and there are no dumb questions.

Here is a list of my questions

1. Do I have to first write an algorithm that can check unique characters where I could use additional data structure and then try without or should I directly jump to the algorithm without using additional data structure?
2. When you said that I can't use additional data structures - do you mean that arrays are also out of limits or just hash map or hash sets?
3. Should the format be an algorithm or actual code?

If you have any other questions, pat your back and please feel free to write in the comments and we can discuss those as well.

Say you got the following answer to your questions:

1. It is up to you, if you know a solution with additional data structures you can describe it to us and then quickly move to the next part.
   1. Best choice is to describe your solution in the form of the code quickly and then move to the next part
2. Yes, you can't use additional data structures which means you can't use arrays along with other data structures as hash map and hash set
3. Format should be actual working code to the best of your abilities

Think about the Solution

This is the time where you keep your mind calm and try to understand how you would go about solving the problem. Ideally you must form your thoughts appropriately for a minute or two before you start speaking out loud.

While thinking in your mind if you encounter any doubts or questions, you could still ask your interviewer. And don't panic, it is normal to have questions at this stage as well.

when we are allowed to use additional data structures

In this case, we could simply use hash sets to store all the unique elements in it. We basically go through all the characters of the string and push them one by one in the hash set. Hash set has the property that it won't allow the duplicates, which means once you are through with all the characters hash set would contain only unique characters. In the end you could compare the count of characters in string vs in the hash set and if they are the same then it means string has all unique characters otherwise false.

when we are not allowed to use additional data structures

In this case, we can't use arrays, hash map, hash set or any other data structure. This means that we must strictly not use any other storage. We can try to compare each element with all the other elements and see if we have a match. In that case we could break early and return false as we encountered duplicates.

NOTE: Usually you would be assessing trade offs between extra storage and the time complexity. In the first case you are using additional storage but you have significantly reduced the overall time

Explain your Solution

Now you have formulated solutions and have a pretty good understanding of how to drive this. This is your time to shine, take the lead and explain how you would solve the first problem and then what changes when we can't use additional data structures.

Don't forget to explain the time and space complexities as well with each of your solution.

Solution with additional Data Structure

public static boolean hasAllUniqueChars(String str) {
        // Early exit: if string length exceeds total possible unique chars (for ASCII)
        if (str.length() > 128) return false;
        
        HashSet<Character> seen = new HashSet<>();
        
        for (char c : str.toCharArray()) {
            if (seen.contains(c)) {
                return false; // Duplicate found
            }
            seen.add(c);
        }
        
        return true; // All characters unique
}

Time complexity: you are basically going over each element of the string and if the string has n characters then the time complexity is O(n)

Space complexity: would be just the same as you would be storing at most n characters in the extra storage i.e. O(n)

Solution without additional Data Structure

public static boolean stringContainsUniqueCharacters(String str) {
    if(str == null) return true; // return early, you could also ask about this specific case - when string is null
    for(int counter1 = 0; counter1 < str.length(); counter1++) {
      for(int counter2 = counter1+1; counter2 < str.length(); counter2++) {
        if(str.charAt(counter1) == str.charAt(counter2)) return false;
      }
    }
    return true; // all combinations were matched but no element was same
}

Time complexity: you are basically going over each element of the string and comparing it with all the other elements it would be O(n^2)

Space complexity: would be constant as we are not using any extra storage i.e. O(1)

Final Thought

I hope you enjoyed the first session of Cracking The Coding Interview — Together.

We’d love to know how you liked it! Please give us a thumbs up or share your thoughts in the comments. It helps us improve and create even better content for our readers.

See you in the next one — until then, happy coding! 👋