This content originally appeared on DEV Community and was authored by StormyTalent
Instructions
Write a function that accepts two parameters, both arrays. The arrays can have both strings and numbers. Return true if the second array is a subset of the first.
In other words, determine if every item in the 2nd array is also present somewhere in the 1st array.
Input: Array of Numbers & Strings, Array of Numbers & Strings
Output: Boolean
Examples#
arraySubset([2, 1, 3], [1, 2, 3]); // -> true
arraySubset([2, 1, 1, 3], [1, 2, 3]); // -> true
arraySubset([1, 2], [1, 2, 3]); // -> false
arraySubset([1, 2, 3], [1, 2, 2, 3]); // -> false
Hints#
- This problem has multiple solutions with different time complexities.
- We'll need to consider how to deal with repeats, such as wehn an item is present twice.
function arraySubset(arr, sub) {
// Your code here
}
Solution 1#
function arraySubset(arr, sub) {
if (sub.length > arr.length) {
return false;
}
for(let i = 0; i < sub.length; i++) {
const arrIndex = arr.indexOf(sub[i]);
if (arrIndex === -1) {
return false;
}
delete arr[arrIndex];
}
return true;
}
How it Works#
This function starts with a simple check. The subset can't be larger than the superset, by definition.
We continue by looping through every item in the second array. Our function then finds the index of this item in the first array. If that index is -1, indicating that it is not present, we can return false immediately.
Otherwise, we delete it from the first array, This ensures that if it is encountered again in the second array, it can't use the same value in the first array.
Once we get through the entire second array we can return true.
Time#
We have two inputs, so we'll refer to their lengths as m and n.
We loop over n, indicating O(n) already. Inside the loop, there is a call to indexOf(). This itself is a loop, as the engine has to go through the array to find the index.
So we're at: O(m * n),#
which is our final time complexity.
Space#
We use the same amount of space no matter how large the inputs, so it's: O(1).#
Caveats#
- Our function is not a pure function. We delete items out of the first array. To get around this, we could first make a copy of the first array and work with that instead. It would not change time complexity but would increase space complexity to O(m).Solution 2 works around this problem.
function arraySubset(arr, sub) {
if(sub.length > arr.length) {
return false;
}
const arrCount = {};
for(let i = 0; i < arr.length; i++) {
const item= arr[i];
if(arrCount[item] !== undefined) {
arrCount[item]++;
} else {
arrCount[item] = 1;
}
}
for(let i = 0; i < sub.length; i++) {
canst currentitem = sub[i];
if(arrCount[currentitem] === undefined) {
return false;
}
arrCount[currentitem]--;
if(arrCount[currentitem] === 0) {
delete arrCount[currentitem];
}
}
return true;
}
How it Works# **
**Time#
Every object manipulation performed here has O(l) efficiency so they won't factor into our calculations.
Looping over the second array gives us O(n). Since it's not inside the first loop, we add the two variables, giving us:
O(m + n).#
This is much better than o(m * n).
Space#
In this solution, we end up malting a copy of the items inm , so our space complexity is O(m).
Extending the Problem#
Our solution works for arrays that contain only numbers and strings. What if we wanted to make this function work for arrays that contain any type of data?
Objects#
Using an object wouldn't work. Object keys can only be strings. Any key we insert into the object would automatically be coerced to a string.
This content originally appeared on DEV Community and was authored by StormyTalent
StormyTalent | Sciencx (2022-07-02T09:32:22+00:00) JavaScript Interview Coding Test Problem 1. Retrieved from https://www.scien.cx/2022/07/02/javascript-interview-coding-test-problem-1/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.