INTERVIEW PROBLEMS - rs-hash/Senior GitHub Wiki
1. Merge Sorted Array
To merge the two sorted arrays nums1 and nums2 into nums1 in non-decreasing order, we can utilize a two-pointer technique that runs in O(m + n) time complexity. The idea is to start from the end of both arrays and fill nums1 from the end to the beginning. This approach ensures that we don't overwrite any elements in nums1 that we haven't yet processed.
Here's how you can implement this in JavaScript:
function merge(nums1, m, nums2, n) {
// Pointers for nums1 and nums2
let p1 = m - 1;
let p2 = n - 1;
// Pointer for the end of nums1
let p = m + n - 1;
// Iterate while there are elements to be compared in nums1 and nums2
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// If there are remaining elements in nums2, copy them
while (p2 >= 0) {
nums1[p] = nums2[p2];
p--;
p2--;
}
}
2. Remove Element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val 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 elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.
var removeElement = function(nums, val) {
let k = 0; // Initialize the pointer for the next position of non-val element
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== val) {
nums[k] = nums[i]; // Place the non-val element at the position of k
k++; // Increment k
}
}
return k; // k is the number of elements that are not equal to val
};
// Example usage:
let nums1 = [3, 2, 2, 3];
let val1 = 3;
let k1 = removeElement(nums1, val1);
console.log(k1); // Output: 2
console.log(nums1.slice(0, k1)); // Output: [2, 2]
let nums2 = [0, 1, 2, 2, 3, 0, 4, 2];
let val2 = 2;
let k2 = removeElement(nums2, val2);
console.log(k2); // Output: 5
console.log(nums2.slice(0, k2)); // Output: [0, 1, 3, 0, 4]
3. 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.
var removeDuplicates = function(nums) {
if (nums.length === 0) return 0; // Edge case for empty array
let i = 0; // Pointer to the position of the last unique element
for (let j = 1; j < nums.length; j++) {
if (nums[j] !== nums[i]) {
i++; // Move the pointer i forward
nums[i] = nums[j]; // Replace the element at i with the current unique element
}
}
return i + 1; // Number of unique elements
};
// Example usage:
let nums1 = [1, 1, 2];
let k1 = removeDuplicates(nums1);
console.log(k1); // Output: 2
console.log(nums1.slice(0, k1)); // Output: [1, 2]
let nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
let k2 = removeDuplicates(nums2);
console.log(k2); // Output: 5
console.log(nums2.slice(0, k2)); // Output: [0, 1, 2, 3, 4]
4. Remove Duplicates from Sorted Array II
solve this problem efficiently in JavaScript, you can use a two-pointer technique to ensure each unique element appears at most twice while maintaining the relative order of elements. Here's the step-by-step solution:
Initialize a pointer to keep track of the position to insert the next valid element. Iterate through the array and use a counter to keep track of occurrences of each element. If an element occurs at most twice, place it at the insertion position and increment the insertion pointer. Continue this process for all elements in the array. Here’s how you can implement this:
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let insertPos = 1; // Pointer for the position to insert the next valid element
let count = 1; // To keep track of occurrences of the current element
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) {
count++;
} else {
count = 1; // Reset count for a new element
}
// If count is less than or equal to 2, we can place the element
if (count <= 2) {
nums[insertPos] = nums[i];
insertPos++;
}
}
return insertPos; // Length of the array with duplicates removed
}
// Example usage:
let nums1 = [1, 1, 1, 2, 2, 3];
console.log(removeDuplicates(nums1)); // Output: 5
console.log(nums1); // Output: [1, 1, 2, 2, 3, ...]
let nums2 = [0, 0, 1, 1, 1, 1, 2, 3, 3];
console.log(removeDuplicates(nums2)); // Output: 7
console.log(nums2); // Output: [0, 0, 1, 1, 2, 3, 3, ...]
5. Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3] Output: 3 Example 2:
Input: nums = [2,2,1,1,1,2,2] Output: 2
Constraints:
n == nums.length 1 <= n <= 5 * 104 -109 <= nums[i] <= 109
function majorityElement(nums) {
nums.sort((a, b) => a - b);
return nums[Math.floor(nums.length / 2)];
}
// Example usage:
console.log(majorityElement([3, 2, 3])); // Output: 3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // Output: 2
other solution
var majorityElement = function(nums) {
let count = 0;
let candidate = null;
for (let num of nums) {
if (count === 0) {
candidate = num;
}
count += (num === candidate) ? 1 : -1;
}
return candidate;
};
6. Rotate Array
Simple Solution Using Array Reverse One of the efficient ways to rotate the array in-place with O(1) O(1) extra space is by reversing parts of the array. Here's the step-by-step approach:
- Reverse the entire array.
- Reverse the first k elements.
- Reverse the remaining n−k elements.
Why This Works
When you reverse the entire array, the elements are in the reverse order of what they should be after rotation. By reversing the first k elements and then the remaining n−k elements, you place each part of the array in the correct order.
function rotate(nums, k) {
const n = nums.length;
k = k % n; // In case k is larger than the array length
// Helper function to reverse a portion of the array
function reverse(start, end) {
while (start < end) {
// Swap elements using a temporary variable
var temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
// Step 1: Reverse the entire array
reverse(0, n - 1);
// Step 2: Reverse the first k elements
reverse(0, k - 1);
// Step 3: Reverse the remaining n - k elements
reverse(k, n - 1);
}
// Example usage:
let nums1 = [1, 2, 3, 4, 5, 6, 7];
rotate(nums1, 3);
console.log(nums1); // Output: [5, 6, 7, 1, 2, 3, 4]
let nums2 = [-1, -100, 3, 99];
rotate(nums2, 2);
console.log(nums2); // Output: [3, 99, -1, -100]
7. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Solution
To solve this problem efficiently, you can use a single-pass approach with a greedy algorithm. The idea is to keep track of the minimum price encountered so far and calculate the potential profit at each day by subtracting the current price from this minimum price. This allows you to determine the maximum profit that can be achieved in a single pass through the array.
Here's the step-by-step approach:
- Initialize two variables: minPrice to a very large value (Infinity) and maxProfit to 0.
- Iterate through the array of prices.
- For each price, update minPrice to be the minimum of the current minPrice and the current price.
- Calculate the potential profit by subtracting the current minPrice from the current price.
- Update maxProfit to be the maximum of the current maxProfit and the potential profit.
- After iterating through all prices, return the maxProfit.
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
const profit = prices[i] - minPrice;
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
// Example usage:
const prices1 = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices1)); // Output: 5
const prices2 = [7, 6, 4, 3, 1];
console.log(maxProfit(prices2)); // Output: 0
8. Best Time to Buy and Sell Stock II
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
function maxProfit(prices) {
let maxProfit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
// Example usage:
const prices1 = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices1)); // Output: 7
const prices2 = [1, 2, 3, 4, 5];
console.log(maxProfit(prices2)); // Output: 4
const prices3 = [7, 6, 4, 3, 1];
console.log(maxProfit(prices3)); // Output: 0
9. Jump Game
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Solution
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) {
return false;
}
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) {
return true;
}
}
return true;
}
// Example usage:
const nums1 = [2, 3, 1, 1, 4];
console.log(canJump(nums1)); // Output: true
const nums2 = [3, 2, 1, 0, 4];
console.log(canJump(nums2)); // Output: false