7 JavaScript Intermediate Level Arrays Interview Questions & Answers
Below is a list of our JavaScript Intermediate Level Arrays interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Can you implement a class SubRectangle?
This interview question concentrates on using JavaScript updates.
Your task is to implement a class SubRectangle. The constructor takes a 2-D matrix of size n X m and stores it. There are two methods in the class:- updateSubrectangle and getValue.
â— The updateSubrectangle updates a portion of the store 2-D matrix with value newValue of the subrectangle whose top-left corner is (row1, col1) and bottom-right corner is (row2, col2).
â— The method getValue returns the value at the provided location.
/*Example*/
passed matrix to the constructor-
[[1, 2, 1],
[4, 3, 4],
[3, 2, 1],
[1, 1, 1]]
the calls made:-
1. getValue(0, 2) // returns 1
2. updateSubRectangle(0, 0, 3, 2, 5) // the array becomes:-
[[5, 5, 5],
[5, 5, 5],
[5, 5, 5],
[5, 5, 5]]
3. getValue(0, 2) // returns 5
4. getValue(3, 1) // returns 5
5. updateSubRectangle(3, 0, 3, 2, 10) // the array becomes:-
[[5, 5, 5],
[5, 5, 5],
[5, 5, 5],
[10, 10, 10]]
6. getValue(3, 1) // returns 10
7. getValue(0, 2) // returns 5
class SubRectangle {
/**
* @param {number[][]} rectangle
*/
constructor(rectangle) {
// TODO
}
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @param {number} newValue
* @return {void}
*/
updateSubRectangle(row1, col1, row2, col2, newValue) {
// TODO
}
/**
* @param {number} row
* @param {number} col
* @return {number}
*/
getValue(row, col) {
// TODO
}
}
Solution:
Approach I (actual update):
After each update call, we will update the given matrix within the passed coordinates of the rectangle. While querying, we directly return the value at passed coordinates.
class SubRectangle {
/**
* @param {number[][]} rectangle
*/
constructor(rectangle) {
this.rectangle = rectangle
}
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @param {number} newValue
* @return {void}
*/
updateSubRectangle(row1, col1, row2, col2, newValue) {
for (let i = row1; i <= row2; i++) {
for (let j = col1; j <= col2; j++) {
this.rectangle[i][j] = newValue
}
}
}
/**
* @param {number} row
* @param {number} col
* @return {number}
*/
getValue(row, col) {
return this.rectangle[row][col]
}
}
Time complexity of updateSubRectangle- O(m * n)
Space complexity of updateSubRectangle- O(1)
Time complexity of getValue O(1)
Space complexity of getValue O(1)
Approach II (lazy update):
In this approach, we will not the rectangle matrix. Instead we will store the update history:- all the arguments passed to updateSubRectangle will be pushed to this.history as a new array. So the value of this.history after the two calls updateSubRectangle(0, 0, 3, 2, 5) and updateSubRectangle(3, 0, 3, 2, 10) of the example will be:-
this.history = [
[0, 0, 3, 2, 5],
[3, 0, 3, 2, 10]
]
Then during getValue, we will check the most recent update to the value at that coordinates. We will check from the last update to the earliest update i.e. loop in reverse direction on the history array. As soon as we find an update, we will return its value. But, if we don’t find any update in the history array, i.e. it is not updated by any operation, we return the original value this.rectangle[row][col].
class SubRectangle {
/**
* @param {number[][]} rectangle
*/
constructor(rectangle) {
this.rectangle = rectangle
this.history = new Array()
}
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @param {number} newValue
* @return {void}
*/
updateSubRectangle(row1, col1, row2, col2, newValue) {
this.history.push(Array.from(arguments))
}
/**
* @param {number} row
* @param {number} col
* @return {number}
*/
getValue(row, col) {
for (let i = this.history.length - 1; i >= 0; i--) {
const history = this.history[i]
const isUpdated =
history[0] <= row &&
row <= history[2] &&
history[1] <= col &&
col <= history[3]
if (isUpdated) {
return history[4]
}
}
return this.rectangle[row][col]
}
}
Time complexity of updateSubRectangle- O(1)
Space complexity of updateSubRectangle- O(1)
Time complexity of getValue- O(size of history)
Space complexity of getValue- O(1)
Written by S. Kumar on May 22nd, 2021
2. Using the minimum number of operations, move all balls to the ith box.
This interview question concentrates on using JavaScript operations within arrays.
There are n boxes. You are given binary string boxes of length n. If boxes[i] is “1â€, it means the ith box contains 1 ball, and If boxes[i] is “0â€, it means the ith box does not contain any ball.
In one operation, you can move a ball from one box to one of its adjacent boxes. So if the ball is currently in the ith box, you can move it to either (i + 1)st box or (i - 1)st box. Note that, after doing so, some boxes may have more than 1 ball.
Return an array result of size n, where result[i] is the minimum number of operations required to move all the balls to the ith box.
/*Example*/
boxes = "110"
expected output = [1, 1, 3]
0th box:- one operation needed to move the ball from the second box.
1st box:- one operation needed to move the ball from the first box.
2nd box:- two operations needed to move the ball from the first box, and one operation needed to move the ball from the second box.
boxes = "001011"
expected output = [11, 8, 5, 4, 3, 4]
Solution:
We can do it in two passes:
â— In the first pass, for the ith box, we calculate the number of operations required to move all the balls from boxes left of the ith box.
So after the first pass, the result array for example 2 will be:
[0, 0, 0, 1, 2, 4]
The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the left side of the ith box.
â— In the second pass, for the ith box, we calculate the number of operations required to move all the balls from boxes right of the ith box.
So after the first pass, the result array for example 2 will be:
[11, 8, 5, 4, 1, 0]
The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the right side of the ith box.
Adding both the result arrays will give us the answer.
/**
* @param {string} boxes
* @return {number[]}
*/
function minimumOperations(boxes) {
const n = boxes.length
const result = new Array(n).fill(0)
let ballsCount = 0
let operationsCount = 0
for (let i = 0; i < n; i++) {
result[i] += operationsCount
if (boxes[i] === "1") ballsCount++
operationsCount += ballsCount
}
ballsCount = 0
operationsCount = 0
for (let i = n - 1; i >= 0; i--) {
result[i] += operationsCount
if (boxes[i] === "1") ballsCount++
operationsCount += ballsCount
}
return result
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
3. Find the winner of an array game.
This question tests the developer's skills working with JavaScript arrays.
You are given an array arr of distinct integers. You are also given an integer k.
In each round, the first element arr[0] and the second element arr[1] play a game. The larger integer wins. It remains at position arr[0] and the smaller number is moved to the end of the array. The game ends when an integer wins k consecutive rounds.
/*Example*/
Given:- arr = [2, 1, 3, 5, 4, 6, 7] k = 2
Expected output: 5
Explanation:
Round arr winner win count
1 [2, 1, 3, 5, 4, 6, 7] 2 1
1 [2, 3, 5, 4, 6, 7, 1] 3 1
1 [3, 5, 4, 6, 7, 1, 2] 5 1
1 [5, 4, 6, 7, 1, 2, 3] 5 2
So four rounds are played and 5 wins 2 consecutive games.
Solution:
We will do one pass over the array. We will keep track of the current winner in the variable currWinner. Initially, we are assuming that the first element is the winner. And then we compare currWinner with other numbers in the array one by one. If the element is smaller than currWinner, we increment the variable winCount by 1 which shows the consecutive wins for currWinner. And if the element is greater than currWinner, it means we have a new winner. So update currWinner and start keeping track of its consecutive wins in the variable currWinner. As soon as we find currWinner with winCount equal to k, we break the loop and return currWinner.
There may be a case when we have iterated over all the elements and still didn’t find the currWinner (for example if k > n). For this, we need to focus on one observation. Let len be the length of the array and max be the maximum element in the array. It can be observed that after len - 1 rounds, always max will be the winner because it will be index 0 and no one will be able to beat it. Thus whatever the value of k is, we will return the maximum element in the array. currWinner will hold the maximum element after the loop finishes.
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
function findWinner(arr, k) {
let currWinner = arr[0]
let winCount = 0
for (let i = 1; i < arr.length; i++) {
if (arr[i] > currWinner) {
currWinner = arr[i]
winCount = 0
}
winCount++
if (winCount === k) break
}
return currWinner
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
4. Sort the arrays in colors.
This interview question shows the developer's ability to work with JavaScript partitioning and arrays.
You are given array nums of size n. The array contains only three integers: 0, 1, and 2 representing colors red, white, and blue respectively. Your task is to sort the array in place so that all the same integers are grouped together with colors in order red, white, and blue.
/*Example*/
Given nums = [2 ,0, 2, 1, 1, 0]
Expected output: [0 ,0, 1, 1, 2, 2]
Given nums = [2, 0, 1]
Expected output: [0, 1, 2]
Solution:
Approach I (counting colors):
In this approach, first, we will count each color in the array. After counting, we will overwrite those colors in the array nums starting with red(0), then white(0), and then blue(2).
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
function sortColors(nums) {
let counts = [0, 0, 0]
for (const num of nums) {
counts[num]++
}
for (let i = 0; i < nums.length; i++) {
if (counts[0] !== 0) nums[i] = 0
else if (counts[1] !== 0) nums[i] = 1
else nums[i] = 2
counts[nums[i]]--
}
}
Time complexity- O(n)
Space complexity- O(1)
Approach II (three-way partitioning):
This is a Dutch national flag problem. We have three types of numbers:- red, white, and blue. We want to group the similar ones and sort the groups in order: red, white, and blue. Let’s call these groups as redGroup, whiteGroup and blueGroup. We will have three-pointers (indices) to the nums array:-
1. redIdx:- it points to the right end of redGroup (exclusive)
2. whiteIdx:- it points to the right end of whiteGroup (exclusive)
3. blueIdx:- it points to the left end of blueGroup (exclusive)
For example, in the final sorted array: the pointers are:-
0 0 0 1 1 1 2 2 2
| | |
redIdx blueIdx whiteIdx
While the array is not completely sorted, these indexes convey the following information:-
1. redIdx:- points to where the next red color will be inserted
2. whiteIdx:- points to where the next white color will be inserted
3. blueIdx:- points to where the next blue color will be inserted
We will iterate over the array. In iteration, we check the color at index whiteIdx. If it is
1. red, we swap numbers at whiteIdx and redIdx, effectively inserting red color at redIdx,
2. white, we just increment whiteIdx by 1, effectively inserting white color at the previous value of whiteIdx,
3. blue, we swap numbers at whiteIdx and blueIdx, effectively inserting blue color at blueIdx.
Let’s take example of [2 ,0, 2, 1, 1, 0]
----------------------------------------------------------------------
Before iteration:-
2 0 2 1 1 0
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 1:-
0 0 2 1 1 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 2:-
0 0 2 1 1 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 3:-
0 0 2 1 1 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 4:-
0 0 1 1 2 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 5:-
0 0 1 1 2 2
| |
redIdx whiteIdx and blueIdx
----------------------------------------------------------------------
After iteration 5:-
0 0 1 1 2 2
| | |
redIdx blueIdx whiteIdx
----------------------------------------------------------------------
whiteIdx and blueIdx cross each other, so we break the loop. And the array is sorted!
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
function sortColors(nums) {
let redIdx = 0
let whiteIdx = 0
let blueIdx = nums.length - 1
while(whiteIdx <= blueIdx) {
if (nums[whiteIdx] === 0) {
swapIndex(nums, redIdx, whiteIdx)
redIdx++
whiteIdx++
} else if (nums[whiteIdx] === 1) {
whiteIdx++
} else {
swapIndex(nums, blueIdx, whiteIdx)
blueIdx--
}
}
}
function swapIndex(nums, idx1, idx2) {
const temp = nums[idx1]
nums[idx1] = nums[idx2]
nums[idx2] = temp
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021
5. What is the max height increase to keep the city skyline?
This question shows the developer's ability to work with JavaScript iteration and arrays.
You are in a beautiful city. The city contains many buildings in the 2-D plane. The city is represented by a 2-D matrix grid. grid[i][j] represents the height of the building at the location. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
Your task is to increase the heights of the buildings in such a way that the skylines of the city in all four directions remain the same as the skyline of the city represented by the original grid. Return the maximum total sum of the increased heights.
/*Example*/
Given grid = [
[3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0],
]
Expected output:- 35
Explanation:
The skyline of original from top or bottom:- [9, 4, 8, 7]
The skyline of original from left or right:- [8, 7, 9, 3]
The grid after increasing heights maximally without affecting skylines:-[
[8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3],
]
The total increase in heights = 35
Note that the skylines remain the same in all directions. If we increase the height of even one building even by one unit, the skylines will be changed.
Solution:
First of all, we will find the skylines of the city. To store the skylines, we use two arrays leftRightSkyline and topBottomSkyline for left-right and top-bottom skylines respectively. Then we iterate over the whole grid and find the skylines.
â— For each row, the max height in that row will be the skyline for that row when viewed from left or right.
â— For each column, the height in that row will be the skyline for that row when viewed from left or right.
[
[3, 0, 8, 4], -> max = 8 (these are row max or left-right skyline)
[2, 4, 5, 7], -> max = 7
[9, 2, 6, 3], -> max = 9
[0, 3, 1, 0], -> max = 3
| | | |
9 4 8 7
(these are column max or top-bottom skyline)
]
After finding the skylines, we try to find the change in heights for each building such that it does not change the skylines. For this, we iterate over the whole grid again. For each building, we know its row and column, and the max heights in those rows and columns.
Let’s say the building is at coordinate i and j with row max = row_max_i = leftRightSkyline[i] and column max column_max_j = topBottomSkyline[j]
Let originalHeight be the original height of the building, that is, originalHeight = grid[i][j]
Let finalHeight be the height of the building after the increase in height
Now assume row_max_i > column_max_j, and we change finalHeight to row_max_i. In this case, the skyline for that column will be changed. But if we change finalHeight to column_max_j, the skyline both in the row and the column will remain unchanged. Thus finalHeight will be the minimum of row_max_i and column_max_j or
finalHeight = minOf(row_max_i, column_max_j)
The increase in the height will be finalHeight - originalHeight. We will sum over these increases into ans and return it.
/**
* @param {number[][]} grid
* @return {number}
*/
function maxIncreaseKeepingSkyline(grid) {
const rowCount = grid.length
const columnCount = grid[0].length
const leftRightSkyline = new Array(rowCount).fill(0)
const topBottomSkyline = new Array(columnCount).fill(0)
for (let i = 0; i < rowCount; i++) {
for (let j = 0; j < columnCount; j++) {
leftRightSkyline[i] = Math.max(
leftRightSkyline[i],
grid[i][j],
)
topBottomSkyline[j] = Math.max(
topBottomSkyline[j],
grid[i][j],
)
}
}
let ans = 0
for (let i = 0; i < rowCount; i++) {
for (let j = 0; j < columnCount; j++) {
const originalHeight = grid[i][j]
const finalHeight = Math.min(
leftRightSkyline[i],
topBottomSkyline[j],
)
const increasedHeight = finalHeight - originalHeight
ans += increasedHeight
}
}
return ans
}
n = number of rows in grid
m = number of columns in grid
Time complexity- O(n * m)
Space complexity- O(n + m)
Written by S. Kumar on May 22nd, 2021
6. Return the number of battleships on the board.
This question focuses on JavaScript cells and iteration.
You are given n x m matrix board. Each cell is either “X†or empty “.â€. The “X†in a cell represents a part of a battleship. Your task is to return the number of battleships on the board.
A battleship can be either horizontal or vertical. In other words, a battleship of size k is either of shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column). There are no adjacent battleships i.e., at least one horizontal or vertical cell separates any two battleships.
/*Example*/
Given board = [
["X", ".", ".", "X"],
[".", ".", ".", "X"],
[".", ".", ".", "X"],
[".", ".", ".", "."],
]
Expected output: 2
Explanation: There are two battleships. One of size 1 at coordinates (0, 0). The other is of size 3 at coordinates (0, 3), (1, 3) and (2, 3).
Solution:
Since there are no two adjacent battleships, the top and right cells to the top-left of a battleship are empty. For example,
[
["X", ".", ".", "."],
[".", "X", "X", "."],
[".", ".", ".", "X"],
[".", ".", ".", "X"],
]
In the above example, the top-left coordinate of the ship {(1, 1), (1, 2)} is (1, 1). The top and right cells to this cell are (0, 1) and (1, 0) both of which are empty. This will be true for all battleships.
We will iterate over the whole matrix and will find such top-left cells of the battleships. The count of these cells will be equal to the number of battleships present on the board.
/**
* @param {character[][]} board
* @return {number}
*/
function countBattleships(board) {
const rowsCount = board.length
const colsCount = board[0].length
let count = 0
for (let i = 0; i < rowsCount; i++) {
for (let j = 0; j < colsCount; j++) {
if (board[i][j] === ".") continue
if (i > 0 && board[i - 1][j] === "X") continue
if (j > 0 && board[i][j - 1] === "X") continue
// (i, j) is the top-left part of the ship
count++
}
}
return count
}
n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021
7. Return a list of coordinates in a spiral matrix.
This question shows the developer's ability to work with JavaScript loops.
You are given four integers: rows, cols, rStart, cStart. Imagine a grid of size rows x cols. You are currently at cell (rStart, cStart) (0-indexed) facing east. You walk in a clockwise spiral shape to visit every position of the grid. Whenever you move outside the grid, you continue to walk outside the grid and will return to the grid boundary later. Eventually, all the cells of grids are visited. Your task is to return a list of coordinates of the cells of the grids in the order they were visited.
/*Example*/
Given: rows = 3 cols = 3 rStart = 0 cStart = 1
Expected output: [[0, 1], [0, 2], [1, 2], [1, 1], [1, 0], [0, 0], [2, 2], [2, 1], [2, 0]]
Explanation:
Legends: > (east) < (west) ^ (north) v (south)
> > > > > > v
6 1 > 2 v
^ v v
5 < 4 < 3 v
v
9 < 8 < 7 < v
/*After visiting the 6th cell, we go out of the grid, we continue walking in the spiral form outside the grid, and re-enters the grid at cell (2, 2).*/
Solution:
We will take the walk iteratively starting from the cell (rStart, cStart). If the current cell is not bounded (it does not belong to the grid), we will skip to the next cell. If it is bounded, then we will push it the result array res.
It can be seen that the path is as follows:
move east 1 step, turn right
move south 1 step, turn right
move west 2 step, turn right
move north 2 step, turn right
move east 3 step, turn right
move south 3 step, turn right
move west 4 step, turn right
move north 4 step, turn right
… and so on.
So the number of steps in the directions while taking a walk is a sequence: 1, 1, 2, 2, 3, 3, 4. Let this be stored in the variable stepsCount. We have a variable direction to store our current direction of the walk with values 0, 1, 2 or 3 for east, south, west or north respectively. The value of stepsCount changes when the new direction is either east or west (0 or 3).
We start our loop with current coordinates rStart and cStart stored in variables x and y. In each iteration, we change coordinates of the current position using the function changeCell. This function takes the coordinates of current position and the current direction.
â— If direction is 0 (east), we move position right, that is, (x, y) -> (x, y + 1)
â— If direction is 1 (south), we move position bottom, that is, (x, y) -> (x + 1, y)
â— If direction is 2 (west), we move position left, that is, (x, y) -> (x, y - 1)
â— If direction is 3 (north), we move position top, that is, (x, y) -> (x - 1, y)
Then we check if the newly changed coordinates belong to the grid or not using the function isBounded. In the end, we change direction and increase stepsCount, if required.
/**
* @param {number} rows
* @param {number} cols
* @param {number} rStart
* @param {number} cStart
* @return {number[][]}
*/
function spiralMatrix(rows, cols, rStart, cStart) {
const res = []
const totalCells = rows * cols
let direction = 0
let stepsCount = 1
let x = rStart
let y = cStart
res.push([x, y])
while(res.length < totalCells) {
for (let i = 0; i < stepsCount; i++) {
[x, y] = changeCell(x, y, direction)
if (isBounded(x, y, rows, cols)) {
res.push([x, y])
}
}
direction = (direction + 1) % 4
if (direction % 2 === 0) stepsCount++
}
return res
}
function changeCell(x, y, direction) {
if (direction === 0) return [x, y + 1]
if (direction === 1) return [x + 1, y]
if (direction === 2) return [x, y - 1]
if (direction === 3) return [x - 1, y]
}
function isBounded(x, y, rows, cols) {
return (
x >= 0 &&
x < rows &&
y >= 0 &&
y < cols
)
}
Time complexity- O((max(rows, cols))2)
Auxiliary Space complexity- O(1)
Total Space complexity- O(rows * cols)
Written by S. Kumar on May 22nd, 2021