JavaScript Data Structures and Algorithms: Essential Interview Questions

# JavaScript Data Structures and Algorithms: Essential Interview Questions

Understanding data structures and algorithms (DSA) is crucial for any software engineer, especially those working with JavaScript. This blog covers some of the most common DSA questions asked in interviews, providing explanations and JavaScript solutions.

Table of Contents

1. Array Rotation

2. Balanced Parentheses

3. Find the Missing Number

4. Reverse a Linked List

5. Binary Search

Array Rotation

Question: How would you rotate an array to the right by k steps, where k is a non-negative integer?

Solution:

function rotateArray(nums, k) {

  k = k % nums.length;

  let part = nums.splice(nums.length - k);

  nums.unshift(...part);

  return nums;

}

Explanation: This function first reduces `k` to a manageable size (in case it's larger than the array's length), splits the array into two parts, and then rearranges the parts to achieve the rotation.

Balanced Parentheses

Question: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

Solution:

function isValid(s) {

  let stack = [];

  let map = {

    '(': ')',

    '[': ']',

    '{': '}'

  };

  for (let char of s) {

    if (map[char]) {

      stack.push(map[char]);

    } else {

      if (stack.pop() !== char) return false;

    }

  }

  return stack.length === 0;

}

Explanation: This uses a stack to track open brackets and ensures they close correctly. If the stack is empty at the end, the string is valid.

Find the Missing Number

Question: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Solution:

function missingNumber(nums) {

  let expectedSum = nums.length * (nums.length + 1) / 2;

  let actualSum = nums.reduce((a, b) => a + b, 0);

  return expectedSum - actualSum;

}

Explanation: This solution uses the formula for the sum of an arithmetic series to find the expected sum and subtracts the actual sum from it to find the missing number.

Reverse a Linked List

Question: How can you reverse a linked list?

Solution:

function reverseLinkedList(head) {

  let prev = null;

  let current = head;

  while (current != null) {

    let next = current.next;

    current.next = prev;

    prev = current;

    current = next;

  }

  return prev;

}

Explanation: Traverse the list, rearranging the links by shifting the nodes one by one from the front to the back.

Binary Search

Question: Implement binary search for a sorted array.

Solution:

function binarySearch(arr, x) {

  let start = 0, end = arr.length - 1;

  while (start <= end) {

    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === x) return mid;

    else if (arr[mid] < x) start = mid + 1;

    else end = mid - 1;

  }

  return -1;

}

Explanation: Binary search repeatedly divides the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.