9 JavaScript Intermediate Level Implementation Interview Questions & Answers
Below is a list of our JavaScript Intermediate Level Implementation 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. Find the letter combinations of a phone number.
This question focuses on finding combinations using strings with JavaScript.
You are given a string of digits consisting of digits 2-9 (both inclusive). Your task is to return all possible letter combinations that can be formed by pressing these digits on a keypad mobile. A mapping from digits is given below:
1 2 abc 3 def
4 ghi 5 jkl 6 mno
7 pqrs 8 tuv 9 wxyz
/*Example*/
Given digits = “23â€
Expected output:- ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Constraints
0 <= digits <= 4
“2†<= digits[i] <= “9â€
Solution:
Approach I (recursive):
We will create all the combinations recursively. We will create our helper recursive function combination. This function adds a new combination to the result. The function takes the following arguments:-
1. digits: The given string digits.
2. result: The resulting array where to which every combination will be stored.
3. KEYS: The mapping of digits to letters.
4. idx: The index of given string digits up to which we will compute a combination of digits.
5. prefix: The prefix of the combination which we have seen up to index idx - 1 of the given string digits.
When the idx is equal to the length of given string digits, it means we have found one possible combination. For given digits = “23â€, the recursion stack is (result array and KEYS mapping are omitted in the function calls):
|combination(“23â€, 0, “â€)
| |digit = “2â€
| |letters = “abcâ€
| |loop on letters “abcâ€
| | |combination(“23â€, 1, “aâ€)
| | | |digit = “3â€
| | | |letters = “defâ€
| | | |loop on letters “defâ€
| | | | |combination(“23â€, 2, “adâ€)
| | | | | |2 == digits.length // true
| | | | | |push “ad†to result
| | | | | |return
| | | | |combination(“23â€, 2, “aeâ€)
| | | | | |2 == digits.length // true
| | | | | |push “ae†to result
| | | | | |return
| | | | | combination(“23â€, 2, “afâ€)
| | | | | |2 == digits.length // true
| | | | | |push “af†to result
| | | | | |return
| | | // similar loop on letters “b†and “câ€
/**
* @param {string} digits
* @return {string[]}
*/
function letterCombinations(moves) {
if (digits.length === 0) return []
const result = []
const KEYS = [
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
]
combination(digits, result, KEYS, 0, “â€)
return result
}
function combination(digits, result, KEYS, idx, prefix) {
if (idx === digits.length) {
result.push(prefix)
return
}
const digit = digits[idx]
const letters = KEYS[digit]
for (const letter of letters) {
combination(
digits,
result,
KEYS,
idx + 1,
prefix + letter,
)
}
}
n = length of the digit string
Time complexity- O(n * 4n)
Space complexity- O(n)
Approach II (iterative):
We will loop over each digit in string digits. For each digit, we will find the corresponding letters using the map KEYS. We will have a final result array. For each digit, we will have a new array newResult. This array will store the letter combination up to the current digit. For each letter for the corresponding digit, we iterate over the previously stored prefixes in the result array. For each such prefix, we push the new combination prefix + letter to newResult. After finding the new combinations up to the current digit, we reassign the result to newResult so that we can iterate over new prefixes for the next digit. After the digits loop, we return the result.
/**
* @param {string} digits
* @return {string[]}
*/
function letterCombinations(moves) {
if (digits.length === 0) return []
const KEYS = [
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
]
let result = [""]
for (let digit of digits) {
const newResult = []
digit = parseInt(digit)
const letters = KEYS[digit]
for (const letter of letters) {
for (const prefix of result) {
newResult.push(prefix + letter)
}
}
result = newResult
}
return result
}
n = length of the digit string
Time complexity- O(n * 4n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
2. How do you multiply strings without a leading-zero product?
This question focuses on JavaScript iteration.
You are given two non-negative integers num1 and num2 in the form of strings. Your task is to find the product of num1 and num2 and return it in the form of a string. You can neither use in-built like BigIntger nor convert the numbers from strings to integers. The product must not have any leading zeros.
/*Example*/
Given num1 = “123†num2 = “45â€
Expected output:- “5535â€
Solution:
To solve this problem, we need to see how multiplication is done on pen-paper (focus on underlined digits). Let resultString be the resulting number in the form of string.
num1 = 1 2 3 index i of num1 (here i = 1)
num2 = 4 5 index j of num2 (here j = 0)
_______________________
1 5
1 0
0 5
1 2
0 8 index (i + j) and (i + j + 1)
0 4 of resultString (here 1 & 2)
______________________________
0 5 5 3 5
0 1 2 3 4 indices of resultString
It can be observed that the product of digits at indices i and j of num1 and num2 respectively is added to the indices (i + j) and (i + j + 1) of resultString. So we will iterate over each digit of the two numbers starting from unit places (that is we loop in reverse order) and find the product of the digits and store them at the appropriate location. To store the product of the digits, we use a result array. It can be observed that when two integers with digits count m and n are multiplied, the product has at most m + n number of digits.
We use the parseInt function to convert a digit into number form which is in string form initially. Thus parseInt(“2â€) = 2.
After looping over all the digits, the result may have leading zeros. So we loop over the result array and put undefined in place of leading zeroes. Then we use Array.prototype.join method to join the result to form a string which will be our desired result. One thing to note is that the Array.prototype.join method does not take undefined values into account. Thus:
[8, 1].join(“â€) = “81â€
[undefined, 5, 5, 3, 5].join(“â€) = “5535â€
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
function multiply(num1, num2) {
const m = num1.length
const n = num2.length
const result = new Array(m + n).fill(0)
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const digit1 = parseInt(num1[i])
const digit2 = parseInt(num2[j])
const idx1 = i + j
const idx2 = i + j + 1
const mul = digit1 * digit2
const sum = mul + result[idx2]
result[idx1] += Math.floor(sum / 10)
result[idx2] = sum % 10
}
}
for (let i = 0; i < result.length; i++) {
if (result[i] !== 0) break
result[i] = undefined
}
const resultString = result.join("")
return resultString || "0"
}
m = length of num1
n = length of num2
Time complexity- O(m * n)
Space complexity- O(m + n)
Written by S. Kumar on June 27th, 2021
3. Use minimum operations to make an array equal.
This question shows the developer's ability to use JavaScript passes and properties.
You are given a positive integer n. You generate an array of length n such that arr[i] = 2 * i + 1 where 0 <= i < n. You perform a series of operations on the array to make all the elements of the array equal. In one operation, you choose two indices of the array i and j and subtract 1 from arr[i], and add 1 to arr[j]. Your task is to calculate the minimum number of operations required to make all the elements of the array equal.
/*Example*/
Given n = 3
Expected output:- 2
Explanation: the generated array is [1, 3, 5]
In the first operation we choose i = 0 and j = 2, so the array becomes [2, 3, 4]
In the second operation we choose i = 0 and j = 2, so the array becomes [3, 3, 3]
Solution:
Approach I (one pass):
In this approach, we will iterate over the half elements of the generated array and find the number of operations to make them equal to mid. All the elements in the array will be equal to mid after those operations. There are two cases that we need to see: when n is odd and when n is even.
When n is odd: When n is odd, it can be observed that, the minimal way to make all the elements equal is to make them equal to the middle element of the array. The middle element is at index midIndex = (n - 1) / 2. The value at i = midIndex is:
mid = arr[midIndex] = 2 * midIndex + 1 = n
Thus, we will make all the elements equal to n. For example,
when n = 5,
=> arr = [1, 3, 5, 7, 9]
=> midIndex = 2
=> mid = 5 = n
In one operation we will choose opposite indices. For example, we will choose (0, 4) or (1, 3). This will make the process easier. Since we increase and decrease simultaneously, we need to iterate over only either the lower indices or the higher indices from midIndex (let’s iterate over lower indices). The number of elements below lower indices are countTerms = (n - 1) / 2.
When n is even: When n is even, it can be observed that, the minimal way to make all the elements equal is to make them equal to the mean of the middle two elements. For example,
when n = 6
=> arr = [1, 3, 5, 7, 9, 11]
The optimal way is to make all of them equal to 6 (mean of 5 and 7). In this case, too, the value of mid is n, that is mid = n.
The same argument applies that we will iterate over lower indices only (or higher indices only). The number of elements below lower indices are countTerms = n / 2.
/**
* @param {number} n
* @return {number}
*/
function minOperations(n) {
const mid = n
let ans = 0
let countTerms
if (n % 2 === 0) {
countTerms = (n - 1) / 2
} else {
countTerms = n / 2
}
for (let i = 0; i < countTerms; i++) {
const term = 2 * i + 1
ans += mid - term
}
return ans
}
Time complexity- O(n)
Space complexity- O(n)
Approach II (using AP properties):
As in the previous approach, the value of the mid element remains the same. There is an important observation while applying operation on a pair of indices.
When n is odd: Let us assume the array is [1, 3, 5, …, n, n + 2, …, 2 * n - 1]. The mid element is n which is also odd. The increments required for the lower indices are: n - 1, n - 3, …., 6, 4, 2 which is an AP with first term n - 1 and difference equal to 2. The sum of this AP will be the number of operations required to make all the elements of the array equal. The sum of the AP is:
sum = (first_term + last_term) * no_of_terms / 2
= (n - 1 + 2) * countTerms / 2
= (n + 1) * (n - 1) / 4
When n is even: Let us assume the array is [1, 3, 5, …, n, n + 2, …, 2 * n - 1]. The mid element is n which is also even. The increments required for the lower indices are: n - 1, n - 3, …., 5, 3, 1 which is an AP with first term n - 1 and difference equal to 2. The sum of this AP will be the number of operations required to make all the elements of the array equal. The sum of the AP is:
sum = (first_term + last_term) * no_of_terms / 2
= (n - 1 + 1) * countTerms / 2
= n * n / 4
/**
* @param {number} n
* @return {number}
*/
function minOperations(n) {
if (n % 2 === 1) {
return (n + 1) * (n - 1) / 4
}
return n * n / 4
}
Time complexity- O(1)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
4. Find the user's active minutes.
This question focuses on JavaScript for loops.
You are given 2-D array logs of size n x 2 and an integer k. The entry logs[i] = [idi, timei] indicates that the user with idi performed some action at the minute time.
Multiple users can perform multiple actions simultaneously, and a single user can perform multiple actions at the same minute.
The user active minutes (UAM) for a given user is defined as the number of unique minutes in which some action was performed.
Your task is to calculate a 1-indexed array answer of size k such that, for each j (1 <= j <= k), answer[j] is the number of users whose UAM equals j.
/*Example*/
Given logs = [[0, 5], [1, 2], [0, 2], [0, 5], [1, 3]] k = 5
Expected output:- [0, 2, 0, 0, 0]
Explanation:
The user with id = 0 performed three actions at minutes 5, 2, and 5. So UAM for this user is 2 (5 is counted once).
The user with id = 1 performed three actions at minutes 2 and 3. So UAM for this user is 2.
Since we have two users with UAM = 2, so answer[2] = 2, and the rest are all zero.
Given logs = [[1, 1], [2, 2], [2, 3]] k = 4
Expected output:- [1, 1, 0, 0]
Explanation:-
The user with id = 1 performed one action at minute 1. So UAM for this user is 1.
The user with id = 2 performed two actions at minutes 2 and 3. So UAM for this user is 2.
There is one user with UAM = 1 so answer[1] = 1, and there is one user with UAM = 2 so answer[2] = 1.
Solution:
We will store UAM for every user. Then we will count the UAM’s from 1 to k.
To calculate the UAM for all users, we will use a map. The keys for the map will be user ids and the corresponding values will be a set (we call this as userActivity). We will iterate over each entry in the array logs. For the particular user with userId, we retrieve its corresponding set userActivity from the map and add the corresponding value of minute time to this set userActivity.
After finding the user activities, we iterate over those user activities in the map. The UAM for that user will be the size of the corresponding set userActivity. We increase the corresponding counter in the answer array.
/**
* @param {number[][]} logs
* @param {number} k
* @return {number[]}
*/
function findingUsersActiveMinutes(logs, k) {
const users = new Map()
for (const log of logs) {
const userId = log[0]
const time = log[1]
const userActivity = users.get(userId) || new Set()
userActivity.add(time)
users.set(userId, userActivity)
}
const answer = new Array(k).fill(0)
for (const userActivity of users.values()) {
const uam = userActivity.size
answer[uam - 1]++
}
return answer
}
n = size of logs
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
5. What is the score of parentheses with the given string?
This interview question concentrates on JavaScript stacks and cores.
You are given string str consisting of opening and closing parentheses. Your task is to compute the score of the string based on the following rules:
1. “()†has score 1.
2. AB has score A + B, where A and B are two balanced parentheses strings.
3. (A) has score 2 * B, where A is a balanced parentheses string
/*Example*/
Given str = “()â€
Expected output: 1
Given str = “(())â€
Expected output: 2
Explanation: 2 * 1 = 2
Given str = “()()â€
Expected output: 2
Explanation: 1 + 1 = 2
Given str = “(()(()))"
Expected output: 6
Explanation: 2 * (1 + 2 * 1) = 6
Solution:
Approach I (using stack):
Every position in the string has a depth. The depth for different positions for string “(()(()))" are: “ ( ( ) ( ( ) ) )"
| | | | |
0 1 2 2 3
We will maintain the score up to the current depth that we are on. When we see an opening bracket, we increase our depth with an initial score of 0 and push to a stack. When we see a closing bracket, we add twice the score of the previous deeper part except when we encounter “()†which has score 1.
We have an array stack. The value stack[i] represents the score of depth i that we have calculated so far. We need to calculate the final value of stack[0], that is, score of depth 0, that is, score of the whole string. Lets iterate example “(()(()))",
Initially stack = [0]
Iteration 1:
char = “(“
push 0 to stack
final stack = [0, 0]
Iteration 2:
char = “(“
push 0 to stack
final stack = [0, 0, 0]
Iteration 3:
char = “)“
currDepthScore = 0
deeperDepthScore = 0
deeperDepthScore = 1
final stack = [0, 1]
Iteration 4:
char = “(“
push 0 to stack
final stack = [0, 1, 0]
Iteration 5:
char = “(“
push 0 to stack
final stack = [0, 1, 0, 0]
Iteration 6:
char = “)“
currDepthScore = 0
deeperDepthScore = 0
deeperDepthScore = 1
final stack = [0, 1, 1]
Iteration 7:
char = “)“
currDepthScore = 1
deeperDepthScore = 1
deeperDepthScore = 1 + 2 * 1 = 3
final stack = [0, 3]
Iteration 8:
char = “)“
currDepthScore = 3
deeperDepthScore = 0
deeperDepthScore = 0 + 2 * 3 = 6
final stack = [6]
So the answer is 6.
/**
* @param {string} str
* @return {number}
*/
function scoreOfParentheses(str) {
const stack = []
stack.push(0)
for (const char of str) {
if (char === "(") {
stack.push(0)
continue
}
const currDepthScore = stack.pop()
let deeperDepthScore = stack.pop()
deeperDepthScore += Math.max(2 * currDepthScore, 1)
stack.push(deeperDepthScore)
}
return stack.pop()
}
n = length of string
Time complexity- O(n)
Space complexity- O(n)
Approach II (count cores):
The final answer will be the sum of powers of 2, as every core “(“, with its score 1, will be multiplied by 2 for each exterior set of parenthesis that contains that core.
Let’s expand the given string:
( ( ) ( ( ) ) )
o1 o2 c2 o3 o4 c4 c3 c1
We are representing opening brackets with oi and closing with ci. Let us represent a balancing pair with <oi, ci>. There are two cores <o2, c2> and <o4, c4>. The first core is at depth 1 and has 1 balancing pair <o1, c1> surrounding it. So its contribution to the score will be 21 = 2. The second core is surrounded by two balancing pairs <o1, c1> and <o3, c3>. So its contribution to the score will be 22 = 4. So the total score is 2 + 4 = 6.
We iterate over the whole string maintaining the number of surrounding balanced pairs in-depth. Depth will be equal to opening brackets before the current bracket which are not balanced yet. When we encounter a “(“, we simply increase depth. When we encounter a “)“, we check its preceding bracket to check if this bracket makes a core or not. If it makes a core, its contribution to the score will be equal to 2depth. We calculate the power using the left-shift operation.
/**
* @param {string} str
* @return {number}
*/
function scoreOfParentheses(str) {
let score = 0
let depth = 0
for (let i = 0; i < str.length; i++) {
const char = str[i]
if (char === "(") {
depth++
} else {
depth--
if (str[i - 1] === "(") {
score += 1 << depth
}
}
}
return score
}
n = length of string
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
6. Sort characters by frequency.
This question focuses on the JavaScript sort function.
You are given string str consisting of English lowercase letters. Your task is to sort the characters of the string in decreasing order of their frequencies in the string.
/*Example*/
Given:- str = "tree"
Expected output:- "eetr"
Please note that the relative order of characters with the same frequency does not matter. So, "eert" is also a valid answer.
Solution:
Approach I (using inbuilt sort function):
NOTE: Since all the same letters are accumulated together, we call them a group. So in the string "tree" after sorting, three groups are:- “eeâ€, “tâ€, “râ€.
We will find the frequency of each character using the function getFreq. This function calculates the frequency of each character and returns it in a map.
After this, we convert the string into an array of characters using spread operation (...). So if,
str = “treeâ€
str = [...str] = [“tâ€, “râ€, “eâ€, “eâ€]
After this, we use the inbuilt sort function Array.prototype.sort. This function takes one argument: compareFunction. In our code, we are passing an arrow function for compareFunction. The compareFunction takes two arguments: a and b and SHOULD return one integer based on the following condition:
1. If a is supposed to come before b in the sorted array, the function SHOULD return a negative integer (usually -1).
2. If a is supposed to come after b in the sorted array, the function SHOULD return a positive integer (usually +1).
3. If the order of a and b does not affect the sorted array, the function SHOULD return zero.
In our case,
â— If the letter a has frequency greater than the frequency of the letter b (freqA > freqB), a MUST come before b. So we return -1.
â— If the letter a has a frequency less than the frequency of the letter b (freqA < freqB), a MUST come after b. So we return 1
â— If both the letters have the same frequency, we sort them lexicographically (this does not matter in the question which group should come first).
/**
* @param {string} str
* @return {string}
*/
function frequencySort(str) {
const freq = getFreq(str)
str = [...str]
str.sort((a, b) => {
const freqA = freq.get(a)
const freqB = freq.get(b)
if (freqA > freqB) return -1
if (freqA < freqB) return 1
if (a < b) return 1
if (b < a) return -1
return 0
})
return str.join("")
}
function getFreq(str) {
const freq = new Map()
for (const char of str) {
const prevFreq = freq.get(char) || 0
freq.set(char, prevFreq + 1)
}
return freq
}
n = length of string
Time complexity- O(n logn)
Space complexity- O(n)
Approach II (using buckets):
We can sort the characters without using the inbuilt sort function. We will use the concept of buckets. We create an array of buckets. buckets[i] is an array and contains the groups of those characters which have a frequency equal to i (or groups of length i each). Initially, we don’t initialize any of buckets[i] to save space.
We iterate over all the letters in the freq map. For each letter char with frequency charFreq, we find the group with length charFreq consisting of char. Then we push the group into corresponding bucket buckets[charFreq]. Then, we iterate over those buckets starting with the largest bucket (hence the groups with larger frequencies) and push the groups into res array.
Things to note in the code:
â— const [char, charFreq] of freq.entries(): We iterate over all the entries of the map. In each iteration, the entry is an array of length 2 with entry = [key, value]. Then, we destructure them into key-value using [char, charFreq] = entry.
â— We did not initialize buckets with empty arrays. So while iterating over buckets in the end, we need to use guard condition if (buckets[i]) to avoid runtime errors.
◠To create the group with char of length charFreq, we use the function String.prototype.padEnd. The function two takes two arguments targetLength and padString. It appends the “this†object (empty string in our code) with padString repeatedly until the length of the resulting string becomes equal to targetLength.
/**
* @param {string} str
* @return {string}
*/
function frequencySort(str) {
const freq = getFreq(str)
const buckets = new Array(str.length + 1)
for (const [char, charFreq] of freq.entries()) {
const bucket = buckets[charFreq] || []
const group = "".padEnd(charFreq, char)
bucket.push(group)
buckets[charFreq] = bucket
}
let res = []
for (let i = buckets.length - 1; i >= 0; i--) {
if (buckets[i]) {
res = res.concat(buckets[i])
}
}
return res.join("")
}
function getFreq(str) {
const freq = new Map()
for (const char of str) {
const prevFreq = freq.get(char) || 0
freq.set(char, prevFreq + 1)
}
return freq
}
n = length of string
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
7. Find all duplicates in an array.
This question shows the developer's knowledge of JavaScript mapping and modifying arrays.
You are given array nums of length n. All the integers in nums are in the range [1, n]. Each integer in the array appears either once or twice. Your task is to find the integers that appear twice and return them in an array in any order.
/*Example*/
Given nums = [4, 3, 2, 7, 8, 2, 3, 1]
Expected output:- [2, 3]
Constraints
1 <= nums[i] <= n
Solution:
Approach I (using map):
We will iterate over all the integers in nums. We will store these integers in a map visited. If the num already exists in visited, it means this integer appears twice. So, we will push it to result in array res.
/**
* @param {number[]} nums
* @return {number[]}
*/
function findDuplicates(nums) {
const visited = new Map()
const res = []
for (const num of nums) {
if (visited.has(num)) {
res.push(num)
}
visited.set(num, true)
}
return res
}
Time complexity- O(n)
Space complexity- O(n)
Approach II (modifying original array):
As all the integers lie in the range [1, n] and the size of the given array is n, which means there is 1:1 mapping between the numbers and indices if all the numbers are distinct. We can rearrange the array so that an integer num appears on the index idx = num - 1 if it is not already there. If it is already at the required index, it means this number has a duplicate.
We will start from index i = 0. For a particular index i, if the number num = nums[i] is not already at index idx = num - 1, we swap integers at index i and idx. This will make num to be present on index idx = num - 1 and the index i will have the previous value of nums[idx]. We will do this for every index and for every number
Before loop:- nums = [4, 3, 2, 7, 8, 2, 3, 1]
Iteration 1:- i = 0
num = 4
idx = 4 - 1 = 3
numAtIdx = nums[3] = 7
num !== numAtIdx // true => so we swap indices i and idx
// the nums is modified to
nums = [7, 3, 2, 4, 8, 2, 3, 1]
Iteration 2:- i = 0
num = 7
idx = 4 - 1 = 6
numAtIdx = nums[6] = 3
num !== numAtIdx // true => so we swap indices i and idx
// the nums is modified to
nums = [3, 3, 2, 4, 8, 2, 7, 1]
Iteration 3:- i = 0
num = 3
idx = 4 - 1 = 2
numAtIdx = nums[2] = 2
num !== numAtIdx // true => so we swap indices i and idx
// the nums is modified to
nums = [2, 3, 3, 4, 8, 2, 7, 1]
Iteration 4:- i = 0
num = 2
idx = 4 - 1 = 1
numAtIdx = nums[1] = 3
num !== numAtIdx // true => so we swap indices i and idx
// the nums is modified to
nums = [3, 2, 3, 4, 8, 2, 7, 1]
Iteration 4:- i = 0
num = 3
idx = 4 - 1 = 2
numAtIdx = nums[2] = 3
num !== numAtIdx // false
// increment i
...
Iteration 9:- i = 4
num = 8
idx = 4 - 1 = 7
numAtIdx = nums[7] = 1
num !== numAtIdx // true => so we swap indices i and idx
// the nums is modified to
nums = [3, 2, 3, 4, 1, 2, 7, 8]
Iteration 10:- i = 4
num = 1
idx = 4 - 1 = 0
numAtIdx = nums[0] = 3
num !== numAtIdx // true => so we swap indices i and idx
// the nums is modified to
nums = [1, 2, 3, 4, 3, 2, 7, 8]
Iteration 11:- i = 4
num = 3
idx = 4 - 1 = 2
numAtIdx = nums[2] = 3
num !== numAtIdx // false
// increment i
// run the condition for while loop becomes false
// the final nums = [1, 2, 3, 4, 3, 2, 7, 8]
We will again loop the modified nums. If the current integer is not at the correct place, it means it is duplicate; so we will push to the result array otherwise we continue to the next integer.
/**
* @param {number[]} nums
* @return {number[]}
*/
function findDuplicates(nums) {
const res = []
let i = 0
while (i < nums.length) {
const num = nums[i]
const idx = num - 1
const numAtIdx = nums[idx]
if (num !== numAtIdx) {
nums[i] = numAtIdx
nums[idx] = num
} else {
i++
}
}
for (let i = 0; i < nums.length; i++) {
if (i !== nums[i] - 1) {
res.push(nums[i])
}
}
return res
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
8. What are the minimum number of jumps to get to index 0?
This interview question shows the developer's knowledge of JavaScript recursion.
You are given an array arr of non-negative integers. When you are at index i, you can jump to index i + arr[i] or i - arr[i]. You are currently at index start. Your task is to determine if you can reach any index with a value 0.
/*Example*/
Given arr = [4, 2, 3, 0, 3, 1, 2] start = 5
Expected output: true
Explanation:- The possible ways are:
i5 -> i4 -> i1 -> i3
i5 -> i6 -> i4 -> i1 -> i3
Solution:
We check all the jumps recursively. We modify the element and make it negative if we have already visited it. When we are at the index start, we check the indices start + arr[start] and start - arr[start] recursively. We perform the following steps:
â— If the current index (start) that we are checking is out of bound, we directly return false.
â— If the current index is already visited (by checking the value of arr[start]), we return false.
â— If the value at the start is 0, it means we can reach at least one index with a value equal to 0. So we return false.
â— Otherwise, we mark the current index as visited, and check the indices start + arr[start] and start - arr[start].
/**
* @param {number[]} arr
* @param {number} start
* @return {boolean}
*/
function canReach(arr, start) {
if (start < 0) return false
if (start >= arr.length) return false
if (arr[start] < 0) return false
if (arr[start] === 0) return true
// visited this element but was not 0
// mark it visited by negating it
arr[start] = -arr[start]
return canReach(arr, start + arr[start]) ||
canReach(arr, start - arr[start])
}
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
9. Find the maximum length of consecutive ones.
This question concentrates on the ability to work with JavaScript iteration and arrays.
You are given binary array nums and integer totalFlips. Your task is to find the maximum length of a subarray so that it has all one’s after flipping at most totalFlips 0’s.
/*Example*/
Given nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] k = 2
Expected output: 6
Explanation: If we flip the bits at indices 6 and 11, we get the required subarray.
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Solution:
We will iterate over the whole array. We will have two pointers (indices) left and right, making a window of size right-left + 1. We track the count of zeros in this window (variable zerosCount). In each iteration, we increment the right pointer. If we encounter a zero, we increase zerosCount. When zerosCount becomes greater than totalFlips, we move the left pointer to the right side. After the loop, the right-left will be the size of the required window. For the given nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0],
NOTE:- x-y in zerosCount denotes the old-new value respectively.
Iter left right window zerosCount remark
1 0 0 1 0-0
2 0 1 11 0-0
3 0 2 111 0-0
4 0 3 1110 0-1
5 0 4 11100 1-2 zerosCount is equal to
totalFlips; maxWindow size = 5
6 1 5 111000 2-3 zerosCount > totalFlips
increase left by 1
7 2 6 1110001 3-3 zerosCount > totalFlips
increase left by 1
8 3 7 11100011 3-3 zerosCount > totalFlips
increase left by 1
9 4 8 111000111 3-2 zerosCount > totalFlips
increase left by 1; window size is
still same = 5; zerosCount is also
reduced
10 4 9 1110001111 2-2 window size is increased to 6
11 5 10 11100011110 2-2 window size is still same = 6
/**
* @param {number[]} nums
* @param {number} totalFlips
* @return {number}
*/
function longestOnes(nums, totalFlips) {
let left = 0
let right = 0
let zerosCount = 0
for (right = 0; right < nums.length; right++) {
// we encountered a 0, so increase the zerosCount
if (nums[right] === 0) {
zerosCount++
}
// we have extra zeros in the window. We slide the
// left pointer and try to remove extra 0’s
if (zerosCount > totalFlips) {
// there was 0 at the left pointer. So update
// zerosCount--
if (nums[left] === 0) {
zerosCount--
}
left++
}
}
return right - left
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021