Day 56: 03_isSubsetOf

1. TIL (Today I Learned)

I solved an algorithm problem which gave a base and a sample array as an input variable and required me to come up with an algorithm that can check if the sample array is a subset of the base array.

I failed several times so I decided to check out the given answer code to study how I should've designed the algorithm.

Below is the final code:

const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  const findItemInSortedArr = (item, arr, from) => {
    for (let i = from; i < arr.length; i++) {
      if (item === arr[i])
        return i;
      else if (item < arr[i]) 
       return -1;
      }
     return -1;
  };

    let baseIdx = 0;
    for (let i = 0; i < sample.length; i++) {
      baseIdx = findItemInSortedArr(sample[i], base, baseIdx) 
      if (baseIdx === -1) {
        return false;
      }
    }
  return true;
};

I first tried to use for loops to iterate through the sample array and check if it is located inside the base sample because that would mean the sample array is a subset of the base array. However, the question was not just so simple. It gave arrays that had the same numbers inside both the base and sample array but in different orders. Therefore my beginning code would fail to track on to if the sample was a subset of the base. Secondly, the question required an advanced case where the sample array's length was 70,000. The code checked failed due to time exceeding because even if my beginning code was able to find out if time was plenty, the question did not allow such code to pass. Therefore when I checked on the reference code, I learned that the given way was to use sort to sort both sample and base arrays as ascending orders. Then, compare the first index's value of both arrays and if it was not same the code was designed to return a false right away. This is because if sample array was a subset of the base array, when sorted in ascending order, the time taken to find the same value inside the base array will decrease significantly.

2. 3 Things to be Thankful For

  1. Thankful for allowing God to think about you.
  2. Thankful for being able to not give up and just hold on to it.
  3. Sorry for just relying on myself only.

3. Ideas and Things to Think About.

  1. I started all this just because I wanted to become ready for the future and be successful and not be a loser. However, the reason I had the eager to do all this was mostly me and 20 percent relying on God. I would like to use today to admit I suck and I cannot ever go through all this things alone. Please God, be with me and just guide me through your plans please take the wheel, God.

좋은 웹페이지 즐겨찾기