Cracking the Coding Interview: 4 JavaScript Solutions

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.

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.

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;
}
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;
}
  1. We can use a regular string instead of a StringBuilder.
  2. We can iterate over strings just like we iterate over arrays and use the bracket notation to access the property at the ith index.
  3. 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.

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;
}

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.

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;
}

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.

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.

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;
}
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jon McEwen

Jon McEwen

One part coder, one part mystic. I write mostly about data analytics, project management, and content creation.