HackerRank Practice Challenge | Frequency Queries

Table of Contents

The Problem

A link to the HackerRank problem:
https://www.hackerrank.com/challenges/frequency-queries

Problem Statement

You are given $q$ queries. Each query is of the form two integers described below:

$1$ $x$ : Insert $x$ in your data structure.
$2$ $y$ : Delete one occurrence of $y$ from your data structure, if present.
$3$ $z$ : Check if any integer is present whose frequency is exactly $z$ . If yes, print 1 else 0.

The queries are given in the form of a 2-D array $queries$ of size $q$ where $queries[i][0]$ contains the operation, and $queries[i][1]$ contains the data element. For example, you are given array $queries=[(1,1),(2,2),(3,2),(1,1)(1,1)(2,1)(3,2)]$ . The results of each operation are:

Operation   Array   Output
(1,1)       [1]
(2,2)       [1]
(3,2)                   0
(1,1)       [1,1]
(1,1)       [1,1,1]
(2,1)       [1,1]
(3,2)                   1

Return an array with the output: $[0,1]$

Input Format

The first line contains an interest $q$ , the number of queries.

Each of the next $q$ lines contains two integers denoting the 2-d array $queries$

Constraints

$1 \leq q \leq 10^5$
$1 \leq x,y,z \leq 10^9$
$queries[i][0] \ni {1,2,3}$
$1 \leq queries[i][1] \leq 10^9$

My Solution

I found this problem to be fairly easy and straightforward so I made a good solution on the first try. Because of this, rather than going straight into my solution I wanted to take a brief tangent and cover the surrounding code that handles input/output.

I’ll be honest: I’m a bit opinionated sometimes as to what I think “good code” is. I think we can all be a bit guilty of that, eh? HackerRank does provide code for the challenges that manage the input/output so you only need to worry about the challenge. Here’s the placeholder JavaScript code for this problem:

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the freqQuery function below.
function freqQuery(queries) {


}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine().trim(), 10);

    let queries = Array(q);

    for (let i = 0; i < q; i++) {
        queries[i] = readLine().replace(/\s+$/g, '').split(' ').map(queriesTemp => parseInt(queriesTemp, 10));
    }

    const ans = freqQuery(queries);

    ws.write(ans.join('\n') + '\n');

    ws.end();
}

It works but I don’t like how messy things look. Here’s how I like to rewrite it:

'use strict'
const { createWriteStream } = require('fs')

const getInput = () => new Promise(resolve => {
  let input = ''

  process.stdin.on('data', data => { input += data })

  process.stdin.on('end', () => {
    const inputs = input.trim().split('\n').map(line => {
      return line.replace(/\s+$/g, '').split(' ').map(Number)
    })

    resolve(inputs.slice(1))
  })
  
  process.stdin.resume()
  process.stdin.setEncoding('utf-8')
})

const main = async () => {
  const stream = createWriteStream(process.env.OUTPUT_PATH)
  const queries = await getInput()
  
  // solution stuff here
  
  stream.end()
}

main()

Like a warm blanket, everything’s all wrapped up now. Here’s why I like to rewrite it the way I do.

I like to have all the input handling self-contained. I also prefer doing all of the formatting done before the ‘real’ code (strings to numbers and all that).
Events are handy but I like promises and async/await way more. Regrettably I can’t entirely get rid of events because I’m not going to spend that much effort messing with streams on a random code challenge online. However, by keeping it all contained within a promise I can treat the entire read stream like a promise and simply await it. It’s easier to see the code flow that way.

Anyway, that was just the set up. Let’s get in to the code for the solution.

class DataStructure {
  constructor () {
    this.numberCounts = new Map()
    this.frequencyCounts = new Map()
    this.results = []
  }
  
  doOperation (op, value) {
    if (op === 1) return this.insert(value)
    if (op === 2) return this.remove(value)
    if (op === 3) return this.output(value)
  }
  
  insert (value) {
    const currentVal = this.numberCounts.get(value) || 0
    const nextVal = currentVal + 1
    
    const currentFreq = this.frequencyCounts.get(currentVal) || 0
    const nextFreq = this.frequencyCounts.get(nextVal) || 0
    
    this.numberCounts.set(value, nextVal)
  
    this.frequencyCounts.set(currentVal, currentFreq - 1)
    this.frequencyCounts.set(nextVal, nextFreq + 1)
  }
  
  remove (value) {
    const currentVal = this.numberCounts.get(value) || 0
    if (currentVal === 0) return
    
    const nextVal = currentVal - 1
    
    const currentFreq = this.frequencyCounts.get(currentVal) || 0
    const nextFreq = this.frequencyCounts.get(nextVal) || 0
    
    this.numberCounts.set(value, nextVal)

    this.frequencyCounts.set(currentVal, currentFreq - 1)
    this.frequencyCounts.set(nextVal, nextFreq + 1)
  }
  
  output (value) {
    this.results.push(+(!!this.frequencyCounts.get(value)))
  }
}

const main = async () => {
  const stream = createWriteStream(process.env.OUTPUT_PATH)
  const queries = await getInput()
  
  const structure = new DataStructure()
  
  for (let [op, value] of queries) {
    structure.doOperation(op, value)
  }
  
  stream.write(structure.results.join('\n'))  
  stream.end()
}

main()

The problem mentioned a data structure so I decided to take that literally and make a class for it. The most notable part of the solution is the use of two dictionaries:
– numberCounts does just that, it keeps a count of every number.
– frequencyCounts keeps track of how many times a given frequency has occurred.

My thoughts making the solution

I’m sure it’s possible to do things with only one dictionary but this seemed like a performant way of solving the problem. With only one dictionary (let’s say a count of numbers) I would have to iterate through the dictionary values every time I wanted to check for a given frequency. Nobody has time for that.

I kept the code fairly straightforward I think, nothing that would make it hard to read. Except for one part, the output function.

output (value) {
  this.results.push(+(!!this.frequencyCounts.get(value)))
}

This takes advantage of a JavaScript typecasting trick. Trying to convert a Boolean to a Number will result in 0 or a 1 whether it’s false or true respectively. Since that is what the problem wants to output it it’s perfect.

And I needed to cast it to a Boolean first since the return of this.frequencyCounts.get(value) would be a number. I was considering whether to delete the key/value pair altogether in the remove() method if the frequency count became 0 but it didn’t seem necessary. If I had done that I could use this.frequencyCount.has(value) which would make the cast to Boolean unnecessary.

Oh and I decided to use a Map() as opposed to a plain object because, according to the docs a map “Performs better in scenarios involving frequent additions and removals of key-value pairs” which fit this use case.

Anyway, that’s all I can think to say on it, cheers!

TL:DR – My Final Solution

'use strict'
const { createWriteStream } = require('fs')

class DataStructure {
  constructor () {
    this.numberCounts = new Map()
    this.frequencyCounts = new Map()
    this.results = []
  }
  
  doOperation (op, value) {
    if (op === 1) return this.insert(value)
    if (op === 2) return this.remove(value)
    if (op === 3) return this.output(value)
  }
  
  insert (value) {
    const currentVal = this.numberCounts.get(value) || 0
    const nextVal = currentVal + 1
    
    const currentFreq = this.frequencyCounts.get(currentVal) || 0
    const nextFreq = this.frequencyCounts.get(nextVal) || 0
    
    this.numberCounts.set(value, nextVal)
  
    this.frequencyCounts.set(currentVal, currentFreq - 1)
    this.frequencyCounts.set(nextVal, nextFreq + 1)
  }
  
  remove (value) {
    const currentVal = this.numberCounts.get(value) || 0
    if (currentVal === 0) return
    
    const nextVal = currentVal - 1
    
    const currentFreq = this.frequencyCounts.get(currentVal) || 0
    const nextFreq = this.frequencyCounts.get(nextVal) || 0
    
    this.numberCounts.set(value, nextVal)

    this.frequencyCounts.set(currentVal, currentFreq - 1)
    this.frequencyCounts.set(nextVal, nextFreq + 1)
  }
  
  output (value) {
    this.results.push(+(!!this.frequencyCounts.get(value)))
  }
}

const getInput = () => new Promise(resolve => {
  let input = ''

  process.stdin.on('data', data => { input += data })

  process.stdin.on('end', () => {
    const inputs = input.trim().split('\n').map(line => {
      return line.replace(/\s+$/g, '').split(' ').map(Number)
    })

    resolve(inputs.slice(1))
  })
  
  process.stdin.resume()
  process.stdin.setEncoding('utf-8')
})

const main = async () => {
  const stream = createWriteStream(process.env.OUTPUT_PATH)
  const queries = await getInput()
  
  const structure = new DataStructure()
  
  for (let [op, value] of queries) {
    structure.doOperation(op, value)
  }
  
  stream.write(structure.results.join('\n'))  
  stream.end()
}

main()