Essential Coding Interview Questions with Javascript (Part II)

Nick Maslov
Sep 5, 2018 · 9 min read

(two-dimensional array, tree search problem)

It is very important to get acquainted with various data structures and how to apply them correctly. This article presents the most common interview questions and popular problems with arrays, two-dimensional arrays, queues, stacks, binary search trees, graphs, etc. To be comfortable with this article, you should be familiar with these data structures and have some basic knowledge of Javascript. Examples of these problems I got in Python tutorials, but I wanted to solve them using JavaScript because JS is one of the most popular programming languages and is required for any web developer.

Links to other problems: Part I, Part III


#6 Assign Numbers in Minesweeper

Remember the old Minesweeper ? We play on a square board and we have to click on the board on the cells which do not have a mine. And obviously we don’t know where mines are. If a cell where a mine is present is clicked then we lose, else we are still in the game.

In this problem we are going to create a minesweeper board. Output should be a two dimensional array, where bombs will have value -1, and other cells will be filled with 0 and +1 to cell for each bomb, it has border with.

The input is bombs — array of coordinates, number of rows , and number of columns

Examples:

Input : 
bombs = [[2,3],[2,1]]
numRows = 4
numCols = 4
Output :
[0, 0, 0, 0]
[1, 1, 2, 1]
[1, -1, 2, -1]
[1, 1, 2, 1]
Input :
bombs = [[2,3],[2,1],[6,6]]
numRows = 10
numCols = 10
Output :
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 2, 1, 1, 0, 0, 0, 0, 0]
[1, -1, 2, -1, 1, 0, 0, 0, 0, 0]
[1, 1, 2, 1, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 1, -1, 1, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

To solve this problem we have to initialize a two-dimensional array with numbers of rows and number of columns from the input, as our field. Then give to our bombs with given coordinates (x, y) value -1 and all cells around (x+/- 1, y+/- 1) will have increment +1. Make sure that you do not get out of the board and don’t cause the error. Our map is ready. Just return the field.

Solution:

function mineSweeper(bombs, numRows, numCols) {
let field = [];
for (let i = 0; i < numRows; i++) {
field[i] = [];
for (let j = 0; j < numCols; j++) {
field[i][j] = 0;
}
}
for (let bomb of bombs) {
let rowB = bomb[0];
let colB = bomb[1];
field[rowB][colB] = -1;
for (let i = rowB - 1; i <= rowB + 1; i++) {
for (let j = colB - 1; j <= colB + 1; j++) {
if (
0 <= i &&
i < numRows &&
0 <= j &&
j < numCols &&
field[i][j] !== -1
) {
field[i][j] += 1;
}
}
}
}
return field;
}

#7 Find Where to Expand in Minesweeper

Here is another problem with minesweeper. You should check the previous problem if you are not familiar with the game. In minesweeper, when you click on a cell that is not a bomb, all surrounding cells that do not have bombs will be shown.

The problem is to find where to expand exactly when you click on a correct cell, and express it by changing all 0 values to -2 in this area. So, in your function you should modify given array and return new one with first click changes like in examples. If clicked not 0 value, nothing change.

Examples:

Input : 
field =
[[0, 0, 0, 0],
[1, 1, 1, 0],
[1, -1, 1, 0],
[1, 1, 1, 0]]
clickX = 0
clickY = 1
Output :
[[-2, -2, -2, -2],
[ 1, 1, 1, -2],
[ 1, -1, 1, -2],
[ 1, 1, 1, -2]]
Input :
field =
[[ 0, 1, 1, 1],
[ 0, 1, -1, 1],
[ 1, 2, 1, 1],
[-1, 1, 0, 0]]
clickX = 3
clickY = 2
Output :
[[ 0, 1, 1, 1],
[ 0, 1, -1, 1],
[ 1, 2, 1, 1],
[-1, 1, -2, -2]]

When a user clicks on a first cell (x, y), we need to find all zero cells connected to the first cell. The first zero is directly connected to the nine cells (x +/- 1, y +/- 1), and each of this nine cells is connected to other cells. This structure is a graph, where you trying to find all the zero cells connected to the first cell, which is the first node in this graph. There are two simple ways to solve a search problem in a graph: Depth-First Search and Breadth-First Search. Which do we want to use? Let’s think about the worst case scenario when all cells are 0, and you need to traverse the entire array.

Let’s first think about how Depth-First Search will work. Suppose that user clicks the cell (0, 0). Depending on the order of direction that you check in your algorithm you can get spider pattern or snake pattern like on the picture behind. Either way, we need to store the positions of all the zero cells in this array. Extra space complexity or auxiliary space would be O(n*m), where n is the number of rows in given field, and m is the number of columns. The time complexity will be also O(n*m) because we need to traverse the entire array.
Let’s now think about how Breadth-First Search will work. Suppose that user clicks the cell (2, 2). You see the pattern on the picture which expands outward from the first cell. The entire outer edges in total will have about O(2(n+m)) cells. Thus, auxiliary space complexity will be O(n+m), which is better than O(n*m), and the time complexity for this algorithm is O(n*m) because we still need to consider the entire array.
Thus, these search algorithms have the same time complexity, but the auxiliary space or the extra space complexity of Breadth-First Search is better than the auxiliary space of Depth-First Search. So let’s use Breadth-First Search instead of Depth-First Search for a search in our solution.

Let’s now think about how Breadth-First search would work. The first step will initialize a queue to keep track of which positions to check later. If clicked cell is 0, we add it to our queue, turning its value to -2, than check all surrounding cells (x +/- 1, y +/- 1), and if they equal 0, add them to our queue, turn them to -2, and remove our cell (x, y) from the queue. We are going to repeat the same to the next position in the queue with while loop till the time when our queue is empty. Our changes on the board are done.

Solution:

function click(field, clickX, clickY) {
let numRows = field.length,
numCols = field[0].length,
toCheck = [];
if (field[clickX][clickY] === 0) {
toCheck.push([clickX, clickY]);
}
while (toCheck.length) {
let [x, y] = toCheck.shift();
for (let i = x - 1; i <= x + 1; i++) {
for (let j = y - 1; j <= y + 1; j++) {
if (
0 <= i &&
i < numRows &&
0 <= j &&
j < numCols &&
field[i][j] === 0
) {
field[i][j] = -2;
toCheck.push([i, j]);
}
}
}
}
return field;
}

#8 Rotating 2D Array

You’re given a two-dimensional array which is square, a number of columns is equal to a number of rows. Write a function, that rotates this array by 90 degrees clockwise direction.

Examples:

Input : 
arr = [[1,2,3],
[4,5,6],
[7,8,9]]
Output :
[[7,4,1],
[8,5,2],
[9,6,3]]

To solve this problem we need to known where the new coordinates should be for each item after rotating by 90 degrees. Item in the top left corner goes to the top right corner, the second item ends up the last item in the second row… Is there a simple equation to express these movements? In our example you can see that the new row index is simply equal to the old column index. Top side in a given array corresponds to the right side in a new array, row becomes a column. So, new column index equal previous row index, and the new row index we can get from old column, where old column index was from 0 to n-1, where n is number of rows, becomes new row index from n-1 to 0 order. So, new row index is equal n-1minus previous column index.

Here is out of place solution, look at rotateOutOfPlace function. Create a new two dimensional array of the same shape and the same size as the original one by copying the original array or initializing new one with the same size. Then copy each item of original array to the new location in the new array. In the end, return a reference to the newly created two dimensional array.

Very common interview question is to solve this problem without using any extra space, modifying existing array and auxiliary space is O(1), look at rotateInPlace function. Item in the top left corner goes to the top right corner, item in the top left corner will go to the right bottom corner…

When we shuffle elements around an array, we need to track the values ​​in these positions so that we do not lose them. An easy way to do this is to create an array of four elements. We can move these values ​​in two steps. First go through these elements and save the values ​​in a temporary array. Then repeat these steps, copying the items from the previous position again. The center does not move when we rotate this array 90 degrees. Unlike the previous solution, we can not simply go through the whole array in rows using this method. If we do this, each element will be rotated four times, moving everything back to its original position.

If the array has an even number of rows and columns, then we just need to iterate through sub array, whose size is exactly one quarter of the given array. What if the given array has an odd number of rows and columns? We won’t be able to slice array to four equivalent sections anymore. Instead, you need to consider a rectangle shaped region. This way you will be able to cover the whole given two-dimensional array except for the value in the center, which we can ignore, it doesn’t move anywhere when array rotate by 90 degrees. We can consider the even case and the odd case separately. Another way is to simply iterate the row index from zero to floor of array length over two minus one. The floor operation selects the largest integer value that is less or equal to the given value. The column index should go from zero to ceil of array length over two minus one. Ceil operation is similar to floor, but exactly the opposite, it would return the smallest integer value that is greater than or equal to the given value. The idea is for each square cycle, we swap the elements involved with the corresponding cell in the sub array from top to left, left to bottom, bottom to right and from right to top one at a time storing them in temporary array with four elements and then we swap our four sub arrays in the entire array.

Solution:

function rotateOutOfPlace(arr) {
let rotatedArr = arr.map(a => a.slice());
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
let newI = j,
newJ = arr.length - 1 - i;
rotatedArr[newI][newJ] = arr[i][j];
}
}
return rotatedArr;
}
function rotateInPlace(arr) {
for (let i = 0; i < Math.ceil(arr.length / 2); i++) {
for (let j = 0; j < Math.floor(arr.length / 2); j++) {
let tmp = [-1, -1, -1, -1],
curI = i,
curJ = j;
for (let k = 0; k <= 3; k++) {
tmp[k] = arr[curI][curJ];
let t = curI;
curI = curJ;
curJ = arr.length - 1 - t;
}
for (let k = 0; k <= 3; k++) {
arr[curI][curJ] = tmp[(k + 3) % 4];
let t = curI;
curI = curJ;
curJ = arr.length - 1 - t;
}
}
}
return arr;
}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade