I recently applied for a Junior software engineer position at a big bank and I was given this question as a challenge with another question with a time limit of two hours and this question was labeled as the easy question. I wasn't able to do it but I'm curious if anyone could provide me with a solution on how to go about solving this particular problem preferably using javascript. I would greatly appreciate anyone who can give me an answer to this question, as I am keen to learn and become a better programmer.

Thank you for your help in advance.

Question Description:
Given two random arrays s and t, they must be compared using the function checker to return 'YES' if they are similar or return 'NO' if they are not similar.

Following are the criteria for the array to be similar and not similar:

1)Scenario for arrays being similar:

s = [10,20,10,20,-10,10,10,-40,-20] t = [20,10,-30,30,20,20,-10,-20,-30]

s and t have to be two arrays which are equal in length and the difference between how many times certain common elements appear in each array must be equal to or less than 3. In this particular scenario the element 10 occurs in s 4 times and in the array t it occurs 1 time, therefore, the difference between its occurences in both the array is 4-1= 3, similarly 20 occurs in s a total of 2 times and a total of 3 times in t, therefore the difference of the occurences of 20 between the two array is 3-2 = 1, where 1 < 3.

Also, the length of both the arrays is the same which is 8(array starts from index 0) in this case for both the arrays, therefore the arrays s and t are similar in this case are the same and hence, 'YES' must be returned by the function.

2)Scenario where the arrays are not the same:

s = [10,20,10,20,-10,10,10,30,-20, 10, 20, 10] t = [20,10,30,30,20,20,-10,-20,30,30,30]

In this case 10 occurs 6 times in s and 1 times in t, therefore 6-1 = 5, so 5>3, similarly 30 occurs 5 times in t and 1 times in s, therefore, 5-1 = 4, 4>3 and the length of the arrays aren't the same, therefore these arrays aren't similar and 'NO' must be returned.

The time limit to solve this question is 1 hour.

function checker(s,t)
{
 // Write your code here
}

The way I approached this question was to first sort the arrays first in increasing order and then check with an if condition if whether they were similar in length and then go about trying to check which numbers were occuring multiple times etc in the arrays itself.

CodePudding user response：

1. check length equality
2. construct an empty hashmap<T, int>
3. iterate through the first list adding 1 for each time each value is involved
4. iterate through the second list, subtracting 1 as above
5. iterate through each value of the hashmap, if any number is > 3 or < -3, return false
6. return true if not outside of function yet

true/false can be substituted for YES/NO

This solution is in O(n) time and O(n) space.

function checker(s, t) {
  if (s.length !== t.length) return 'NO';

  const occurances = {};

  for (const val of s) {
    if (!occurances[val]) occurances[val] = 1;
    else occurances[val]  ;
  }
  
  for (const val of t) {
    if (!occurances[val]) occurances[val] = -1;
    else occurances[val]--;
  }
  
  for (const val of Object.values(occurances)) {
    if (val > 3 || val < -3) return 'NO';
  }
  
  return 'YES';
}

console.log(checker([10, 20, 10, 20, -10, 10, 10, -40, -20], [20, 10, -30, 30, 20, 20, -10, -20, -30]));
console.log(checker([10, 20, 10, 20, -10, 10, 10, 30, -20, 10, 20, 10], [20, 10, 30, 30, 20, 20, -10, -20, 30, 30, 30]));

CodePudding user response：

You could check the length first and exit early if not equal.

Then count each value, up for s and down for t.

Return the check of each value.

function checker(s, t) {
   if (s.length !== t.length) return 'NO';
   const
       count = o => d => v => counts[v] = (counts[v] || 0)   d,
       counts = {},
       add = count(counts);
   
   s.forEach(add(1));
   t.forEach(add(-1));

   return Object
           .values(counts)
           .every(v => Math.abs(v) <= 3)
       ? 'YES'
       : 'NO';
}

console.log(checker([10, 20, 10, 20, -10, 10, 10, -40, -20], [20, 10, -30, 30, 20, 20, -10, -20, -30]));
console.log(checker([10, 20, 10, 20, -10, 10, 10, 30, -20, 10, 20, 10], [20, 10, 30, 30, 20, 20, -10, -20, 30, 30, 30]));

CodePudding user response：

Create a map that keeps track of the counts of each array, and then see which ones are off by > 3.

function checker(s, t) {
   if (s.length !== t.length) return 'NO';
   function makeCountMap(arr) {
     return arr.reduce((p, c) => {
       if (!p[c]) {
          p[c] = 0;
       }
       p[c]  ;
       return p;
     }, {});
   }
   const sCountMap = makeCountMap(s);
   const tCountMap = makeCountMap(t);

   return Object
           .entries(sCountMap)
           .every(entry => Math.abs(entry[1] - tCountMap[entry[0]] || 0) <= 3)
       ? 'YES'
       : 'NO';
}

console.log(checker([10, 20, 10, 20, -10, 10, 10, -40, -20], [20, 10, -30, 30, 20, 20, -10, -20, -30]));
console.log(checker([10, 20, 10, 20, -10, 10, 10, 30, -20, 10, 20, 10], [20, 10, 30, 30, 20, 20, -10, -20, 30, 30, 30]));