Exploring Arrays: Exercises and Interview Questions

If you are not familiar with some advanced operations with arrays I have wrote an article covering some of the common structures and theory about arrays (or vectors).

In this article, let’s face some common questions that use arrays to solve it. Of course, they are for learning purposes and most often are not good for production environment.

I highly recommend you to try to solve this questions by yourself and then compare your findings with my implementations, also, I would be happy if you share your implementations with us in the comment section 🙂

I will go over the first question, and then, I will propose additional questions in the end of this article, and a separate page with solutions.

Question 1: Implement an algorithm that checks if a string has only unique characters.

To solve this problem you have to loop all chars and keep track of them. The question is, how to keep track? Well, you can use an Array! But, it’s extremely important to know if this string is written in ASCII or UNICODE.

Why? ASCII has 256 chars, so you can easily set bounds to your problem and use a simple array, check this out:

public boolean IsAllUnique(String str)
{
   if (str.length() > 256) return false; // See Note 1 bellow
   boolean[] check = new boolean[256];
   for (int I = 0; I < str.length(); I++)
   {
      int chr = str.charAt(I);        // convert char to int
      if (check[chr]) return false;   // found, so not all unique
      check[chr] = true;   // unique so far
   }
   return true;            // all unique!
}

Note 1: If an ASCII string has more then 256 chars, it’s not possible to be all unique, one has to be duplicated. So you can set a end condition before we need to loop. This solution uses 1 loop so in the worst case we have O(n) and space O(1) because we use a fixed vector of 256.

What about Unicode?

It’s tricky to set bounds to Unicode strings, so the best way is to use a HashTable and populate it. If you are not sure about the encode type, you better use this approach. If you are in an interview, ASK your interviewer about the encode.

public boolean IsAllUniqueUnicode(String str)
{
   HashMap map = new HashMap<int, boolean>();
   for (int I=0; I<str.length(); I++)
   {
      int chr = str.charAt(I);
      if (map.get(chr)) return false;   // found, return false
      map.put(chr, true);               // no, so add to map
   }
   return true;
}

You have now a version that works both for ASCII and Unicode. The odds of using this approach however is performance. You still have 1 loop, but you also have the search time of your HashMap, usually log n, so, we can guess that our performance now drops to O(n+logn). Not a big trouble if you want to keep it working.

Question 2: Write a function that reverse a char array. Example: “Steak” becomes “kaetS”.

This is a classic one! Simple, very simple, let’s write what we have right in our minds:

public char[] reverse(char[] input)
{
   char[] output = new char[input.length()];
   for(int I=0; I<input.length(); I++)
   {
      output[input.length() - 1 - I] = input[I];
   }
   return output;
}

Congratulations, we wrote a O(n) performance function that reverse the char array, but eating the DOUBLE of the space: O(2n). Now I ask you, how would you improve this?

A: Do swaps in place instead of copying to a new array.

public char[] reverse(char[] input)
{
   for(int I=0; I<input.length() / 2; I++)
   {
      char temp = input[I];
      input[I] = input[input.length() - 1 - I];
      input[input.length() - 1 - I] = temp;
   }
   return output;
}

Note on line 3 that we only need now to go half way of the length, because we are taking the first element and swapping with the last element. Then, the second element and swapping with the element prior to the last, and so and so, until we reach the middle. Since we are going half way, the processing time drops 50%: O(n/2), and since we are not duplicating our array anymore, our working space is now only O(n).

Tip: There are ways to make a swap without a TEMP var, but we will discuss this later, since it not concerns arrays. I call this: Blowing Hanoi Tower!

Some exercises to play along

As I suggested, try to make this exercises by yourself, try hard, burn your brain! Then, come back and check the “Resolution Page” (that I will publish later). Some of the questions I borrowed from the book “Cracking the Coding Interview” from Gayle Laakmann McDowell, an excellent reading.

Q3: Write an algorithm that checks if a string is a permutation from another string. Ex: Does “cause” is a permutation of “sauce”? Return true or false.

Q4: Given a game board represented by a N by N matrix with integers on each slot, one of the game commands is to rotate this board by 90 degrees. Write a function that perform this rotation in place.

Q5: You have a Rubik’s Cube. Write a function that perform a rotation in one of the rows. You also have to define the Cube’s data structure, and keep track of its colors.
Note: you don’t need to solve the cube, just rotate CW or CCW.

Good luck!

This entry was posted in Vectors & Arrays. Bookmark the permalink.