Cracking the Coding Interview Chapter 1 Java Soltuions - Arrays and Strings
My personal solutions to the infamous "Cracking the Coding Interview" questions. These are my interpretations of the solutions, and to be honest, you won't get much out of them unless you buy the book and try solving them yourself.
Here I'm solving these problems as exercises to keep myself sharp. When you go rouge and start looking for contracting work you're just going to have to deal with answering these questions. Matter of fact, when it boils down to it, professional contractors are professional interviewers. Master this skill and it will open a lot of doors for you.
Chapter 1
01. Determine if a string has all unique characters (GitHub)
This is a tough one to start the book out with IMO. Honestly if you don't know the int array trick, you're going to struggle with it. I've seen people give this to young candidates and they easily give up. Much easier to solve if the usage of a hashmap isn't immediatly taken off the table.
| public Boolean checkDupesBinary(String str) { | |
| char[] charArray = str.toCharArray(); | |
| Boolean[] charSpot = new Boolean[256]; | |
| for (char theChar : charArray ) { | |
| int charInt = (int) theChar; | |
| if (charSpot[charInt]) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } |
02. Implement a function to reverse a string (GitHub)
Fairly straight forward, think of the steps first. Start at the begining and swap start and end, move into the array and do the same for its opposite in the arry. If you wanted to be fancy you could swap the values in place without using a temp var, but I don't see the point in that for this exercise. See others package
03. Given two strings, determine if they are premutations of each other (GitHub)
If you could easily solve a problem with a HashMap, but are not allowed to use structures, then an int or boolean array might help solve the issue.. I was thinking I'd need two int arrays then count them, however the book suggests incrementing with one, then decrementing with another, great idea.
| private Boolean isPermutationBinary(String a, String b) { | |
| if (a.length() != b.length()) return false; | |
| char[] charA = a.toCharArray(); | |
| char[] charB = b.toCharArray(); | |
| int[] counter = new int[256]; | |
| for (int i = 0; i < charA.length; i++) { | |
| int asciiNum = (int) charA[i]; | |
| counter[asciiNum]++; | |
| } | |
| //great little trick to avoid comparing two arrays, decrement the first | |
| for (int i = 0; i < charB.length; i++) { | |
| int asciiNum = (int) charB[i]; | |
| counter[asciiNum]--; | |
| if ( counter[asciiNum] < 0 ) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } |
04. Replace all spaces in a string with %02 (GitHub)
This solution was fairly straight forward. Count up the spaces, allocat a new char array of the correct size, and fill in as you go. Use extra pointer to keep track of return strings position.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
private Boolean isPermutationBinary(String a, String b) {
if (a.length() != b.length()) return false;
char[] charA = a.toCharArray();
char[] charB = b.toCharArray();
int[] counter = new int[256];
for (int i = 0; i < charA.length; i++) {
int asciiNum = (int) charA[i];
counter[asciiNum]++;
}
//great little trick to avoid comparing two arrays, decrement the first
for (int i = 0; i < charB.length; i++) {
int asciiNum = (int) charB[i];
counter[asciiNum]--;
if ( counter[asciiNum] < 0 ) {
return false;
}
}
return true;
}
| private Boolean isPermutationBinary(String a, String b) { | |
| if (a.length() != b.length()) return false; | |
| char[] charA = a.toCharArray(); | |
| char[] charB = b.toCharArray(); | |
| int[] counter = new int[256]; | |
| for (int i = 0; i < charA.length; i++) { | |
| int asciiNum = (int) charA[i]; | |
| counter[asciiNum]++; | |
| } | |
| //great little trick to avoid comparing two arrays, decrement the first | |
| for (int i = 0; i < charB.length; i++) { | |
| int asciiNum = (int) charB[i]; | |
| counter[asciiNum]--; | |
| if ( counter[asciiNum] < 0 ) { | |
| return false; | |
| } | |
| } | |
| return true; | |
| } |
05. Basic string compression (GitHub)
Sort of a funny question, there's probably a better way to encapulate iterating over the string twice.
06. Rotate an NxN matrix 90 degress clockwise (GitHub)
Don't even get me started on this one... Actually wait, get me started on it. It's a tough question and I've given it it's own explaination.
07. Zero out a row and column with zeros (GitHub)
This would be a much better question to start out with, try it before the matrix rotation.
08. Is the string a rotation of the other (GitHub)
This is a sneaky one, technically really simple once it finally comes to you. A great example of why you just need to keep trying everything little thing in your disposal before giving up. What if I put this here, rotated that, joined them together? Ahhh....