Essential Coding Interview Questions with Javascript (Part I)

Nick Maslov
Sep 5, 2018 · 5 min read

(Array and String Problems)

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 II, Part III


#1 Most Frequently Occurring Item in an Array

Given an array, find the most frequent element in it. If there are multiple elements that appear maximum number of times, print any one of them.

Examples:

Input : arr = [1, 3, 2, 1, 4, 1]
Output : 1
1 appears three times in array which
is maximum frequency.
Input : arr[] = [10, 20, 10, 20, 30, 20, 20]
Output : 20

The naive approach is to run two loops. The time complexity of this approach is O(n²). An efficient solution, which is requiring to know on interviews, is to use hashing and time complexity O(n).
We create a hash table and store elements and their frequency counts as key-value pairs. At the same time, we dynamically store the maximum repeating element and its frequency in individual variables, so when the loop through the array is completed, we already have the answer.

Solution:

function mostFrequent(arr) {
let maxCount = -1,
maxItem = null,
count = {};
for (let i of arr) {
if (!count.hasOwnProperty(i)) count[i] = 1;
else count[i] += 1;
if (count[i] > maxCount) {
maxCount = count[i];
maxItem = i;
}
}
return maxItem;
}

#2 Common Elements in Two Sorted Arrays

Given two arrays sorted in ascending order, print all intersections - common elements in these arrays.

Examples:

Input :
a = [1, 5, 10, 20, 40, 80]
b = [6, 7, 20, 80, 100]
Output: 20, 80
Input :
a = [1, 5, 5]
b = [3, 4, 5, 5, 10]
Output: 5, 5

First, we have to initialize an empty array for the result, and two pointers which point to first elements at given two arrays. Pointer with smaller number will move to the next element each step. If numbers are equal, we are adding this item to our result and move pointers to next items. The time complexity will be O(max(n, m)), where is n is a number of items in first array, m is a number of items in second.

Solution:

function commonElements(a, b) {
let p1 = 0,
p2 = 0,
result = [];
while (p1 < a.length && p2 < b.length) {
if (a[p1] === b[p2]) {
result.push(a[p1]);
p1 += 1;
p2 += 1;
} else if (a[p1] > b[p2]) {
p2 += 1;
} else {
p1 += 1;
}
}
return result;
}

#3 Is One Array a Rotation of Another?

Determine if two arrays are a rotated version of each other, return boolean, assume that no duplicates.

Examples:

Input : 
a = [1, 2, 3, 4, 5, 6, 7]
b = [5, 6, 7, 1, 2, 3, 4]
Output : true
Input :
a = [1, 2, 3, 4, 5, 6, 7]
b = [5, 6, 7, 8, 9, 10]
Output : false

To solve this problem first of all what we need is to check if array A and B has the same length. If they don’t, rotation impossible. After that let’s pick any element from array A and find the same in B. If you can’t find it, there is no rotation. If you do find it, check if the elements after that the same, and after, and so on. Any different items - return false. When you get last item, without returning false, than you should return true.
Following algorithm has time complexity O(N).

Solution:

function isRotaion(a, b) {
if (a.length !== b.length) return false;
let key = a[0],
keyI = -1;
for (let i = 0; i < b.length; i++) {
if (b[i] === key) keyI = i;
}
if (keyI === -1) return false;
for (let i = 0; i < a.length; i++) {
let j = (keyI + i) % a.length;
if (a[i] !== b[j]) return false;
}
return true;
}

#4 Non-Repeating Character

Write a function to find the first non-repeated character in a string.

Examples:

Input : str = 'abacddbec'
Output : 'e'
Input : str = 'hello world'
Output : 'h'

Here’s a linear solution O(n) to the non-repeating character problem. We need to iterate through the entire string with the fo loop, counting a number of times each character appears using a hash table. Then iterate through the string again and return character whose count is only one. If there is no such a character, return null.

Solution:

function nonRepeating(str) {
let charCount = {};
for (let c of str) {
if (charCount.hasOwnProperty(c)) charCount[c] += 1;
else charCount[c] = 1;
}
for (let c of str) {
if (charCount[c] === 1) return c;
}
return null;
}

#5 One Edit Away Strings

Given two string s1 and s2, find if s1 can be converted to s2 with exactly one edit. An edit between two strings is one of the following changes:

  1. Insert a character
  2. Remove a character
  3. Replace a character

Return true or false.

Examples:

Input :
s1 = 'hello'
s2 = 'hell0'
Output: true
Input :
s1 = 'hello'
s2 = 'hell'
Output: true

We have to check 4 cases.
First, if the length between two strings differs by more than 1 character, we return false, because we have to edit several times.
Secondly, in case two strings are of equal length, we need to compare each character in the strings, if there are several differences, return false, if less, true.
In case, if s1 is longer than s2, we have to count difference, starting from, and when difference will be equal 1, just change index to index + 1 of longer s1 string. If by the last character of s2, the difference didn’t change return true, else false.
The last case, when we need to add character to s1, we can just use the previous method, but compare s2 with s1.
This problem has a lot of problems in it, so the best way to organize code is to divide it to subfunctions.

Solution:

function isOneAway(s1, s2) {
if (s1.length - s2.length > 1 || s2.length - s1.length > 1) return false;
else if (s1.length === s2.length) return isOneAwaySameLength(s1, s2);
else if (s1.length > s2.length) return isOneAwayDiffLength(s1, s2);
else return isOneAwayDiffLength(s2, s1);
function isOneAwaySameLength(s1, s2) {
let countDiff = 0;
for (let i = 0; i < s1.length; i++) {
if (s1[i] !== s2[i]) {
countDiff += 1;
if (countDiff > 1) return false;
}
}
return true;
}
function isOneAwayDiffLength(s1, s2) {
let i = 0,
countDiff = 0;
while (i < s2.length) {
if (s1[i + countDiff] === s2[i]) {
i += 1;
} else {
countDiff += 1;
if (countDiff > 1) return false;
}
}
return true;
}
}

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