George
Lead Frontend-developer of an IT-company
Many developers don’t like being asked to write code on an interview, but sometimes it’s unavoidable. In this article, I will analyze several tasks that you may encounter when passing an interview for the position of a Middle JavaScript developer.
What knowledge is needed:
- JavaScript;
- basic data structures;
- Big O.
How to approach the problem soving:
- think aloud;
- take your time and don’t give up;
- work with passion.
JavaScript
I can’t stress enough how important it is to learn the language itself well in the first place. This will help you write an elegant solution without getting bogged down in its intricacies. To do this, you must not only know all the elements and rules of the language, but also have a deep understanding of how they work.
Useful resources:
- Eloquent JavaScript (by Marijn Haverbeke);
- JavaScript Ninja (by John Resig).
Data Structures
If you do not know the data structure, the chances of coming up with an optimal solution (and a solution in general) are much less. Therefore, you must definitely learn how to work with the following things:
- arrays;
- objects/hashmaps;
- linked lists;
- stacks;
- queues;
- trees;
- graphs.
Big О
Big O describes the efficiency of code execution – that is, how fast the algorithm is executed taking into account the input data (time complexity).
After you write your solution, it is important to name its complexity and execution time.
Big O to the problem is written as a comment above the solution.
Example:
// O(n) time | O(1) space
After determining the effectiveness of your code, discuss with the interviewer what else can be improved. If possible, offer alternative ways to solve the problem. This will show that you are not just giving memorized options – you really understand how the code works.
Think aloud
Before you start writing code, you need to solve the problem in your mind pronouncing the whole thought process. So you will not get confused, and the interviewee will be able to assess your way of thought.
Take your time and don’t give up
One of the common mistakes is to give a ready-made solution without double-checking. Before submitting your work, be sure to go through your code one more time, analyzing it aloud.
Don’t panic and don’t give up if you can’t reach the solution. It’s not over yet, and you can still successfully pass the interview. Think about the problem and ask the interviewer for a little hint – it’s better than sitting silently and hoping that you will get help from outside.
Work with enthusiasm
Show genuine interest in solving the problem – this will defuse the situation and facilitate the process for both you and the interviewer. Feel the excitement, act with a twinkle in your eyes and with heart afire – then it will be much easier to concentrate on the task.
Middle level tasks
Sum of two numbers
Write a function that takes two arguments: an array of unique integers and an integer sum. If the sum of any two array numbers from the argument is equal to the number that comes as the second argument, the function must return a new array of these two numbers in any order. If there is no solution, return an empty array. The current number cannot be added to itself.
Input example:
array = [3, 5, -4, 8, 11, 1, -1, 6] targetSum = 10
As a result:
[-1, 11] or [11, -1], as -1 + 11 = 10 = targetSum
Solution 1
// O(n^2) time | O(1) space
function twoNumberSum(array, targetSum) {
for (let currentIndex = 0; currentIndex < array.length; currentIndex++) {
const currentNumber = array[currentIndex];
for (let currentCompareIndex = currentIndex + 1; currentCompareIndex < array.length; currentCompareIndex++) {
const currentCompareNumber = array[currentCompareIndex];
if (currentCompareNumber + currentNumber === targetSum) {
return [currentNumber, currentCompareNumber];
}
}
}
return [];
}
We iterate over the array, and on each element we iterate over all subsequent elements, checking the current sum with the following ones against the sum from the argument.
Solution 2
// O(n) time | O(n) space
function twoNumberSum(array, targetSum) {
const nums = {};
for (const currentNum of array) {
const potentialMatch = targetSum - currentNum;
if (potentialMatch in nums) {
return [currentNum, potentialMatch];
} else {
nums[currentNum] = true;
}
}
return [];
}
We iterate over the array once, storing in the new object the lack of the current element needed to get the targetSum. On each iteration, we check if the current value is in the residuals object. If so, then we already ran into a value in the previous iteration that lacked the current element as a remainder. Accordingly, we found a pair and can return it.
Converting an array to an object with grouping and filtering of elements
Write a function that takes an array of students as input, where a student is an object with fields “name”, “age” and “group number” {name: string, age: number, groupId: number}, and returns an object as output, where the key is the group number and the value is an array of students over 17 years old.
Solution 1
// O(n) time | O(n) space
function groupOnlyMatureStudentsByGroup(students) {
return students.reduce((acc, student) => {
const { groupId, age } = student;
if (age < 18) {
return acc;
}
if (groupId in acc) {
acc[groupId].push(student);
} else {
acc[groupId] = [student];
}
return acc;
}, {});
}
We iterate over the array using the higher-order reduce method, collecting the result into an accumulating value.
Solution 2
// O(n) time | O(n) space
const groupOnlyMatureStudentsByGroup = (students) =>
students.reduce(
(acc, student) =>
student.age < 18
? acc
: acc[student.groupId]
? acc[student.groupId].push(student) && acc
: (acc[student.groupId] = [student]) && acc,
{}
);
Signature Solution in one line – that’s a given!
If the student’s age is less than 18, return the accumulator. If not, see if its group id is in the accumulator. If there is, then the accumulator already has an array with students, therefore, we add this student to it; otherwise we create a new array with the current student and add it to the accumulator under the current group id.
Checking a line for a palindrome
Write a function that takes a string consisting of lowercase letters as input, and returns a boolean as output, which answers whether the given string is a palindrome or not.
A palindrome is a word or text that reads the same in both directions.
Solution 1
Option 1
// O(n^2) time | O(n) space
function isPalindrome(string) {
let reversed = "";
for (let i = string.length - 1; i >= 0; i--) {
reversed += string[i];
}
return string === reversed;
}
Option 2
function isPalindrome(string) {
let reversed = [];
for (let i = string.length - 1; i >= 0; i--) {
reversed.push(string[i]);
}
return string === reversed.join("");
}
- Set up a variable to store the result.
- We loop through the string from the end, each time concatenating the current letter with the variable we previously introduced.
- Compare the input string with the reversed one.
Why does the first solution have time complexity O(n^2) and the second O(n)?
The reason is the way JS stores values at a low level. Due to the fact that the string is a primitive value, when concatenating in each loop, it is re-created with a new memory location.
Solution 2
function isPalindrome(string) {
let leftPointer = 0;
let rightPointer = string.length - 1;
while (leftPointer < rightPointer) {
if (string[leftPointer] !== string[rightPointer]) {
return false;
}
leftPointer++;
rightPointer--;
}
return true;
}
- We start two pointers – for the end and the beginning of the line.
- We go through the while loop until the left pointer crosses the right one.
- In the loop, we check for a mismatch between the letters of the string by pointers. If we find an inequality, the given string cannot be a palindrome, so we exit the function by returning false.
- If the condition didn’t pass, then we move both pointers closer to the center and continue to go through the loop.
- If we exited the loop, then the string is a palindrome and we return true.
Solution 3
// O(n) time | O(n) space
const isPalindrome = (string) => string === string.split("").reverse().join("");
Nowhere without a one-line solution! There is nothing wrong with using built-in functions to quickly solve a problem, even if it is not as efficient as possible. But keep in mind that this should not be your only solution; it can only be presented as an addition to more effective options.
- We split the string into an array of letters.
- Reverse the order of elements.
- We connect the elements back into a whole line.
- WIN!
Find nearest value in binary tree
Write a function that takes two arguments – a binary tree and a number value, and returns the nearest value found in the binary tree.
Node = { value: number | null, left: Node | null, right: Node | null }
Solution
// Average: O(log(n)) time | O(1) space
// Worst: O(n) time | O(1) space
function findClosestValueInBst(tree, target) {
let currentNode = tree;
let currDifference = Math.abs(currentNode.value - target);
function findClosest(node) {
const difference = Math.abs(node.value - target);
if (difference === 0) return node.value;
if (difference <= currDifference) {
currentNode = node;
currDifference = difference;
}
if (target < node.value) {
if (node.left === null) {
return currentNode.value;
}
return findClosest(node.left);
} else if (target >= node.value) {
if (node.right === null) {
return currentNode.value;
}
return findClosest(node.right);
}
}
return findClosest(currentNode)
}
Knowing the property of a balanced binary tree, where on the left are all node values less than the current value, and on the right are equal or greater in value, we can at best discard half of the tree each time.
In this solution, we go recursively through the nodes, recording and comparing the difference with the value from the argument. If the value is equal to the desired value, then we have found the node we need; otherwise we look to see if the current value of the node is less or more than the one we are looking for. Depending on this, we continue to descend recursively in the direction we need, updating the difference, until we hit the end of the branch.
Conclusion
During an interview, you may face completely different tasks. You shouldn’t be afraid of them. The main purpose of these tasks is that a developer voices the way of thinking. Most likely, they will turn a blind eye to errors and a task that is not fully implemented in the code. It is important for the interviewer to see how you reason, what approaches you use depending on the situation, how quickly you can read and understand someone else’s code. It is on the basis of this information that he will build further conversation with you and make a hiring decision.
So keep it up and good luck with your interview! ☺
