In this article, I will show both of you methods of addressing a regular meeting style question. The main arrangement is more self-evident and less productive.
The second solution introduces a great problem-solving tool: frequency counter objects, which greatly improves the efficiency.
Here’s what you’ll gain from reading this article:
- A framework for approaching problems
- A very useful, highly performant problem solving technique
- An improved ability to analyse functions and improve performance
The problem
“Write a function called “squared” which takes two arrays. The function should return true if every value in the array has its value squared in the second array. The frequency of values must be the same.”
-- Your interviewer
From the outset, I will show you the "Gullible" method of tackling the issue – the more clear way that isn't effective.
I'll then, at that point show you an effective method to tackle the issue utilizing "recurrence counter articles". This is an extremely convenient method to have in your critical thinking tool compartment (your cerebrum).
Understanding the problem
Problem solving 101: Before we attempt to write a solution, it’s very important to understand the problem - to give some examples and the results we expect. We can then use these examples as tests to ensure our solution is working correctly.
Examples:
- Squared([1, 2, 3], [9, 1, 4]) // true
- Squared([1, 2, 3], [1, 4]) // false
- Squared([2, 2, 3], [4, 9, 9]) // false
Example 1 is true because:
- 12 = 1 (yep, that’s in array 2)
- 22 = 4 (yep, that’s in array 2)
- 32 = 9 (yep, that’s in array 2)
Example 2 is false because:
- 12 = 1 (yep, that’s in array 2)
- 22 = 4 (yep, that’s in array 2)
- 32 = 9 (nope, that's not in array 2)
Example 3 is false because:
- 22 = 4 (yep that’s in array 2)
- 22 = 4 (nope, there is only one 4 in array 2)
- 32 = 9 (yep, but we won’t even get to this check because the function returned false beforehand)
The “naïve” way
To start with, we check if the exhibits are not equivalent length. If not, we return bogus and escape the capacity early in light of the fact that the recurrence of qualities can't in any way, shape or form be something very similar.
Next, we loop over each number (num) in arr1. Inside the loop, we use indexOf() to look for the position of num2 in arr2. The value is assigned to the variable foundIndex.
If the value was not found, indexOf returns -1. So, we can check if foundIndex = -1, and return false if so.
If all is good, we move on and remove this value from arr2 using the splice() method. This ensures the frequency of values in both arrays are the same.
After looping over each number, and all the checks pass, we can return true.
function squared(arr1, arr2) {
if (arr1.length !== arr2.length) return false
for (let num of arr1) {
let foundIndex = arr2.indexOf(num ** 2)
if (foundIndex === -1) return false
arr2.splice(foundIndex, 1)
}
return true
}
Performance:
This calculation has a Big O(n2) in light of the fact that we circle over each and every thing in the primary cluster, then, at that point inside this circle, we are circling over each and every thing in the subsequent exhibit (with indexOf()) even from a pessimistic standpoint case.
Assuming the clusters are of length n, the quantity of activities will be n * n = n2. Subsequently Big O(n2).
Presently, this isn't exactly evident on the grounds that the subsequent cluster becomes more limited on each circle, so on normal we will just circle over a large portion of the subsequent exhibit (0.5n). The Big O will be of n * 0.5n = 0.5n2. Be that as it may, Big O takes a gander at 10,000 foot view stuff, and as the information approaches limitlessness, the 0.5 will be inconsequential thus we rearrange to Big O(n2).
A smarter way – Frequency Counter Objects – Big O(n)
What are Frequency Counter Objects?
Recurrence counters are objects that count things up. Here's two instances of where they would be helpful:
- The occasions a person shows up in a string
- The occasions a number shows up in an exhibit
Utilizing recurrence counters can likewise fundamentally work on the presentation of a calculation, as it can frequently eliminate the need to utilize settled for-circles.
This is what the recurrence counter article for [1, 2, 3, 4, 3] would resemble:
let frequencyCounter = {
1: 1,
2: 1,
3: 2,
4: 1,
}
All the numbers appear once, apart from 3, which appears twice.
To make a recurrence counter item, we circle over the exhibit being referred to. We then, at that point make a key and give it a worth of the current worth + 1, or on the other hand in case it's the first occasion when we've experienced this number, frequencyCounter[num] will be indistinct thus we initialise the worth to 1.
I utilized two for… of circles as I felt it was simpler to peruse, however it should likewise be possible with only one for-circle.
The recurrence counter articles can then measure up. We first check if each key squared from recurrence counter 1 is a key in recurrence counter 2. If not, return bogus.
Then, we check if the frequencies (values) are equivalent. If not, return bogus.
What's more, on the off chance that we overcome this solid, we get to the base and bring valid back.
function squared(arr1, arr2) {
if (arr1.length !== arr2.length) return false
let frequencyCounter1 = {}
let frequencyCounter2 = {}
// Create frequencyCounter1
for (let num of arr1) {
frequencyCounter1[num] = frequencyCounter1[num] + 1 || 1
}
// Create frequencyCounter2
for (let num of arr2) {
frequencyCounter2[num] = frequencyCounter2[num] + 1 || 1
}
// Compare frequency counters
for (let key in frequencyCounter1) {
if (!(key ** 2 in frequencyCounter2)) return false
if (frequencyCounter1[key] !== frequencyCounter2[key ** 2]) return false
}
return true
}
Performance
- To create frequencyCounter1, we loop over all the numbers in arr1 => n loops
- Same for frequencyCounter2 => n loops
- To compare the frequency counters, we loop over all the keys in frequencyCounter1 => at worst case, n loops
Total = n + n + n = 3n
Resulting in a Big O(n) – linear time complexity.
Much better than our first effort of with Big O(n2) – quadratic time complexity.
#viastudy
.gif)
0 Comments