DSA Interview Challenges

Longest Common Prefix

The main function iteratively updates the common prefix by comparing it with each string in the array.
The getCommonPrefix function constructs the common prefix by comparing characters one by one until a mismatch occurs.


/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let i =0;
    if(strs.length===1)
        return strs[0];
    let result ="";
     result += getCommonPrefix(strs[0], strs[1]);
    for(let i=2;i<strs.length;i++){
       result= getCommonPrefix(result, strs[i]);
    }
    return result;
};
 
function getCommonPrefix(str1, str2){
    let longStr;
    let smallStr;
    let result="";
    if(str1[0] !== str2[0])
        return "";
   if(str1.length<=str2.length){
       longStr = str2;
       smallStr = str1;
   }
    else{
        longStr = str1;
       smallStr = str2;
    }
   for(let i=0;i<smallStr.length;i++){
       if(longStr[i]=== smallStr[i]){
           result+=longStr[i];
       }
       else{
           return result;
       }
    } 
    return result;
}

Complexity

Time: O(N * M)
- Where N is the number of strings and M is the length of the shortest string among all the strings.
Space: O(M)
- Where M is the length of the shortest string among all the strings.

Reverse Linked List

Iterating through the list and reversing the direction of the next pointers of the nodes.
After the entire list is reversed, the head pointer is updated to point to the new head of the list, which was the original tail.


/**
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null,curr=head,next=null
    while(curr!=null){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
};

Complexity

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

Valid Anagram

Create an object called “count” , with key as character of string and value as count of that character in the string
Loop through those two strings , one with increasing of count and other with decreasing of count


/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
 
var isAnagram = function(s, t) {
    if(s.length !== t.length)
        return false;
    
    let count={};
 
    for(let char of s){
        count[char] = (count[char] || 0) + 1;
    }
    
    for(let char of t){
        if(!count[char])
            return false;
         count[char]--;
    }
    return true;
};

Complexity

Time: O(n)
Space:
- O(1) : If the character set is fixed (e.g., ASCII), the space required for the count object is O(1) since the number of unique characters is constant (256 for extended ASCII).
- O(k) : For Unicode or larger character sets, the space required could be O(k), where k is the number of unique characters in the input.

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)

Valid Perfect Square

Naive approach would be start half the number now multiply each number by itself and check if it match with target
As the array is already sorted Binary search can be modified to reduce the time complexity


/**
 * @param {number} num
 * @return {boolean}
 */
var validPerfectSquare = function (num) {
  if (num == 1) return true;
 
  let left = 0,
    right = Math.floor(num / 2);
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (mid * mid === num) {
      return true;
    }
 
    if (mid * mid < num) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
};

Complexity

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

Search Insert Position

Naive approach would be start from left side of the array and insert at a point where you find the first match or next higher number. This approach works very well for small arrays.
As the array is already sorted Binary search can be modified to reduce the time complexity


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0, right = nums.length - 1;
  let ans = nums.length;
 
  if (target > nums.at(-1)) {
    // if target is greater than the last element
    return ans;
  }
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // obtain the mid value
 
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] >= target) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};

Complexity

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

Find Smallest Letter Greater Than Target

Binary search technique is used to find the smallest letter greater than the target
If the target is greater than the last element or smaller than the first element, return the first element


/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function (letters, target) {
  let left = 0, right = letters.length - 1;
  let ans = 0;
 
  // if target is beyond the limits of letters
  if (target < letters[0] || letters.at(-1) < target) {
    return letters[ans];
  }
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (target < letters[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return letters[ans];
};

Complexity

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

Rotate String

check the input “goal” is contained in the concatination of the input “s” with itself and the both input length should same


/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
  return s === goal || (s + s).includes(goal) && s.length === goal.length;
};

Complexity

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

Sqrt(x)

Use binary search technique to with a range from 0 to x
Use the mid value to check if mid * mid is less than or equal to x


/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let left = 0, right = x, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const square = mid * mid;
 
    if (square <= x) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return ans;
};

Complexity

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

Pascal’s Triangle

Start with a pascal 2D array with default array with value 1. Use nested loops; one for row generation and other for values inside the each row.
Let each value of the current row be calculated from previous row values excluding 1st and last element. Prepend and append 1 to each row value (pattern says by default)


/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  var pascal = [[1]];
 
  for (var i = 1; i < numRows; i++) {
    pascal[i] = [1]; // 1st element of all the rows is 1
 
    for (var j = 1; j < i; j++) {
      pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
    }
 
    pascal[i][i] = 1; // last element of all the rows is 1
  }
  return pascal;
};

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)

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)

Longest Harmonious Subsequence

Find the frequency of each element
if map[key - 1] exist, then calculate max from maxLength,map previousvalue and current value


/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
  let map = {};
  for (let i of nums) {
    map[i] = (map[i] || 0) + 1;
  }
  let maxResultLength = 0;
  for (let [key, value] of Object.entries(map)) {
    if (map[key - 1]) {
      maxResultLength = Math.max(maxResultLength, map[key - 1] + value);
    }
  }
  return maxResultLength;
};

Complexity

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

Largest Odd Number in String

Find the lastOddNum in string and slice the string from 0 to lastOddNum index


/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function(num) {
    if(num & 1)
        return num;
    let lastOddNum = getLastOddNum(num);
    if(num.length>1){
        let i = num.lastIndexOf(lastOddNum)
        return num.slice(0,i+1);
    }
    return "";
};
 
function getLastOddNum(num){
    for(let i=num.length-1;i>=0;i--){
      if(num[i] & 1 === 1)
          return num[i];
    }
}

Complexity

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

Valid Palindrome

The program cleans the input string by keeping only alphanumeric characters and converting them to lowercase.
It then checks if the cleaned string is equal to its reverse to determine if it is a palindrome.


/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  let cleanedStr = '';
 
  // Helper function to check if a character is alphanumeric
  function isAlphanumeric(char) {
    return /^[a-zA-Z0-9]+$/.test(char);
  }
 
  // Build the cleaned string with only alphanumeric characters
  for (let char of s) {
    if (isAlphanumeric(char)) {
      cleanedStr += char.toLowerCase();
    }
  }
 
  // Compare the cleaned string with its reverse
  let reversedStr = cleanedStr.split('').reverse().join('');
  return cleanedStr === reversedStr;
};

Complexity

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

Longest Palindrome

The program counts the frequency of each character in the input string s and calculates the length of the longest palindrome that can be formed using those characters.
It adds 2 to the length for every pair of characters and includes a central character if the original string length is greater than the count of pairs.


/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
  let longestCount = 0;
  let charCountObj = {};
 
    for (const char of s) {
        charCountObj[char] = (charCountObj[char] || 0) + 1;
        if (charCountObj[char] % 2 == 0) longestCount += 2;
    }
    return s.length > longestCount ? longestCount + 1 : longestCount;
};

Complexity

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