1
\$\begingroup\$

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;
}
\$\endgroup\$

closed as off-topic by vnp, Stephen Rauch, Heslacher, Toby Speight, yuri Aug 27 '18 at 14:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – vnp, Stephen Rauch, Heslacher, Toby Speight, yuri
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Are you sure that this test case is failing? Seems ok to me. \$\endgroup\$ – insertusernamehere Aug 27 '18 at 8:29
  • \$\begingroup\$ Yes... that is weird and complexity or memory is not the reason which makes is weirder. When I try it on my own editor, it works fine but it does not work in the hackerrank. You could try it to check if you want to see. It says 'wrong answer'. It doesn't even say 'terminated due to timeout' @insertusernamehere \$\endgroup\$ – Ugur Yilmaz Aug 27 '18 at 15:52
  • \$\begingroup\$ I've tested your code on HR and it failed due to timeout for me. Your implementation seems fine. Can you re-check? If this is the case, you can edit your question and set the tags to optimization. We can then reopen the question. :) \$\endgroup\$ – insertusernamehere Aug 28 '18 at 8:20
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your solution but even your code does not pass all the test cases in hackerrank. It caused a timeout for 5 test cases out of 14. Seems okay to me though. @insertusernamehere \$\endgroup\$ – Ugur Yilmaz Aug 27 '18 at 15:59
  • \$\begingroup\$ @UgurYilmaz Do you have input values for the failed test cases? It would be interesting to optimize the code further for those. \$\endgroup\$ – insertusernamehere Aug 27 '18 at 16:01
  • \$\begingroup\$ All I could say is it is tested with an array size of 10000. It is not possible to insert all the index here. Other than that, to be honest, I am trying to understand your approach and but I really don't understand how would you get the same output by not visualizing all the steps? How do you determine if a number is used more than once for the 3rd action by not creating an object to hold occurrences? I am kind of confused how do you manage to work it with the only array? And do you have any idea why my code in the above does not work for the test case I did put? \$\endgroup\$ – Ugur Yilmaz Aug 27 '18 at 16:15
  • \$\begingroup\$ I've set up a little performance test in this fiddle. It's running both versions against 100.000 values in the range of [1..1000]. The original takes around 7-8s, the other version 100-120ms on my machine. Maybe I got some time tomorrow to think of a way to optimize this even further. @UgurYilmaz \$\endgroup\$ – insertusernamehere Aug 27 '18 at 16:54
  • \$\begingroup\$ I've optimized the code again and it's now passing all tests on HR. It seems that your code failed not due to a false result but due timeouts - at least in my tests on HR. I also updated the explanation. If you have any questions, feel free to ask. @UgurYilmaz \$\endgroup\$ – insertusernamehere Aug 28 '18 at 11:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.