Frequency Queries hackerrank [closed]

Question

This is the problem:

You are given queries. Each query is of the form two integers described below: - 1: Insert x in your data structure. - 2: Delete one occurrence of y from your data structure, if present. - 3: Check if any integer is present whose frequency is exactly. If yes, print 1 else 0.

The queries are given in the form of a 2-D array query of size q where queries[i][0] contains the operation, and queriesi contains the data element contains the operation and contains the data element. For example, you are given array. [[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]] The output=[0,1]

The question can be found here; https://www.hackerrank.com/challenges/frequency-queries/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

My code does not work some of the cases on hackerrank for some reason but I can't figure out why. It is not caused by timeout or compiler error. It gives a 'wrong answer' in the compiler but when I try to test my code with the same input on VSCode, it actually works. It's the first time I am encountering something like this. If I would be more specific, I tested my code manually against this input

[1, 3], [1, 38], [2, 1], [1, 16], [2, 1], [2, 2], [1, 64], [1, 84], [3, 1], [1, 100], [1, 10], [2, 2], [2, 1], [1, 67], [2, 2], [3, 1], [1, 99], [1, 32], [1, 58], [3, 2]

and it returns [1,1,0] on vs code when I try it. However, on hackerrank it says the wrong answer even though it expects the same result. Any idea what's going on?

Here is my code in javascript;

function freqQuery(queries) {
  let store = [];
  let output = [];
  let obj = {};
  let checkFreq = false;

  for (let i = 0; i < queries.length; i++) {
    let query = queries[i];

    if (query[0] === 1) {
      store.push(query[1]);
    } else if (query[0] === 2) {
      let index = store.indexOf(query[1]);
      if (index > -1) {
        store.splice(index, 1);
      }
    } else {
      let freq = query[1];
      if (store.length === 0) {
        output.push(0);
      } else {
        obj = charToObj(store);
        for (let number in obj) {
          if (obj[number] === freq) {
            checkFreq = true;
            break;
          } else {
            checkFreq = false;
          }
        }
        if (checkFreq) {
          output.push(1);
        } else {
          output.push(0);
        }
      }
    }
  }

  return output;
}

function charToObj(arr) {
  let obj = {};
  for (let i = 0; i < arr.length; i++) {
    if (obj[arr[i]]) {
      obj[arr[i]] += 1;
    } else {
      obj[arr[i]] = 1;
    }
  }
  return obj;
}

Answer 1

Optimizations

You should think of your algorithm as a black box. As long as input and output match, internally the function has not to reproduce the textual representation of the problem.

With this in mind you can simplify your code. You also have an approach already in the charToObj function. I would use this to solve the whole problem:

• create a map
• store values in that map and increase their amount, when they reappear
• decrease amount, if necessary
• test the map for given frequencies

This has a few advantages:

• shorter code, easier to follow
• no helper function necessary
• no need to call splice
• no inner loops anymore
• no need to build obj over and over again

The new functions could look like this:

function freqQuery(queries) {
    const frequencies = [];
    const result = [];

    for (const query of queries) {
        const action = query[0];
        const value = query[1];

        if (action === 1) {
            if (typeof frequencies[value] === 'undefined') {
                frequencies[value] = 1;
            } else {
                ++frequencies[value];
            }
        }

        if (action === 2) {
            if (frequencies[value]) {
                --frequencies[value];
            }
        }

        if (action === 3) {
            result.push(frequencies.indexOf(value) === -1 ? 0 : 1);
        }
    }

    return result;
}

console.log(
    freqQuery([[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]]),
    freqQuery([[3, 4], [2, 1003], [1, 16], [3, 1]]),
    freqQuery([[1, 3], [2, 3], [3, 2], [1, 4], [1, 5], [1, 5], [1, 4], [3, 2], [2, 4], [3, 2]]),
    freqQuery([[1, 5], [1, 6], [3, 2], [1, 10], [1, 10], [1, 6], [2, 5], [3, 2]]),
    freqQuery([[1, 3], [1, 38], [2, 1], [1, 16], [2, 1], [2, 2], [1, 64], [1, 84], [3, 1], [1, 100], [1, 10], [2, 2], [2, 1], [1, 67], [2, 2], [3, 1], [1, 99], [1, 32], [1, 58], [3, 2]]),
);

---

Instead of the three if-statements you could also use switch:

switch(action) {
    case 1: …
    case 2: …
    case 3: …
}

Small improvements

The bottleneck in this functions is indexOf. An alternative is using .includes():

if (action === 3) {
   result.push(frequencies.includes(value) ? 1 : 0);
}

This is faster for all test cases I ran in Chrome and Node.js. It is sometimes faster but can be slower depending highly on the input in Safari and Firefox.

Here's a test on jsfiddle.

Taking it one step further

So, the bottleneck is still the expensive test in case 3:

frequencies.includes(value)

Let's get rid of this by keeping track of the current frequencies ourselves. The main improvement is, that we finally will only have to check whether a given index evaluates to true:

if (action === 3) {
    result.push(frequencyTracker[value] > 0 ? 1 : 0);
}

We introduce a second array frequencyTracker, which is filled with the amount each frequency occurs. I've used the ternary operator simply to shorten the code.

function freqQuery(queries) {
    const frequencies = [];
    const frequencyTracker = [];
    const result = [];

    for (const query of queries) {
        const action = query[0];
        const value = query[1];
        let index;

        if (action === 1 || action === 2) {
            index = frequencies[value];
            frequencyTracker[index] ? --frequencyTracker[index] : null;
        }

        if (action === 1) {
            typeof frequencies[value] === 'undefined' ? frequencies[value] = 1 : ++frequencies[value];
        }

        if (action === 2 && frequencies[value]) {
            --frequencies[value];
        }

        if (action === 1 || action === 2) {
            index = frequencies[value];
            frequencyTracker[index] ? ++frequencyTracker[index] : frequencyTracker[index] = 1;
        }

        if (action === 3) {
            result.push(frequencyTracker[value] > 0 ? 1 : 0);
        }
    }

    return result;
}

console.log(
    freqQuery([[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]]),
    freqQuery([[3, 4], [2, 1003], [1, 16], [3, 1]]),
    freqQuery([[1, 3], [2, 3], [3, 2], [1, 4], [1, 5], [1, 5], [1, 4], [3, 2], [2, 4], [3, 2]]),
    freqQuery([[1, 5], [1, 6], [3, 2], [1, 10], [1, 10], [1, 6], [2, 5], [3, 2]]),
    freqQuery([[1, 3], [1, 38], [2, 1], [1, 16], [2, 1], [2, 2], [1, 64], [1, 84], [3, 1], [1, 100], [1, 10], [2, 2], [2, 1], [1, 67], [2, 2], [3, 1], [1, 99], [1, 32], [1, 58], [3, 2]]),
);

This doesn't look as elegant as the naive solution, but it's way faster. It passes all test cases on HackerRank as well.

Explanation

As requested in the comments, here's a an example to explain how this works in detail:

Before we begin, we create an empty array, which we will become a sparse array later.

Now we run through all queries:

If the action is 1 we set or increase our counter at the given index.

[1, 2] → [undefined, undefined, 1] + [undefined, 1]
[1, 4] → [undefined, undefined, 1, undefined, 1] + [undefined, 2]
[1, 4] → [undefined, undefined, 1, undefined, 2] + [undefined, 1, 1]

If the action is 2 we decrease our counter at the given index.

[2, 2] → [undefined, undefined, 0, undefined, 2] + [1, 0, 1]

If the action is 3 we check whether the value in our frequencyTracker is "true" or "not 0" or "nor undefined".

[3, 1] → [1, 0, 1] → 0
[3, 2] → [1, 0, 1] → 1

Naming

Some variable names are good, others are ambiguous, like:

charToObj()
obj

This should be improved.