DSA Interview Challenges

Missing Number

The total of the first n natural numbers is n * (n + 1) / 2
The difference between the sum of the input array and the total should be the missing number


/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function (nums) {
  const n = nums.length;
 
  var total = (n * (n + 1)) / 2;
  var sum = 0;
 
  for (var i = 0; i < n; i++) {
    sum = sum + nums[i];
  }
 
  return total - sum;
};

Complexity

Time: O(n)
Space: O(1)

Concatenation of Array

Create a new array to hold the concatenated array
Loop through the input array and push each element to the new array twice


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var getConcatenation = function (nums) {
  const concatNums = [];
 
  for (let i = 0; i < nums.length; i++) {
    concatNums.push(nums[i]);
  }
 
  for (let i = 0; i < nums.length; i++) {
    concatNums.push(nums[i]);
  }
 
  return concatNums;
};

Complexity

Time: O(n)
Space: O(n)

Single Number

Perform bitwise XOR on all elements in the array
The XOR operation will cancel out all duplicate numbers, leaving the single number


/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  return nums.reduce((x, y) => x ^ y);
};

Complexity

Time: O(n)
Space: O(1)

Kids With the Greatest Number of Candies

Find the kid with the most candies & check if each kid can have the most candies by adding extra candies
Max can also be easily found using Math.max(...candies)


/**
 * @param {number[]} candies
 * @param {number} extraCandies
 * @return {boolean[]}
 */
var kidsWithCandies = function (candies, extraCandies) {
  // find the kid with the most candies
  let max = 0;
  for (let i = 0; i < candies.length; i++) {
    if (max < candies[i]) {
      max = candies[i];
    }
  }
 
  // check if each kid can have the most candies
  for (let i = 0; i < candies.length; i++) {
    candies[i] = candies[i] + extraCandies >= max;
  }
 
  return candies;
};

Complexity

Time: O(n)
Space: O(n)

Count Tested Devices After Test Operations

Keep track of the number of devices that have been tested
Increment the count if the battery percentage is greater than the current count


/**
 * @param {number[]} batteryPercentages
 * @return {number}
 */
var countTestedDevices = function (batteryPercentages) {
  let count = 0;
 
  for (let i = 0; i < batteryPercentages.length; i++) {
    if (batteryPercentages[i] > count) {
      count++;
    }
  }
 
  return count;
};

Complexity

Time: O(n)
Space: O(1)

How Many Numbers Are Smaller Than the Current Number

Build a count array to store the frequency of each number
Calculate the number of elements lesser than the current number


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
  const length = nums.length;
  const limit = 100;
  let countArray = new Array(limit + 1).fill(0);
 
  // build the count array
  for (let i = 0; i < length; i++) {
    countArray[nums[i]]++;
  }
 
  // calculate the number of elements lesser than the current number in one pass
  let prevCount = 0;
  for (let i = 0; i <= limit; i++) {
    if (countArray[i]) {
      const currentCount = countArray[i];
      countArray[i] = prevCount;
      prevCount += currentCount;
    }
  }
 
  const smallerArray = [];
  for (let i = 0; i < length; i++) {
    smallerArray.push(countArray[nums[i]]);
  }
 
  return smallerArray;
};

Complexity

Time: O(n)
Space: O(n)

Running Sum of 1d Array

Naive approach would be to calculate the sum of all the array elements before the current index for every element, in to a new array.
Simpler and better approach would be to replace the current element by its sum with the previous element


/**
 * @param {number[]} nums
 * @return {number[]}
 */
var runningSum = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[i] += nums[i - 1];
  }
  return nums;
};

Complexity

Time: O(n)
Space: O(1)

Shuffle the Array

Simple solution would be to create a new array and shift the elements in the order given


/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number[]}
 */
var shuffle = function (nums, n) {
  const newNums = [];
 
  for (let i = 0, j = n; i < n; i++, j++) {
    newNums.push(nums[i], nums[j]);
  }
 
  return newNums;
};

Complexity

Time: O(n)
Space: O(n)

Check if Array Is Sorted and Rotated

In a sorted array, if current value is greater than the next value, then it is unsorted pair
In a rotated sorted array, there will be only at max one unsorted pair


/**
 * @param {number[]} nums
 * @return {boolean}
 */
var check = function (nums) {
  let unsortedCount = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > nums[(i + 1) % nums.length]) {
      unsortedCount++;
    }
 
    if (unsortedCount > 1) {
      return false;
    }
  }
 
  return true;
};

Complexity

Time: O(n)
Space: O(1)

Matrix Diagonal Sum

The diagonal sum of matrix can be calculated by calculating the sum of the each diagonal and adding up
In case the matrix is having odd number of rows, then central element has to be considered only once


/**
 * @param {number[][]} mat
 * @return {number}
 */
var diagonalSum = function (mat) {
  const n = mat.length;
  let diagonalSum = 0;
 
  // sum of diagonal from [0, 0] to [n-1, n-1]
  for (let i = 0; i < n; i++) {
    diagonalSum += mat[i][i];
  }
 
  // sum of diagonal from [0, n-1] to [n-1, 0]
  for (let i = 0, j = n - 1; i < n; i++, j--) {
    diagonalSum += mat[i][j];
  }
 
  // if n is odd, then subtract the central element
  if (n % 2 === 1) {
    diagonalSum -= mat[Math.floor(n / 2)][Math.floor(n / 2)];
  }
 
  return diagonalSum;
};

Complexity

Time: O(n)
Space: O(1)

Check if Number Has Equal Digit Count and Digit Value

Store the count of each digit in the array
Compare the count of each digit with the digit value


function digitCount(num) {
  const numCount = new Array(10).fill(0);
 
  for (const digit of num) {
    numCount[digit]++;
  }
 
  for (let idx = 0; idx < num.length; idx++) {
    // if count of digit is not equal to digit value
    if (numCount[idx] != num[idx]) {
      return false;
    }
  }
 
  return true;
}

Complexity

Time: O(n)
Space: O(1)

Sum of Unique Elements

This is basically calculating the frequency of each element and sum up the unique elements (having frequency 1)


/**
 * @param {number[]} nums
 * @return {number}
 */
var sumOfUnique = function (nums) {
  let arr = [],
    sum = 0;
  for (let i = 0; i < nums.length; i++) {
    arr[nums[i]] = (arr[nums[i]] || 0) + 1;
  }
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == 1) {
      sum += i;
    }
  }
  return sum;
};

Complexity

Time: O(n)
Space: O(n)

Max Consecutive Ones

Use a counter to keep track of the number of consecutive ones
Update the maximum count when a zero is encountered


/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function (nums) {
  let count = 0, max = 0;
 
  for (const num of nums) {
    if (num) {
      count++;
    } else {
      max = Math.max(max, count);
      count = 0;
    }
  }
 
  return Math.max(max, count); // Edge case when the array ends with 1
};

Complexity

Time: O(n)
Space: O(1)

Move Zeroes

Move all non-zero elements to the front of the array
Fill the remaining elements with zeros


/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let pointer = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (nums[i]) {
      nums[pointer] = nums[i];
      pointer++;
    }
  }
 
  for (let i = pointer; i < nums.length; i++) {
    nums[i] = 0;
  }
 
  return nums;
};

Complexity

Time: O(n)
Space: O(1)

Rotate Array

Reverse the entire array to get the correct order of the elements
Reverse the first k elements and the remaining elements separately


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  k = k % nums.length;
 
  nums.reverse();
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  return nums;
};
 
function reverse(nums, start, end) {
  while (start < end) {
    // Swap the start and end elements
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
 
    start++;
    end--;
  }
}

Complexity

Time: O(n)
Space: O(1)