DSA

Application 📱 and solving of technical interview Data 🔡 Structure 🏛️ and Algorithm questions ❓in Javascript.

Introduction

It’s been a journey on the third series of data structure and algorithm. We’ve been through all or almost all of the basic requirements to tackle real life algorithm questions.

Having gone through my previous articles? Let’s get coding enough talking.

Today we’re going to be solving real technical interview questions in Javascript from leet code questions.

1. Using Merge Sort Algorithm : Merge Sort Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

Follow up:

Can you come up with an algorithm that runs in O(m + n) time?

Read this question properly and attempt to solve it. By trying to write a psuedo algorithm before solving it with code as that’s the most important part of solving DSA questions.

Aiit…Let’s get to the solution.

To solve the given problem, we can use the merge sort algorithm. Since the input arrays nums1 and nums2 are already sorted, we can take advantage of this fact to efficiently merge them into a single sorted array. Here’s the JavaScript solution:

function merge(nums1, m, nums2, n) {
  let i = m - 1; // Index of last element in nums1
  let j = n - 1; // Index of last element in nums2
  let k = m + n - 1; // Index of last position in nums1

  // Merge nums1 and nums2 starting from the end
  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i];
      i--;
    } else {
      nums1[k] = nums2[j];
      j--;
    }
    k--;
  }

  // If there are remaining elements in nums2, append them to nums1
  while (j >= 0) {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
}

Explanation:

The merge function takes four parameters: nums1, m, nums2, and n. nums1 is the target array that will store the merged result, m is the number of elements in nums1, nums2 is the array to be merged, and n is the number of elements in nums2.

We initialize three pointers, i, j, and k, to keep track of the current positions in nums1, nums2, and the merged result respectively.

Starting from the end of the arrays, we compare the elements at indices i and j. If the element in nums1 is greater than the element in nums2, we place it in the correct position in nums1 at index k and decrement i. Otherwise, if the element in nums2 is greater, we place it in nums1 at index k and decrement j. We continue this process until we reach the beginning of either nums1 or nums2.
After merging all the elements from nums2 into nums1, if there are remaining elements in nums2 but none left in nums1, we iterate through the remaining elements of nums2 and append them to nums1 in the correct positions.

By following this approach, we merge the two sorted arrays nums1 and nums2 into a single sorted array stored in m, as required.

Example usage:

In the example above, we have nums1 as [1, 3, 5, 0, 0, 0] with m as 3, and nums2 as [2, 4, 6] with n as 3. After calling the merge function, nums1 is updated to [1, 2, 3, 4, 5, 6], which is the merged result of both arrays in non-decreasing order.

The time complexity of this algorithm is O(m + n) since we iterate through both nums1 and nums2 once. We use three pointers to track the positions, avoiding the need for extra space.

This approach is efficient as it avoids creating a separate array for the merged result, and it takes advantage of the fact that both input arrays are already sorted. By merging the arrays in-place, we meet the requirements of the problem statement.

The merge function can be used to merge two sorted arrays efficiently, and it provides a solution to the problem of merging nums1 and nums2 into a single sorted array stored in nums1 while considering the given constraints.

Note: It’s important to ensure that nums1 has sufficient space to accommodate the merged result. The length of nums1 should be m + n to accommodate both the original elements and the additional space for merging.

2. Using Linked List: Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Follow up:

Could you do it in O(n) time and O(1) space?

To solve the given problem, we can use a two-pointer approach along with some linked list manipulation. Here’s the JavaScript solution:

function isPalindrome(head) {
  if (!head || !head.next) {
    return true; // An empty list or a single node is considered a palindrome
  }

  // Find the middle of the linked list using the slow and fast pointer technique
  let slow = head;
  let fast = head;

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Reverse the second half of the linked list
  let prev = null;
  let curr = slow.next;

  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Compare the reversed second half with the first half of the linked list
  let p1 = head;
  let p2 = prev;

  while (p2) {
    if (p1.val !== p2.val) {
      return false; // Values mismatch, not a palindrome
    }
    p1 = p1.next;
    p2 = p2.next;
  }

  return true; // All values match, it is a palindrome
}

Explanation:

The isPalindrome function takes the head of a singly linked list as input and returns true if the linked list is a palindrome, or false otherwise.

We handle some special cases first:

• If the linked list is empty or contains only one node, it is considered a palindrome by definition, so we return true.
• For a linked list with two or more nodes, we use the slow and fast pointer technique to find the middle node. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Next, we reverse the second half of the linked list. We start from the node next to the middle and reverse the pointers to create a new reversed linked list.

Finally, we compare the reversed second half with the first half of the linked list. We use two pointers, p1 and p2, starting from the head and the reversed second half, respectively. We traverse both halves simultaneously, comparing the values of each pair of nodes. If any pair of values mismatch, we return false, indicating that the linked list is not a palindrome. If all pairs of values match, we return true, indicating that the linked list is a palindrome.

The time complexity of this algorithm is O(n) since we iterate through the linked list only once. We reverse the second half in-place without using any additional space, meeting the O(1) space complexity requirement.

This solution efficiently checks whether a linked list is a palindrome by utilizing the characteristics of a palindrome and manipulating the pointers of the linked list.

3. Using hashmap: First unique character in a string

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

Constraints:

• 1 <= s.length <= 105
• s consists of only lowercase English letters.

To solve the given problem, we can utilize a hashmap to store the frequency of each character in the string. Then, we can iterate through the string to find the first character with a frequency of 1. Here’s the JavaScript solution:

function firstUniqChar(s) {
  const charCount = new Map();

  // Store the frequency of each character in the hashmap
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }

  // Iterate through the string to find the first non-repeating character
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (charCount.get(char) === 1) {
      return i; // Found the first non-repeating character, return its index
    }
  }

  return -1; // No non-repeating character found, return -1
}

Explanation:

The firstUniqChar function takes a string s as input and returns the index of the first non-repeating character in the string. If there is no non-repeating character, it returns -1.

We use a hashmap, charCount, to store the frequency of each character in the string. The keys of the hashmap are the characters, and the values are their corresponding frequencies.

First, we iterate through the string to populate the hashmap. For each character, we check if it already exists as a key in the hashmap. If it does, we increment its frequency by 1. If it doesn't, we add it to the hashmap with a frequency of 1.

Next, we iterate through the string again to find the first non-repeating character. For each character, we check its frequency in the hashmap. If the frequency is 1, we have found the first non-repeating character, so we return its index.

If we complete the loop without finding any non-repeating character, we return -1 to indicate that no such character exists in the string.

The time complexity of this algorithm is O(n), where n is the length of the string. We iterate through the string twice, once to populate the hashmap and once to find the first non-repeating character. The space complexity is O(1) since the hashmap can have a maximum of 26 entries (for lowercase English letters).

This solution efficiently finds the first non-repeating character in the string by utilizing a hashmap to store the frequencies of the characters and iterating through the string to identify the desired character.

4. Remove duplicates from sorted array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

To solve the given problem, we can utilize a two-pointer approach to remove duplicates in-place. Here’s the JavaScript solution:

function removeDuplicates(nums) {
  if (nums.length === 0) {
    return 0; // Empty array has no duplicates
  }

  let uniqueIndex = 0; // Pointer to track the position of unique elements

  // Iterate through the array starting from the second element
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] !== nums[uniqueIndex]) {
      uniqueIndex++;
      nums[uniqueIndex] = nums[i]; // Move the unique element to its correct position
    }
  }

  return uniqueIndex + 1; // Return the count of unique elements
}

Explanation:

The removeDuplicates function takes an integer array nums as input and returns the number of unique elements in the array after removing duplicates.

We handle a special case first:

• If the array is empty, there are no duplicates, so we return 0.

Next, we use a two-pointer approach to remove duplicates in-place. We have a pointer uniqueIndex that tracks the position of unique elements. Initially, it points to the first element in the array.

We iterate through the array starting from the second element. For each element, if it is different from the element at the uniqueIndex, it means we have found a new unique element. We increment the uniqueIndex and move the new unique element to its correct position.

By the end of the iteration, all duplicates are removed, and the first uniqueIndex + 1 elements in the array are the unique elements in their original order.

We return uniqueIndex + 1 as the count of unique elements.

The time complexity of this algorithm is O(n), where n is the length of the input array nums. We iterate through the array once, comparing elements and moving unique elements to their correct positions. The space complexity is O(1) since we modify the array in-place without using any additional space.

This solution efficiently removes duplicates from a sorted array in-place while maintaining the relative order of the elements and returns the count of unique elements.

5. Kadane’s Algorithm: Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

To solve the given problem, we can use the Kadane’s algorithm, also known as the Maximum Subarray Sum algorithm. This algorithm efficiently finds the subarray with the largest sum. Here’s the JavaScript solution:

function maxSubArray(nums) {
  let currentSum = nums[0]; // Initialize the current sum as the first element
  let maxSum = nums[0]; // Initialize the maximum sum as the first element

  // Iterate through the array starting from the second element
  for (let i = 1; i < nums.length; i++) {
    // Compare the current element with the sum of the current element and previous subarray
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    // Update the maximum sum if the current sum is greater
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum; // Return the maximum subarray sum
}

Explanation:

The maxSubArray function takes an integer array nums as input and returns the sum of the subarray with the largest sum.

We initialize two variables: currentSum and maxSum to the first element of the array. These variables represent the current sum and the maximum sum found so far.

We iterate through the array starting from the second element. For each element, we compare the current element with the sum of the current element and the previous subarray. We choose the maximum between the current element itself and the sum of the current element and the previous subarray.
At each iteration, we update the currentSum to the maximum value between the current element and the sum of the current element and the previous subarray. We also update the maxSum to the maximum value between the current maxSum and the currentSum.

By the end of the iteration, maxSum will hold the sum of the subarray with the largest sum.

The time complexity of this algorithm is O(n), where n is the length of the input array nums. We iterate through the array once, updating the currentSum and maxSum. The space complexity is O(1) since we only use a constant amount of additional space to store the currentSum and maxSum.

This solution efficiently finds the subarray with the largest sum using Kadane’s algorithm, making it a highly effective approach for solving this problem.

I hope this examples are enough to master a bit of technicalities to approach solving a technical interview algorithm question.

If you enjoy this drop a like or comment. Happy coding 💻!