Cracking the Coding Interview: 4 JavaScript Solutions
Cracking the Coding Interview is a canonical book for preparing for software engineering interviews. It’s a fantastic resource with one downfall, the solutions are written in Java.
¯\_(ツ)_/¯
Java isn’t exactly the new hotness, and learning it can cause major headaches. But fear not — this story will be the first in a series in which I hack together JavaScript solutions for Cracking the Coding Interview problems.
Let’s start with the basics, Strings and Arrays.
1. Check Permutation
Description:
Given two strings, write a method to decide if one is a permutation of the other.
My Solution:
I had done similar things over at CodeSignal, so this problem was very familiar to me. After ten or fifteen minutes of deliberation, I realized array.sort()was the key. I didn’t even need to intermittently get up and pace my living room.
Notice that we writelet sortOne = string1.split('').sort().join('');, and we are able to chain string methods and array methods here because those methods return arrays and strings.
function permutationCheck(string1,string2) {
let sortOne = string1.split('').sort().join('');
let sortTwo = string2.split('').sort().join('');
if(sortOne === sortTwo) {
return true;
} else {
return false;
}
}Official Solution:
My solution was essentially the same as the official solution. Notice that here we write a sort method and then a permutation method that uses the previously defined sort method.
String sort(string s) {
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}
boolean permutation(String s, String t) {
if(s.length() != t.length()) {
return false;
}
return sort(s).equals(sort(t)):
}
}2. String Compression
Description:
Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaawould becomea2b1c5a3. If the compressed string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters.
My Solution:
This was a fairly straightforward problem. I knew I could solve it by creating an object with key-value pairs that corresponded to the string characters and their counts. What I was uncomfortable with was how many loops I stacked on top of each other.
function compression(string) {
let compressed = "";
let map = {
}
string.split("").forEach((e,i) => {
map[e] = 0;
})
string.split("").forEach((e,i) => {
map[e] += 1;
})
for (var element in map) {
compressed += element+map[element];
}
if (compressed.length > string.length) {
return string;
} else {
return compressed;
}
}Official Solution:
Gasp! After looking at the official answer, I realized my solution was close but missed a key point in the description. Go back and see if you can find where I botched things.
CCI provides three solutions to this problem, each with progressively better performance. The solutions are considerably more verbose than mine. For the sake of brevity, let’s look at the middle solution. Also, hello Java syntax.
String compress(String str) {
StringBuilder compressed = new StringBuilder();
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++;
/* If next character is different than current, append this char to result. */
if(i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressed.append(str.charAt(i));
compressed.append(countConsecutive);
countConsecutive = 0;
}
}
return compressed.length() < str.length() ? compressed.toString() : str;
}I find this solution to be quite clever, mostly because it always increments countConsecutiveon each iteration but sets it back to zero if the next character is different than the current character. Touché, CCI, touché.
Let’s write it in JavaScript for good measure.
function compression(string) {
let compressed = "";
let countConsecutive = 0;for (i = 0; i < string.length; i++) {
countConsecutive++;
if (i + 1 >= string.length || string[i] != string[i + 1]) {
compressed += string[i];
compressed += countConsecutive;
countConsecutive = 0;
}
}
return compressed.length < string.length ? compressed : string;
}There are a couple of takeaways from our JavaScript version.
- We can use a regular string instead of a StringBuilder.
- We can iterate over strings just like we iterate over arrays and use the bracket notation to access the property at the ith index.
- Our ternary at the end is the same in Java as it is in JavaScript.
3. Check String Rotation
Description:
Assume you have a method isSubstringwhich checks if one word is a substring of another. Give two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g., “waterbottle” is a rotation of “erbottlewat”).
My Solution:
I really found the description of this problem to be perplexing. To start, “substring” and “rotation” were not immediately familiar terms. Yes, they are both pretty self-explanatory, but I still had to do some groundwork before their meanings were clear. What really confused me, though, was to what extent the problem wanted my solution to depend on isSubstring. In my impatience, I decided to scrap the method altogether because I recognized a brute-force solution right away.
Here’s what I did:
function checkRotation(one, two) {
one = one.split('');
two = two.split('');
if (one.join('') === two.join('')) {
return false
} else {
for (i = 0; i < one.length - 1; i++) {
temp = two.pop();
two.unshift(temp);
if (one.join('') === two.join('')) {
return true
}
}
}
return false;
}All I’m doing here is checking each possible rotation of string two against string one. Then I return true if there’s a match between them. The code is convoluted by conditionals and array methods, though. There are two things here that I think are noteworthy. 1) Join methods do not manipulate the original array. 2) I had to convert each array into a string before checking equality. Had they been arrays, even if their contents matched, both in value and position, their object references would be different. Thus the equality check would never return true.
Official Solution:
I’m a little bitter about this one. The official solution is clever but not a huge feat of logical prowess. I think if the description had been more explicit, my solution may have been closer to being correct.
Here’s how they did things:
boolean isRotation(string s1, String s2) {
int len = s1.length();
/*Check that s1 and s2 are equal length and not empty */
if(len == s2.length() && len > 0) {
/* Concatenate s1 and s1 within new buffer */
String s1s1 = s1 + s1;
return isSubstring(s1s1, s2);
}
return false;
}The trick here is that if you concatenate the first string with itself, and if the second string is a rotation of the first string, the second string will always be found somewhere in that concatenation.
For example, if s1 is “Bob” and s2 is “bBo”, our substring method would check “bBo” against “BobBob”. And Lo and behold! “bBo” is right there in the middle of “BobBob”. How clever.
4. Zero Matrix
Description:
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to zero.
My solution:
This problem was similar to problems I had done in the past. In order to solve a basic matrix problem, you need to know how to nest loops, which isn’t all that difficult. Still, I always seem to confuse my index references at some point while typing out the code.
My real concern with this problem was that my solution’s runtime had ballooned out of control. It’s not possible to iterate through a matrix with anything better than a runtime of O(n²). I knew, best case, that’s what my runtime would be. Things got complicated, though, because retrieving the positions of the zeros was one thing (an O(n²) operation) but going back through the matrix to wipe the rows and columns required more nested loops. What happens when you loop then loop and loop once more, two times?
Here’s what I did:
function matrix(m) {
//Create arrays to hold row and column positions
var rows = [];
var columns = [];
for (r = 0; r < m.length; r++) {
for (c = 0; c < m[r].length; c++) {
if (m[r][c] === 0) {
rows.push(r);
columns.push(c);
}
}
} //Loop through row array to replace with zeros
rows.forEach((e, l) => {
for (i = 0; i < m.length; i++) {
for (j = 0; j < m[i].length; j++) {
if (i === e) {
m[i][j] = 0;
}
}
}
}) //Loop through column array to replace with zeros
columns.forEach((e, l) => {
for (i = 0; i < m.length; i++) {
for (j = 0; j < m[i].length; j++) {
if (j === e) {
m[i][j] = 0;
}
}
}
})//Return our mutated matrix
return m;
}Official Solution:
Well, sometimes you get lucky. The official solution is essentially the same as my solution, with some minor differences. Most importantly, we’re still looping a lot in this solution.
In hindsight, I think both my solution and CTCI’s solution are O(n²). The stacked nested loops are constant, so we can drop them. What do you think? What’s the runtime of both of these algorithms? Let me know in the comments.
void setZeros(int[][] matrix) {
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[matrix[0].length];//Store the row and column index with value 0
for(int = 0; i < matrix.length; i++) {
for (int j = 0; j <matrix[0].lenght; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
column[j]=true;
}
}
}
//Nullify Rows
for (int i = 0; i < row.length; i++) {
if (row[i]) nullifyRow(matrix, i);
}
//Nullify Columns
for (int j = 0; j < column.length; j++) {
if (column[j]) nullifyColumn(matrix, j);
}void nullifyRow(int[][] matrix, int row) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[row][j] = 0;
}
}void nullifyColumn(int[][] matrix, int col) {
for (int i = 0; i < matrix[0].length; i++) {
matrix[i][col] = 0;
}
}
}Cheers!
